I participated in ICFPC 2020 last weekend to continue my tradition of using this programming-contest as a fun way of spending three days trying to program a solution for a really tough problem. This year’s contest was organized by a team from kontur.ru that has itself been performing quite well in recent iterations of this contest. As it turned out, the famous quote by Winston Churchill was quite apt for this year’s contest: “It is a riddle wrapped in a mystery inside an enigma; but perhaps there is a key.” Somewhat incredibly, I ended up being both very frustrated with the contest as well as managing to have lot of fun working through it. It is quite weird, to be honest.
The Task
A fictional space-observatory in Russia starts receiving encoded messages
from aliens that are posted as teasers by the organizers during the days
leading up to the contest. If you are familiar with the Pioneer plaque, the
Arecibo message,
and/or the Lincos
language, you will get a fair idea of the gradual progression of more and
more complex messages that seek to build a language for communicating with the
aliens. A community of contestants starts decoding these messages and updating
the documentation on a
web-site provided by the organizers. At the beginning of the contest, even more
messages are provided by the organizers to be decoded, including a “huge
message” that turns out to be the instructions to run a “galaxy
simulator” using a programming-language and interaction-protocol
described by the previous set of messages. It was unclear what needed to be
done after that.
As a contestant, or even as a casual participant like yours truly, you had to:
- Understand the task-specification, such as it was, to figure out what needs to be done. This documentation was built and refined by the community of contestants sending in Git pull-requests during the days leading up to the contest (based on the teaser-images posted by the organizers) and even into the early hours of the contest, but they apparently gave up at that point. The result was that the documentation remained quite incomplete and vague about the task at hand till the end of the competition.
- Implement a reasonably-performant and bug-free virtual-machine with a graphical interface to run a “galaxy simulator” written in purely functional programming-language (that was defined – incompletely – by the task-specification). This VM had to communicate with a server hosted by the organizers using an HTTP-based protocol that was also incompletely specified. It had to have a graphical UI to be able to precisely capture your mouse-clicks.
- Literally click around a lot of times at random places in the galaxy simulator UI hoping to uncover some clues about what is to be done next. If you persevered, and had not yet developed RSI from the constant clicking, you would discover (apparently – I just gave up at this point) that you have to create a bot for controlling a ship participating in a battle against another ship orbiting a weird square planet with a weird gravitational field. Your bot would be pitched in a battle against bots written by other contestants to determine the overall winner of the contest. That was the task for the contest.
To say that this was frustrating would be a gross understatement. What compounded this frustration was that there were so many different channels for the organizers to disseminate crucial information (albeit cryptically) – the main contest web-site, a couple of blogs, Read The Docs, YouTube, Twitter, Discord, Twitch, etc. were all used – the Discord chat in particular, was apparently quite critical (I hate trying to concentrate on solving a problem and having to constantly check a busy chat-room, so I missed out on all such information that never made it back as updates to the task-specification).
This year’s contest would have been particularly difficult for newcomers, especially if they did not already know the basics of functional programming and the lambda calculus. If the contest is not approachable for newcomers, and frustrates old-timers, the already-small community will become even smaller over time and might even disappear.
What is even more frustrating is that it is quite obvious how much love and effort the organizers have put into the contest, so why would they squander it away on an ill-defined task like this? The galaxy simulator is incredible and contains tutorials, mini-games, easter-eggs, battles, etc. all expressed via a fairly “pure” and abstract language. I gather that the submission-system was also quite good and worked flawlessly for the contestants. The technology behind the contest is an amazing achievement.
My Attempt
The contest started at 18:30 IST on a Friday and ended at 18:30 IST on the
subsequent Monday. I had tried to end my work-day by the evening while I was
still in the middle of an interesting coding-session, but that turned out to be
a mistake – I could not stop thinking about it while reading the
task-specification, so to clear up my head-space I decided to go back and
finish the coding (as well as writing the unit-tests) – this
unfortunately meant staying up late into Friday-night.
I got up relatively late on Saturday and had to finish a few chores in the middle of yet another lock-down in Bangalore due to COVID-19. When I got back to the problem, it was still as inscrutable as ever. I spent hours trying to decipher parts of the task-specification and then gave up in frustration.
On Sunday morning, I started coding up whatever I could understand of the task-specification. I chose Go once again, and made decent progress with writing a small lexer, a recursive-descent parser, and an expression-evaluator that was helped immensely by the pseudo-code posted by the organizers.
By Monday afternoon, I had ironed out enough of the bugs to get the simulator to work along with a rudimentary visualizer and to explore it further (albeit far too late to matter for the contest):
I spent an inordinate amount of time trying to figure out and correctly implement the modulation and demodulation of a list of messages, which was necessary to communicate with the server run by the organizers. Correct communication with this server was necessary even for local explorations within the galaxy simulator. This was made difficult by trying to decipher whether tiny little squares in the given image were a ‘0’ or a ‘1’ and how many of them were there for each input-case.
An embarrassing cause of a lot of wrist-pain was that I was drawing each layer of the images resulting from every expression-evaluation in the same color, making it impossible to tell where I was supposed to click (resulting in me trying to click everywhere inside the drawn parts). The organizers have gone out of their way to ensure that contestants implemented precise capture of mouse-clicks. This also made me implement a “dynamic zoom” feature so that the target-squares for the mouse-clicks were much bigger for the initial click-tests in the galaxy simulator.
A frustrating bug caused me even more wrist-pain due to having to click around a lot in the UI, as I wondered why the galaxy simulator was so slow in moving through its frames. Because the galaxy simulator went through an expression-evaluation cycle only after a mouse-click (and I had discovered that injecting random mouse-clicks to speed up this process was not a great idea), it was not immediately obvious to me that the underlying problem was that my mouse-clicks were not getting registered with the right values when negative coordinates were involved. This turned out to be due to the way Go rounds integer-division towards zero even for negative numbers (just like C/C++).
It was nice to see it all finally working in the galaxy simulator at a decent speed and then to explore around in the UI (there is even a tic-tac-toe game in there). One of the interesting things to note is that the task-specification has all the images “upside down”, as becomes obvious when you render the humans shown above. The flip side of drawing things the right way up is that it is not easy to spot the symbols from the task-specification in the UI. Neither orientation of the Y-axis is thus optimal. One of the organizers noted, “In space, what is up and what is down?“.
The time for the contest was up by Monday evening and I gave up trying to decipher it further. However, I continued to tweak things (and fix a couple of bugs) over the next couple of days. This turned out to be interesting enough in the end that I plan to shortly revisit it and explore it further.
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. (I particularly liked this three-part series of write-ups by Dmitry Astapov.)
Epilogue
The frustration with the task-specification this year led me to become
nostalgic about some previous years’s task-specifications. To my horror,
I found out that many of the past contest web-sites were no longer working.
Thanks to the Wayback Machine, I was
able to salvage some of these task-specifications and problem-sets. I have
now uploaded them to my repositories above, in case anyone else finds these
useful. Of course, task-specifications and problem-sets for contests requiring
interactions with a server not existing any more will be of limited value.
Despite resolving to code more in Go the last time to get more familiar with its idioms and standard library, I have not spent much time with it in the interim. This is because my day-job involves coding (when I do get a chance) in C++. This meant that I spent a lot of time figuring out how to do even the basic things in Go, exploring some of its standard library to see if I could use something from there (I could, in a lot of cases – it seems like a nice “batteries included” approach like that of Python), etc. Not good.