I just finished taking part in ICFPC 2025 over the weekend. This was a nice contest with a deceptively simple task that turned out to be quite hard. It did not require any familiarity with Functional Programming concepts. I had a lot of fun during the contest, but did not have any breakthrough in actually solving the problems. In other words, I continue the glorious tradition from past years.
The task this year was inspired by the novel “The Name Of The Rose” by Umberto Eco – William of Backus and Adso of Milner travel to the monastery of St. Kleene, where they would like to map out the renowned Library Of Lambdas despite the machinations of the jealous librarian Alonzo of Curry. (Yes, there are so many references to famous people in Functional Programming.) They must map out the library during surreptitious expeditions at night based on planned traversals through its rooms and only partial records of the room-labels. They had to minimize the number of such expeditions, as each expedition incurred a risk of getting caught.
I chose to solve the problem this year using Go. I was able to solve the sample problem both manually and programmatically in a day, but only because it used distinct room-labels. The complications of distinct rooms having the same room-label, doors leading back to the same room or even back to themselves, the randomization of the problem during each attempt, etc. meant that the task was quite difficult to solve reliably. In the end, I committed a broken implementation because I could not continue beyond the contest-end due to the server being turned down (probably to limit AWS bills for the organizers). That was a bummer. Despite that sorry end to the contest, I had loads of fun trying to come up with heuristics to solve this task during the given time.
For each attempt, I just generated a single plan of the maximum allowed length
comprising traversals through random doors of whichever room I found myself in.
If I was lucky, I would get enough information back through the recorded
room-labels to reconstruct a map that was equivalent to the original map of the
library. To reconstruct the map using the recorded observations, I initially
marked each observation as a potentially distinct “phantom” room.
Then I turned each exit discrepancy into a “real” room (e.g. if you
see that the door numbered x in a room labeled A leads
to a room labeled B in one instance, but one labeled C
in another, they must be distinct rooms). Then I tried to find common sub-paths
of a certain minimum length in the overall traversal that strongly hinted at a
the same set of rooms being visited (e.g. you see A2B3C2D1A once
and then again the same pattern a while later). I wanted to use these findings
to reduce the number of phantom rooms by clustering more and more of them
together, but I ran out of time (and access to the server).
One of the weird things about this year’s contest was that initially there
was no limit on the lengths of the expedition and the number of attempts to
solve a given problem. This meant that several teams got “perfect”
scores during the Lightning Round by just trying out different route-plans until
they got lucky in making a correct guess. The organizers then put a limit of
18×n on the length of the expedition (where n
was the size of the problem), which made it harder to get lucky. For the
problems in the General Round from the Addendum, the limit was further reduced
to 6×n and they could only be solved by employing
additional markers for the room-labels, which made it even harder to get lucky
with the right guess.
Another weird thing about this year’s contest was that there was a single person who was the primary organizer of contest, but they had some obligations during this period that made them take at least two long-distance flights (about 15 hours). This severely limited their availability, although there was a secondary organizer available to address contestant queries. Thankfully there were no major issues during this period.
Continuing my experiment from last year, I once again tried to see if ChatGPT, Gemini, et al could help me come up with a better solution. The models were a bit more helpful this time, but I ended up having to do the bulk of the work myself. More than a year of progress, but their utility on such problems has only improved marginally. (Or maybe I just have not improved in my prompting skills – I am still “holding it wrong”, as they say.)
Interestingly, some of the contestants reported success with using a SAT Solver (including multi-year champions Team Unagi, who uploaded their Rust-based solution here. Others tried to use random walks with Simulated Annealing (including regular participants and winners like Wild Bashkort Mages and Frictionless Bananas).
As a sign of the times, Discord was once again the primary mechanism for communicating with the organizers and with other contestants. There were a few announcements and teasers on Twitter and on BlueSky for sure, but nothing substantial beyond that. The /r/icfpcontest sub-Reddit has sadly been effectively dead for the past couple of years or so. There were no mailing-lists set up this year.
The source-code for my attempt this year can be found on GitHub, on GitLab, and on Bitbucket.