ICFPC 2024
ICFPC, the annual competition associated with the functional programming conference, this year took place from June 28 to July 1. Ilya and I participated for the 11 time as Sunspear team with C++, and for us it was the most interesting year.
Initially we got involved in all this after reading reports about the 2006 and 2007 years. The highlight of those years was that, besides the main task, there was some room for mystery; task wasn't clear at the start - you had to figure out some system devised by the organizers, and only then you could advance in solving the main task and earn points. Unfortunately, this approach is rarely taken by organizers (different people each year), and usually they give just a formal description of the task, which you solve all the contest. During our participation, only in 2020 there was an attempt to do something more intricated, but it didn’t turn out well - there was starting task that opened up a whole bunch of puzzles explaining the main task and how to solve it. Ideally interesting, it seemed. But the starting task was overcomplicated, and organizers were forced to provide hints, then solution diagrams, then pseudocode for the solution, which didn’t add enthusiasm to do anything ourselves.
But enough history, let's return to 2024. Before the contest, there were several teasers, and they made my heart beat faster because they referenced years 2006, 2007, and 2020, but I cautiously refrained from getting too excited. But then contest begins, we open the rules, and there is no task, just a description of how to communicate with a server. The setting this year was as follows: the ancient secret society, which was the focus of the 2006, has actually left Earth (I can understand why), and apparently thrives somewhere among the stars, and we've got access to their cosmic server. All that is known is that if you send the string S'%4}).$%8 to the server, it responds with some mess of characters.
To be more precise, not quite "mess", it was known how strings were encoded - a symbol is converted to S, b to !, c to ", and so on. In addition, there was a whole invented functional programming language, let's call it Alien, the program on which could be sent to the server, but it was still unclear for what. In two lines, I wrote a string re-encoding so that we could write and read in a human-friendly manner. It turned out that the S'%4}).$%8 command is get index, and the server responds to it with a long description that this is an educational server with several courses that you can take to earn points - aha, so here they are, the tasks. Initially, only two courses were available, and the total number was unknown.
The first course was called lambdaman, and it's a set of two-dimensional maps for a Pac-Man-like game with character named lambdaman, but without ghosts, only walls and pills. You need to send a solution for each map in the form of a sequence of moves up-down-left-right (symbols UDLR) that allows lambdaman to eat all the pills. The shorter the message, the better. Note, it's not the number of moves that counts, but the length of the message. So if you compress a string with a program in Alien, you get more points.
The second course was spaceship. There's an infinite two-dimensional field and a list of coordinates to visit, and you control the acceleration of the spaceship. Here, the fewer moves, the better, so compressing isn't necessary.
After reading all these rules and getting inspired, I went to take care of the baby, while Ilya started setting up the infrastructure for the future parser and interpreter of the Alien language, initially implementing only strings. After about four hours, we had our console that could send strings to the server and output decoded responses, along with a bunch of classes for the interpreter.
Next, Ilya started working on the spaceship, while I made a mistake. I have a project template specifically for ICFPC that automates running tasks in threads with different solvers, recording results in a database, selecting the best ones, etc. This has been the format for every past year: one task for which you need to compose an algorithm. Seeing the tasks, I decided it was time to dust it off, even though it was completely inappropriate. First, I spent a lot of time (about 3 hours) adapting it to solve various types of tasks, and for the rest of the contest, I was busy maintaining the system's functionality. Essentially, it was an overcomplication for features that weren’t needed.
Because of this, I started working on the first real task only 8 hours after the competition began. I got lambdaman, which was essentially a traveling salesman problem: visit all the points in the list with the minimum number of moves. I decided that for quick results a straightforward solution would suffice — just move to the nearest pill each turn. We can improve the results later when we had some ideas about string compression. This approach usually works for ICFPC, at least in my case: if I start overthinking, I risk not solving the task at all.
For the spaceship, Ilya also decided to start with a greedy algorithm to choose the sequence of passing points. The acceleration needed to be adjusted so that the spaceship would not just pass through the points but actually be on them at the end of a move. During one move the acceleration could be changed only by +/-1 on each axis, so Ilya had to make the spaceship "orbit" around points. For instance, if the spaceship needed to travel 2 moves on one axis and 5 on another, it couldn't always slow down enough on the first axis to be at the point exactly in 5 moves. This required flying past the point (often on both axes) and circling back around.
Ilya managed to think over this algorithm and then went to sleep, having noticed that many teams were overtaking us on the hello – another task where we gained points for simply sending valid commands to the server, like get index, get lambdaman, get scoreboard, etc. We had already sent everything we knew, and the only remaining option was to solve language_test, a language interpreter check. Ilya couldn’t believe that so many teams had written an Alien interpreter in such a short time, but later it turned out to be true.
I finished coding lambdaman, and it turned out that a few tasks couldn’t be solved because the server sent them as Alien programs, which we couldn’t execute yet. Nevertheless, I earned the first points for the task, bringing us up to 133 place (not really great), so I should have gone to sleep. However, the hello task kept bothering me. I spent about half an hour trying different commands, hoping to find something we missed that everyone else didn't, and I was convinced that everyone had just written an interpreter. I decided to start on it, thinking that maybe it would be quick, and we could perform better in the lightning division (points cutoff for the first 24 out of 72 hours of the competition). However, my brain completely refused to grasp the paradigms of functional programming, and I had to spend several hours learning what it is and how it works. Having finally settled it in my head, I went to ~~sleep~~ wake up the baby, and only after sending him off on a walk with his grandmothers did I get to bed in a semi-conscious state. Finishing the interpreter by the lightning division cutoff was no longer an option.
While I was sleeping, Ilya finished the spaceship task, allowing us to enter the top 100 in the lightning division. We could have earned more points, but several problems remained unsolved because Ilya's data storage method was suboptimal, causing the program to hang. He fixed this bug just an hour after the lightning division cutoff, which was a bit frustrating. Spaceship task turned out to be not so simple. Firstly, one of the maps was given as a program in Alien. Secondly, the solutions for last few problems were so large that the server wouldn't accept them (there was a 1 MB limit for the solution of a single problem). This meant that these solutions also had to be sent as programs in Alien, which we still couldn't do.
After we submitted part of the spaceship solutions, the third course opened up to us – 3d, and it's something! As you might have guessed, 3d means three-dimensional, but here's the twist: the third dimension is not space, but time. There is a two-dimensional field where you can place input value cells, result cells, arithmetic operators, comparison operators, and movement operators (but there are no operators for comparison like "greater than" or "less than"). Each operator has inputs and outputs; for example, the addition operator takes two arguments from its left and top, adds them, and in the next move places the result to its right and bottom, while the input values disappear. The movement operator, as the name suggests, moves its input to its output, and the argument doesn't have to be a number; it can move other operators as well... oh, functional programming! Finally, there is a time-warp operator, which moves the input value to a cell at specified relative coordinates in space and time, and forgets later timeline history. With several such operators, you can send multiple values back in time, but you need to ensure they all jump synchronously to the same point in time; otherwise, the program is considered incorrect.
The evaluation criterion is the program's volume in space/time. In other words, the smaller the area the solution occupies and the shorter the cycle time before a time warp, the better. This is quite mind-blowing because it turns out that it's super efficient to use loops. For example, to find the maximum of two numbers (with a known range), you need to increment each of them by 1 in a time loop until one of them reaches the maximum. It's very unusual to think in such terms.
There were 12 tasks to solve in this course, ranging from simple (find the factorial of a number, take the absolute value, find the maximum of two numbers, etc.) to complex (find the sine; check that in a string encoded as a number, consisting of many opening and closing brackets, the brackets are correctly balanced).
Ilya enthusiastically tackled this course, spending all the remaining competition time on it. He discarded the idea of writing a graphical interface to compose solutions manually — it was uncertain whether it would pay off. Even the interpreter he wrote for debugging the ready solutions could have been skipped — the best tool turned out to be a LEGO Duplo constructor with stickers.
I went on to battle with the Alien interpreter, cycling several times through the stages of "everything is clear, let's work" and "oh my god, I have no idea how this is supposed to work." You might ask, "What's so complicated about it?" Well, once you understand the concept, it's not too bad, except you need to force your brain to think in a strange, somewhat unnatural way. You have to think not in terms of objects and functions applied to them, but only in terms of functions, which don't even know what they are working with (strings, numbers, etc.). Mostly, they call their body (another function) with some argument, which is also probably a function, and only somewhere deep in this chain does the real action happen — string concatenation, multiplication, comparison, etc. That's why debugging was not easy: in order to find where something goes wrong, you have to check step by step how everything is supposed to work, which is tedious and unpleasant. My mood was further dampened by the thought that those damned functional programmers had probably written a converter from Alien code to Haskell in 20 minutes and were not worrying at all, while I had to suffer.
Finally, the language_test program reports, that I passed the test and need to send the special number to the server to gain my scores. I rejoiced, but it was premature — the server did not accept the result. Endorphins kept me from giving up, and I went back to fixing bugs with my last bit of strength. It turned out there was an overflow during operations on int, 32 bits were not enough. I switched to int64 (later I switched to int of infinite length), and success! Curiously, I conquered language_test exactly one minute after the halfway point of the competition, catching up with the other teams on the hello task. How I learned to stop worrying and love functional programming.
Then I remembered that I could now decode the tasks that the server sent in the Alien language and earn points for them, but it wasn't that simple — my interpreter broke on each of them except for one spaceship task. I sent at least that one. Together with the language_test, it only bumped us up 14 places in the rankings, and we were still below our lightning division result, meaning the other teams were performing better. I went to sleep for a luxurious six hours.
The final day of the competition started. After handling household chores and the baby, I tackled the remaining bugs in the interpreter and solved all lambdaman tasks except the last one (21), which hung up completely. I spent a long time scrutinizing its code, trying to figure out what was wrong. Ilya raised the question of whether it was worth spending more time on it, and we decided it was better to focus our efforts elsewhere. At some point, the organizers gave all teams access to all courses, and a new course — efficiency — became available to us. I headed there, hoping for something new, but found a bunch of Alien programs. Each program returns a number that needed to be sent to the server as the solution. None of them worked with my interpreter, they hung, just like lambdaman21.
With my now experienced eye, I looked at the first of these tasks and realized that it was just a program of the form f(f(1)) and so on, with 20-something nested f's, where f(x) = x + x + x + x. So the program returns (4x)^N, where N is the depth of nesting. Why was it hanging then? Even a sixth-grader could manually calculate the result for x = 1 and N = 20, though not quickly. It turned out the issue was with lazy evaluation: in a typical program, we would solve this problem from the end, first computing f(1) = 4, substituting the result into the next f(4) = 16, and so on to the top of the stack, a total of 20 function calls. Here, however, we were forced to go from the top down, and that what happens. We take the very first f call with the argument from the remaining 19 nested f's and substitute this argument into the function without evaluating it (lazy calculatio-o-o-ons!), resulting in 19 f + 19 f + 19 f + 19 f. Then we try to evaluate the first operand, which is f of 18 nested f's, substitute the argument, and get 18 f + 18 f + 18 f + 19 f + 19 f + 19 f. It's not hard to guess that we are finding (4x)^N as the sum of over a trillion 1, and it's not just a trillion additions. Each of these additions involves a bunch of operations on the tree of the executed program. Madness 🙂
The course description for efficiency kindly left a hint that besides the call-by-name strategy for substituting function arguments (where we literally copy the argument to all places of use and compute it independently each time), there is also call-by-need, which does the same but with caching: if the substituted argument has been computed with certain inputs, it won't be computed again; instead, the saved value is returned. Simple and logical, I thought, and went on to implement it. After half an hour, I realized that nothing was simple at all, and in fact, I didn't understand anything. My completely exhausted brain refused to think; my thoughts were wandering in circles. I went to bed but couldn't fall asleep. I opened the next tasks from efficiency and recognized a familiar pattern, similar to lambdaman21, which I hadn't figured out so far, so I decided to return to it.
After delving into the lambdaman21 code again, I realized that it was a loop in Alien. The Alien language doesn't have a built-in loop instruction, but with three lambdas, an if, and a little magic, one can be created, as the organizers demonstrated. In task 21, the loop runs from a very large (12210-digit) number to 0, each iteration finds the remainder of its division by 4, depending on the result adds one of four hardcoded characters to a certain string (which is the output of the program), and then divides the number by 4, decreasing it. My goodness, this is the algorithm for decompressing Alien int into a string of 4 different characters, exactly what I needed for compressing lambdaman solutions! I manually edited the Alien decompression code for my needs, wrote the compression in C++, uploaded new solutions, and Ilya simultaneously uploaded the manual solutions for the first three 3d tasks. Finally, we climbed up from the 129th place, where we had slipped to, to the 67th. It was 8 hours till the end of the competition, supposedly I should sleep a bit and make the final push, but I couldn't.
I spent about 4 hours trying to understand the call-by-need strategy and implement caching, but when I've finished it, the program didn't work as expected. I had no energy left for debugging, so I abandoned it. Ilya periodically brought another 3d solution, keeping us from losing our place. He solved a total of 6 problems. Following his example, I manually solved several initial efficiency tasks before they grew too large. At some point, I realized that I had actually fully understood lambdaman21; it's just that my interpreter can't compute it for the same reason as efficiency, but C++ can 🙂. I translated lambdaman21's code from Alien to C++, finally got the task's map, solved it with my not-so-smart algorithm, and moved up just a couple of places - everyone else had also solved it.
There wasn't any energy left for something big, and only about 40 minutes remained until the end of the competition. We could have tried to compress the last spaceship tasks to get some points, but we realized we just couldn't manage it right then. So, Ilya and I shook hands, and ICFPC was over for us. We took 64th place out of 470 registered teams, although only about 250 of them actually did something. Not the most impressive result, but I can't say we made any major wrong decisions or wasted a lot of time. Still, in future years, we need to force ourselves to stop and think before rushing to solve/use/invent something.
It was a great contest in terms of organization: simple task descriptions on one screen, a wide range of opportunities to apply efforts and earn points, well-thought-out progression - the organizers correctly estimated how much time each subtask would take, placed the tasks in the right order, provided hints where needed, and kept silent where not. No tedious and boring wrappers for server exchanges, no JSONs, just pure enjoyment from solving tasks and looking at Alien code 🙂. Let's see what next year brings.
