I took part in ICFPC 2021 last weekend. I was somewhat hesitant going into the contest this year after having been weirded out by last year's task, but I am happy to report that the task this year was a “classic” no-nonsense ICFPC task with a concise and straightforward specification. That did not mean that it was an easy task to fulfill – going by the write-ups from other teams, it seems I was not alone in thinking that.
As my day-job continues to almost exclusively involve C++, I wanted to use this opportunity as a way to properly learn the Rust programming-language. However, once again I could not get it to work on Lucifer in time for the contest. So it was back to coding in Go for me this year as well. At least this way I could learn to program in it a bit more.
The contest started at 17:30 on Friday 9th July in my time-zone and ended at 17:30 on Monday 12th July after 72 hours. I took the day off on Monday to enjoy three back-to-back days of trying to solve a hard problem. This was quite an enjoyable experience, even though I did not successfully solve it. I continued to tinker with it after work on a couple of other days during the rest of the week and will probably do so for at least a couple of more days.
The task was based on the Japanese TV-game “Brain Wall” (watch some clips from the game to get a feel for it). Given a wall with a hole cut-out moving towards a figure, you have to contort the figure to assume a pose that will fit the hole, while trying to minimize the distances of its extremities from the corners of the hole (in other words, maximize how closely the pose resembles the hole). Unlike a human, the edges of the 2D figures in the task could be stretched or compressed by a certain amount (they behaved like springs).
The specification for the task was concisely and precisely stated with no fixes required during the contest (except, of course, for the addition of the traditional bonus-tasks and extra problems). Various problems corresponding to the task were available via a dedicated web-site, which also allowed the contestants to submit corresponding solutions and visualize how they fared. Both the problems and the solutions were encoded in JSON. Thus the task this year was a “classic” no-nonsense ICFPC task and the associated set-up made it really simple to submit and visualize solutions to various problems. The really hard part was in automatically coming up with solutions for the problems.
I started off by writing code to parse problems and solutions (the organizers included a sample solution for the first problem in the task-specification itself). Since it was important to visualize these problems and understand how the solutions looked in relation to the problem, I then wrote a simple visualizer for the problems and the solutions.
I then tried hard to come up with an analytical solution for the problems and spent several hours on it. (It turns out that this was a mistake, as many teams managed to get high scores by simply solving the problems manually – after all, there were relatively few problems to solve and the organizers just wanted solutions to those problems, rather than pit the program from one contestant against that from another. However, what is the fun in that? I take part in ICFPC to try to solve hard problems rather than win a contest.)
After a while, I gave up and tried to take a shot at learning Simulated Annealing and using it to come up with solutions (in other words, a glorified trial-and-error method). But before doing that, I had to implement a few 2D-geometry algorithms and this turned out to be a can of worms of its own. In particular, I tried to essentially implement scan-line polygon-fill and failed miserably at it – in the end, I just ended up using SDL2_gfx to render into an off-screen buffer and then reading back the pixel-values. Shameful.
Simulated Annealing turned out to be unexpectedly weird. In particular, the algorithm as described on Wikipedia, in the book “The Algorithm Design Manual”, the canonical papers cited as references for it, etc. are all different. This seems bizarre to me and I might be missing something here. In addition, no one seems to provide guidance on how to specify various critical parameters for the algorithm to work, what to look out for when trying to get to a solution, etc. It seems like this approach should eventually yield a solution, but all my attempts with it have failed so far. I still want to properly learn it, so I will probably continue to tinker with it for a while longer.
So I ended this year without either manual or automated solutions for any of the problems, which is sad. However, I did learn quite a bit during the contest and I did have fun trying hard to come up with automated solutions for the problems. That is what makes ICFPC enjoyable for me and the organizers delivered on this count. Kudos to them.
The source-code for my attempt this year can be found on Bitbucket, on GitHub, and on GitLab. You can find some other write-ups on /r/icfpcontest (and in this thread in particular) or on the contest web-site itself.