ICFPc 2021 was a great contest, the problem had a relatively short spec that made a low barrier to entry, but it has hidden depth that made it difficult to perfect. It was a truly elegant problem.
The first great feature of this year's contest was that the initial spec was only a mere 5 pages, unlike the huge behemoth that made up the 2020 contest. Also, 2020 year's spec was spotty and initially incomplete, while this year spec was simple with only backward-compatible updates. The minimal amount of required reading and infrastructure work means this year probably has the lowest barrier to entry of all ICFP contests so far.
The task is based on a certain game show, where given a hole and an initial pose, you are to transform the pose such that the new pose will fit through the hole. Edges can only be stretched up to a certain limit, higher points are awarded for being close to the vertices of the hole. This feels like a more lenient version of ICFPc 2016 in the sense that it was another folding problem, but with integer math plus epsilon instead of high precision rational numbers. I was happy to be reminded of 2016 again, although the real deja vu was seeing clips of that long forgotten game show, which definitely caught me off guard. This year's contest was fun from the very start!
The second great feature of this contest was that even though the spec is simple, it elegantly describes a complex task that lends itself to many interesting techniques. Finding where to place all vertices at once seems very difficult, but if you randomly move edges one by one to make them fit, you will observe how it perturbs nearby edges, and eventually gain an intuition for how to solve each problem through rippling updates. This seems like the kind of task that would have been a good fit for simulated annealing, but I am sure there are other interesting approaches that would be applicable as well.
Finally, the contest website and submission interface was extremely stable and responsive, with almost instantaneous feedback. This has been a fairly consistent praise pretty much year regardless of who was running the contest, and I am thankful for another smooth contest this year.
Like 2016, I did not immediately have a good intuition on how to approach this year's task, and resorted to solving each problem manually. But unlike 2016, this year I wrote a tool to do this job instead of folding actual pieces of paper. Initially I had just an SVG generator and thought I would make a batch solver out of that, but I soon reached the conclusion that it's impossible to make progress without an interactive graphical tool, and proceeded to build one out of SDL. Historically I have avoided spending time on visualization tools for ICFP, but this year all the coding time was spent on tweaking the tool. This allocation of time appears to be the right bet, maybe I should spend more time on visualizations in the future.
It was only after playing with the tool for a long time did I have enough intuition on how to automate a solution. Specifically, it was on the second day after I added the feature to draw concentric circles for showing acceptable edge lengths, where it dawned on me that this was a constraint propagation problem, but by then I was already committed to solving all problems manually. I might have taken a different approach if there were something like 200+ problems, but 132 problems seems just appropriately sized such that manual solution was viable, and that's what I did. This manual approach landed me 71th place in the lightning round (out of 137) and 60th place (out of 160) in the full round, which is a pretty good result considering it was mostly brute force.
In terms of actual time, I sunk over ~43 hours into this contest, which is roughly consistent with all previous years. ~33 hours of which was using my tool to manually solve each problem, so there weren't that much time spent on coding at all. In fact, there were about zero time spent on debugging. This is of course because I did very little coding this year, I didn't have time to write any bugs! You can download the tarball here:
https://drive.google.com/file/d/1mwKCCesbJX2SVRAKW3GhAWu0_rFa3jcu/view
Didn't have time to write any bugs... but taking another look now, I immediately spotted multiple typos. There are no tests so there are most definitely bugs, but they were exactly what I submitted so I left everything as is.
I also made a recording of the tool in action, and the corresponding output from contest server. You can see that solving a single problem instance took about 10 minutes for relatively easy problem instances, so definitely not a scalable approach. But it was sufficiently fun that I didn't mind doing it.
Many thanks to this year's organizers for a fun contest. This year's ICFP contest is definitely one of the better ones.
Previous (2021-03-29): Godot Engine
Next (2021-07-24): "Seishun Butayarou wa Nightingale no Yume wo Minai" by Kamoshida Hajime