ICFP Programming Contest 2024
This is team "A Storm of Minds" writeup for the ICFP Contest 2024.
We participated as a Team of three: Jan, Daniel, and me (Chris). Daniel was invited to a barbecue on Friday and would join us only near the end of the lightning round. While we prefer meeting in person for the contest, we decided to work remotely this year.
The organizers have published a detailed report
describing the task and the individual problems.
The contest started at 14:00 local time, and five minutes before that time, an emergency cropped up at work, which took me two hours to resolve. But at least Jan could look at the task, write some submission scripts, and solve the welcome problems.
The first task was to understand and implement the ICFP language used for communication. The language was lambda calculus augmented with primitive data types (booleans, integers, and strings) and operations. For recursion, the Y combinator had to be used.
After solving the welcome problems, we could enter the “lambdaman” and “spaceship” courses. All communication with the server was in ICFP language, so we needed an evaluator to decode the problems. Most of them came as a single string literal, which could be decoded by table lookup, but for the rest of them, I started to implement an ICFP interpreter in Haskell. About five hours into the contest, we had the problems decoded, but as it turned out, my interpreter had some bugs that led to incorrect decoding. Luckily, a “language test” was provided, which helped fix these.
Submitting solutions to the “lambdaman” and “spaceship” courses unlocked the “3D” course, which in turn unlocked “efficiency,” making for four courses in total.
The Courses
Lambdaman
In “lambdaman” you were given a labyrinth of ASCII characters where you had to collect pills, much like Pacman.Scoring was by the shortest solution in bytes, which meant that getting the shortest number of moves was not enough for a good score - you had to submit the shortest program that would generate the necessary moves. Given that there were only four possible moves, the most obvious compression was to encode each move as two bits in a long number literal, with a tiny program to decode that number into moves. Some of the problems were even encoded that way. That much obviousness was too much for us, and we failed to see that possibility and just implemented a simple run-length encoding scheme.
Spaceship
The “spaceship” problem involved visiting a given set of locations in 2D space with a spaceship that could increase or decrease its velocity by 1 in both x and/or y direction at each move. This is a typical traveling salesman problem. Larger problems, containing up to 65000 locations, necessitated the use of a heuristic solution.3 1/2 hours into the contest, Jan had written a simple spaceship solver in Python, which just accelerated toward the nearest unvisited location, and was able to submit solutions for most of the problems except for the bigger ones. And that’s basically all we did with spaceship - we were busy with the other problems and did not implement a better solution.
3D
7 1/2 hours into the contest, we had unlocked the 3D course.The objective was to write small programs in a language laid out as operators and values on a two-dimensional grid. The language did not have loops but a time-travel operator that could be used to the same effect. Jan solved these mostly by hand, with the help of some small tools written in Python.
Efficiency
In a way, this was the simplest problem: just evaluate a given ICFP program and submit the result. There was a catch, however: the programs took very long to run, even if compiled to the most efficient native code. For example, problem 5 computed the smallest Mersenne Prime greater than 1000000. My way to solve these was to look at the code to understand what they computed and then write it by hand in a compiled language or solve it using other means. For example, some problems could be solved with a Sat solver (I used Minisat).Conclusion
When the scoreboard was locked two hours before the end of the lightning round, we were at place 22. In the main round, we dropped below place 60. This was a very "classic" contest we enjoyed tremendously, despite not meeting in person and not having the full time for the contest.
Having a grasp of the problem after the first 24 hours and then having 48 hours to find good solutions is something we
like. As usual, we did well in Lightning and worse in the main round. That's likely because we often fall into
the trap of trying small improvents to existing bad approaches instead of taking the time to come up with a
good approach. This can be see in the wonderful journey images the organizers made available right after
the contest. Here's ours. As you can see, it's descending all the time. With some teams, it goes up instead,
which is what it should look like.
Other things I (Chris) liked about this year’s contest:
- Low resource use. I did not feel that a faster CPU or more RAM would have helped. That could have been different if we had implemented an optimizer for any of the courses; in particular, the largest spaceship problems might have profited from more CPU time.
- You could split the work nicely among multiple people. We were three team members, but both 3D and efficiency were worked on by a single person only.
- My decision to use Common Lisp if possible turned out quite well, because I could easily transform the efficiency programs using Lisp code or even macros. Also, having infinite precision integers in the base language was a big advantage.
- We went too far in splitting up the work. That was not even a conscious decision - it just happened that way. Part of the reason might be that we worked remotely instead of meeting in person as usual. Anyway, stopping occasionally to talk about the problems and exchange ideas would have been good.
Our repo is on github.