Semicircle Packing

Semicircle packing

A couple of weeks ago, I entered the GPU World short story competition. I'll post my entry here once the winners are announced. The guidelines imply that I needn't wait until then, but usually writing contests don't allow self-publishing before the end of the competition, so I'd rather not take the risk.

The cash prizes are crazily high for a writing competition: a $40,000 first-place prize; and 7 runner-up prizes of $4,000 each. GPU World's prize pool is 13x to 100x bigger than the other short story competitions I've entered this year.1 If you submit the minimum 1,000 words required and go on to win first place, each word nets you 40 US dollars. It is (well, was) worth a punt.

Alright, enough talk about numbers.

It wasn't until I was halfway through writing my GPU World story that I started to scrutinise where this prize money was coming from. At the bottom of the main contest page, two supporters are listed: Paradigm and Guardian Angel Intelligence Inc. The former, Paradigm is a venture capital firm, which the competition guidelines lists as the provider of the cash prizes. The latter, Guardian Angel Intelligence, piqued my interest with its name alone. I was even more surprised when I clicked on its link and discovered it is an article by Gwern Branwen, who also serves as one of the judges for the competition.2 There is some discussion here on Hacker News about Guardian Angel Intelligence and Gwern's announcement of it, but it is mostly speculative because (at time of writing) there is not much public information about the company itself.

Back to Paradigm. I simultaneously felt two things when I clicked on Paradigm's website:

• Awe. Their website is ridiculously cool. To me, it's reminiscent of Ryoji Ikdea.3

• Intrigue. Even though I've run a venture-backed startup before, I don't recall hearing about their fund until now.

I spent a few minutes leafing through the flat-futurist interactive visualisations on Paradigm's homepage, and eventually4 found myself on their Puzzles page.

It is at this point I would like to note that I could easily spend my time producing an article about the motivations behind venture capital firms and startups running and funding writing contests. I'm going to earmark this topic for a future essay, as it appears that we are on the precipice of human originality, creativity, and artistic ingenuity being valued far higher than they were just a couple of years ago.

Paradigm's Puzzles page is an eclectic mix of challenges, such as: making a prediction market bot, writing a prompt for an AI agent's negotiation strategy, and Anthropic's original take-home test. Each puzzle has a public leaderboard and you can submit a solution easily by logging in with your X.com account. What I like the most about the puzzles is that they cover the gamut of approachability, in terms of technical ability. While you can try to hand-optimise an Anthropic kernel if you're able to, you could instead write a prompt to pursuade AI buyers that a pen is worth a lot of money.

I spent a bit of time on the persuasion puzzle but since its verifier is closed and rate-limited to 5 tries per hour, it's not the kind of thing I could obsessively try to crack. So, I looked for something else -- ideally something that I could verify locally on my own machine. It was at this point that I stumbled upon the puzzle that took up a great deal of my thinking time thereafter: the one called "Pack Semicircles".

Principally, this semicircle packing puzzle is quite simple. You have to arrange 15 identical semicircles into whatever arrangement you can come up with, with the objective to pack them as tightly together such that when you draw a circle around your arrangement the size of that circle is as small as possible.

With these kinds of experiments, I like to think about things independently first without looking up any kind of answer. There's a tendency these days to just throw the URL of the page at Claude or Codex and have it come up with a solution or explanation (spoiler alert: I do eventually enlist Codex's help), but I want to sauté my own -- likely naïve -- approaches before getting external inspiration, at least initially anyway.

I'm a visual thinker and tinkerer, so after sketching in my Remarkable tablet for 15 minutes, I moved over to a graphics editor. I've been mostly using Figma for the past couple of years, but I needed some stronger tooling for dealing with shapes (I used to be a power user of Affinity5 Designer / Photo), so I booted Affinity Photo up first to do some rough arranging.

I started by packing most of the semicircles into a rough "outer fan" shape, with a "core" in the middle that would house the remaining semicircles.

But I realised that the segments for the inner core couldn't just be manually fiddled into place without creating a large, inefficient gap. So I started experimenting (again, manually) with more deliberate symmetry and came up with some pleasing inner packings.

This felt like a great way to work on some visual ideas. It was so much easier using an interactive graphics editor than pen and paper to nucleate different, sometimes random arrangements. But I was still struggling to efficiently pack the shapes together in a way where progress was measurable. Up until now, I had been manually setting the enclosing circle to a radius of 3 -- which would put me in the top ⅔ of the leaderboard. Every time I came up with a new visual idea, or tweaked one subset of the semicircles, I had to manually readjust all the other semicircles.

I moved over to Affinity Designer since that has a Symbols6 tool.

Using a mixture of reusable symbol components, and blending modes, I was able to create subgroups of semicircles that I could arrange into different patterns, and automatically repeat and update those patterns as I tweaked them.

I began to realise a couple of things at this point:

• Getting an efficient packing of the semicircles with a symmetrical layout is very fiddly -- even in graphics software that has tools for reusable symbols.

• In isolation, I was discovering asymmetrical tweaks which allowed me to pack certain groupings more efficiently. This was also very fiddly.

I realised that I wanted to build my own visualisation tool. But since I was coming to the end of my initial independent research on this problem, I decided to see what research existed out there just in case that would help inform any tool I decided to build for myself.

Surprisingly, there really isn't much on the internet about efficient arrangements of semicircles! Maybe that isn't so surprising to other people, but I was having a lot of fun doing this, and there is a tonne of work on the internet about regular circle packing, or shape packing in general. I assume the author of the Paradigm shape packing puzzle intentionally chose an odd number of semicircles, because otherwise an even number of semicircles could just be combined into circles and therefore benefit from the wealth of circle packing research out there.7

I found one blogspot (remember blogspot?) post about semicircle packing. The author laments the lack of existing research on semicircle packing and cites one Math Exchange post -- which also ironically laments the lack of existing literature. I was excited about discovering this post, but it ended up being somewhat of a dead-end for me, especially since the author seems to be talking more about even numbers of semicircles.

So I set out to create a piece of software that would allow me to quickly visualise symmetrical semicircle layouts, which solved the two problems (or realisations) I had when using graphics software manually: easy creation of symmetrical layouts, and asymmetrical tweaks to these layouts.

After some back and forth with Codex, I landed somewhere promising with just a couple hours' development time.

You can try it at puzzles.rorz.io/semicircle-packing.

I got exactly what I wanted: a tool that let me arrange as many layers of fanned semicircles (i.e. equally spaced, angled, and oriented) as I wished. Once I'd had fun creating trivial layouts of symmetrical fans manually, I added a new mode called Tighten which would adjust each fan layer's settings to most optimally pack them together into a smallest-as-possible radius.

Just as with my experiments in Affinity Designer, after a while Codex came to the same conclusion as me: we needed a way to make asymmetric tweaks to the overall layout in order to more efficiently pack the semicircles further. The purist in me wanted the best solution to be symmetrical, but the leaderboard containing many results below my symmetrical best of 2.97 had me thinking that this was a futile ideal to pursue.

As a result, a Relax mode was introduced which splits each fan layout into individual layers. These are then tweaked by a search algorithm in order to keep bringing down the enclosing radius as much as possible.

I got to about 2.96 using my tool alone, but that still only had me in the top 50% of the leaderboard. I realised at this point that I needed help from Codex.

I spent a chunk of my weekly Codex usage on Astra Max and Ultra, as well as Sol Ultra and Terra Ultra -- all of which managed to find different approaches using the UI that I'd built up until now. Dynomight's notes on "doing math" were useful reading at this point in order to develop strategies that would get more juice out of Codex's models. Eventually, after getting to the top-10 in the leaderboard and stalling, I decided to take a fresh approach and fork the original Python repo.

After hill-climbing different solutions, I managed to get into the top 3 on the leaderboard (where I've since stayed) with a radius of 2.94853.

Here's the visualisation of that submission:

It's not symmetrical at all!8

While I was in the process of hill-climbing a better solution, Astra Ultra came across a PDF of a paper that the #1 position on the leaderboard entrant (and their agent) created, detailing the various strategies they tried. Sadly, none of these were able to help me and Codex beat them.

Something I reflect on after having spent a few days tinkering with this is that I got the most dopamine from getting Bronze on the leaderboard by way of brute-forcing with Codex; but I got the most fulfilment from sketching out the shapes in my graphics editor and working with Codex to build a custom visualisation tool. I had a tonne of fun working on this problem, and will keep chipping away at it in Codex. I'm also going to update puzzles.rorz.io with more tools as and when I get round to it.

Footnotes

• I entered two short story competitions in the UK this year. One had a prize pool of £7,500, the other £1,000. GPU World's prize pool is $100,000. ↩

• It is fun to see that it's the same Gwern (of Gwern.net fame) who I used to read a lot of when I was at university. Gwern was also recently a judge on the 1Picture1000Words competition which I published my entry for here. ↩

• I've been to many Ryoji Ikeda exhibitions in London, and I would say that he is probably my favourite artist. I recently made the hero image on my LinkedIn profile a pastiche of Ikeda's datamatics work. You can play around with my implementation and view its code here. ↩

• Note to maintainers of Paradigm's website: It's quite hard to spot the link to the Puzzles page as your homepage currently points to https://www.paradigm.xyz/research#paradigm-puzzles from its navigation menu instead of /puzzles. ↩

• Affinity has since discontinued these individual desktop apps after being acquired by Canva. ↩

• I couldn't find a relevant resource to link to here -- the latest documentation is for the superseded version. ↩

• That is to say that breaking up circles into semicircles may still yield much more efficient packings. ↩

• It does have some interesting properties though, and pseudo-symmetry. Perhaps more detail for a later post. ↩