ICFP contest 2024 writeup

Friday

Friday 14:00 in Prague, Andrey Popp (remotely) and I are impatiently waiting for the contest to begin — this is going to be the first time participating for both of us. Before that, we’ve only read some of the after reports — no doubt that’s a lot of fun.

At 14:00 sharp, the task appears: “tldr; there is some ICFP expression language, but don’t bother for now, you only need to be able to encode and decode strings to proceed”. So be it, we had a quick call and hacked something out in Python (don’t judge!). Now we were able to talk to their server! Basically, you need to take some string, say “get index”, encode it, and send it to https://boundvariable.space/communicate as the POST body along with your team token and then decode the result. (By the way, our team name was “Ateam”, you can think of it as “Ahrefs team”, “Andrey & Alexey team” or simply “A team” depending on your point of view and imagination). All in all, we learned that we have two problems to solve (lambdaman and spaceship) and about 25 test cases for each one. In a random manner, we split them — I got spaceship while Andrey took lambdaman.

lambdaman

Labyrinth walking problem, where you have the 2D labyrinth in ASCII art consisting of . - pills and # - walls. The brave lambdaman should collect all the pills, avoiding the walls, and try to do it with the minimal possible moves. The solution to the problem is any expression which evaluates to a string consisting of "UDLR" symbols, denoting the directions lambdaman is taking.

We’ve quickly implemented the simplest possible solution — generate all paths from the starting point and then combine them through backtracking. Hoping next, once we have the way to write proper programs, we’ll be able to compress paths and score more points.

spaceship

You have the integer coordinates of the planets in the 2D universe your spaceship has to visit. The problem with your spaceship is that you can only adjust its velocity by 1 in any of 2 directions at once, and for doing this you have an old numpad with 1 to 9 buttons, where 1 adds (-1, -1) to velocity, 2 - (0, -1), 3 - (1, -1), 5 leaves velocity unchanged, and so on. You have to press one of the buttons, and after that, the spaceship changes its position accordingly: x := x + vx and y := y + vy. So the solution is a series of 1..9 numbers encoded as an ICFP string. Again, the shorter the instruction you have - the better. Much like the lambdaman you'd say. Yes, that’s what we thought too, but apparently not exactly, and we'll learn the hard way on Sunday :(

For the solution, I went with a greedy brute force trying to reach the next point one by one, caching visited points (just in case). For each next speed change, I picked the most “logical” one — e.g. the one which gets the spaceship closer to the destination. The initial list of planets was rearranged in different ways: sorted by Manhattan distance from 0,0, by real distance, by the square of the distance, not sorted, even random order (don’t judge again!). Overall, when I felt tired, I tried various initial sorting and strategies of picking the next speed change and just re-ran all the cases we had — sometimes it resulted in better scores which I didn’t hesitate to submit. We had close to perfect results for the first few cases and the best one for spaceship11 after all.

Very quickly we realized that not all of the problem descriptions are delivered as plain ICFP strings. Some of them (at least lambdaman6, lambdaman9, spaceship22) are full-featured ICFP programs. Andrey quickly put together an AST-based ICFP interpreter (💪) which immensely helped us move forward. However, it was quite slow on some input (or didn't finish). Also, quite obviously, the solution could be submitted as an ICFP expression, which might be more efficient in terms of score (e.g., the general rule about the both problems above - the shorter the better).

So, by the end of Friday, we had:

• a slow ICFP interpreter (not all programs received from the server even completed)
• first 3 or 4 lambdaman solved with mediocre scores
• 80% of spaceship problems solved (same level of mediocrity in scores though)
• a new 3d task appeared in the menu
• and the 48th place on the scoreboard !!!111

The plan for the next day was:

• Andrey was going to rewrite the interpreter to bytecode
• I was going to tackle the 3d task

Saturday

After getting up and reading the thread in the company chat, I realized that we have some internal competition:

$ ./run get scoreboard | rg '(Ateam|piglets)'
> "get scoreboard"
| **37** | ****dysfunctional** | **piglets**** | **91** | **35** | **35** | **** | **** |
| 64 | Ateam | 97 | 52 | 37 |  |

In any case, it was time to start on 3d for me (Andrey worked on an interpreter late on Friday and it was 99% ready by my morning). Honestly, that was one of the things which I was stuck on for quite some time. Basically, the task descriptions were fairly simple: write the abs(), sign(), factorial() functions or similar. However, if you read the language specification above, you'll realize that it is not trivial.

I sat with pen and paper for a while (honestly, till lunch) until I was able to discuss it with my family (yes, they made fun of me): “Imagine, you need to find the absolute value, but you don’t have the greater than/less than operations? How would you do it?”. Maybe it was the break, maybe the rise of sugar level in my blood afterwards, but all of a sudden, I realized that the modulo operation preserves the sign (yes, that was written in the spec from the very beginning 🤦) and that was a breakthrough moment for me. I quickly solved 3d2 (abs) and 3d3 (sign) with quite satisfying scores:

* [3d2] Your score: 2400. Best score: 2394.
* [3d3] Your score: 1752. Best score: 1736.

Here is the 3d2 solution if you're curious, but don't ask questions about it please:

. 2 . 1 . 2 . A
A * . + . % . *
. . . . . . . S

Following that, I solved 3d4 (maximum of 2 numbers) and 3d6 (detect the prime number). At this point, I was super exhausted and totally not satisfied with the fact that I couldn't figure out how to emulate loops in this language. I still can't, to be honest (beyond the idea that time travel operator is needed).

Meanwhile, Andrey significantly improved the performance of the interpreter (it was good enough for all the 3d tasks I had been working on so far) and the lambdaman scores. Also, the new task efficiency appeared in the list. It was quite a "simple" one - given the ICFP program provided by the organizers, run it and submit the integer result as the solution. As simple as that! But... there is always a "but" - our interpreter was not performant enough even for efficiency1 :( Andrey rolled up his sleeves and started to optimize it.

I decided to switch to something else and see how much (and if at all) we could improve lambdaman and spaceship solutions by providing shorter ICFP programs which will generate the answer string. I had really high hopes for RLE encoding, especially seeing spaceship solutions being a long series of 1111122222888811111... etc.

My experiment showed that spaceship solutions score based on the final string length, not the POST body size. However, Andrey's similar experiment with the lambdaman showed different results. I was too tired to make any realistic conclusions, so I decided to stay optimistic and still try to implement some lambdaman cases manually in ICFP.

The solution for lambdaman6 was literally repeating 200 R symbols. So I went ahead and came up with a program:

B. S3/,6%},!-"$!-!.[} B$ Ly B. vy vy B$ Lv B. vv vv B$ L$ B. v$ v$ SLLLLLLLLLLLLLLLLLLLLLLLLL

Which gave us a score of 93 right away (it was 200 before):

~/fun/icfp2024/icfpc2024 [main]$ cat test.icfp | req | decode_s.py decode
Correct, you solved lambdaman6 with a score of 93!

Andrey came up with the idea of making a Python API for writing ICFP programs to avoid this very specific syntax. This ended Saturday with the following plan for Sunday:

• We both have roughly half a day
• Andrey is planning to work more on the interpreter to approach efficiency
• I’ll work on the Python API for ICFP and the RLE encoder for lambdaman/spaceship solutions to improve scoring

Sunday

After some struggling, recalling lambda calculus, and heavily applying the Y combinator, I came up with an implementation of RLE encoding.

The main idea is that numbers in ICFP are base-94, so I thought one number (3 symbols: 2 for the number itself + 1 for space) could represent a series of N symbols from our desired alphabets (UDLR for lambdaman and 123456789 for spaceship). E.g., 1 is U, 2 is UU, 3 is UUU, 23 is D, 24 is DD, and so on. I made a Python program accepting the solution, extracting the alphabet from it, and generating the appropriate RLE encoder in ICFP.

I was extremely surprised, but it worked!!! Honestly, it was a very satisfying moment and I had really high hopes for improving the spaceship specifically. However, this is where frustration waited for me around the corner. They accepted my nice and short spaceship solutions, but scores were counted by the resulting string :( Nevertheless, we were able to improve many lambdaman cases, getting close to perfect scores sometimes. Later on, I manually solved 6, 9, and 10 lambdaman cases (yes, ICFP was at my fingertips!).

In any case, when I called it a day, we still had 0 efficiency solved and Andrey was planning to optimize the interpreter even more. Fast forward, it didn't work and he had quite pessimistic prospects about it (we had a chat around midnight). So, things went in a quite sad direction: we had no clue about efficiency, we were kicked out of the top 100, and "dysfunctional piglets" were definitely far ahead.

Monday

I had almost given up. I tried the last version of the interpreter on the efficiency problems, but that unsurprisingly didn't finish. I gave one last look at the efficiency1 source code and all of a sudden realized that I could read it and roughly understand what it is doing! Try it for yourself, isn't this easy?

B$ L! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! B$ v! I" L! B+ B+ v! v! B+ v! v!

Basically, it’s a forkbomb producing 4^22. An equivalent Python program is:

print(4 ** 22)

That worked! After that, I quickly solved 2, 3, 4, and 13 (the main observation was that recursion is limited by some reasonably big number, so I tried with smaller ones and figured out the principle).

efficiency5 and efficiency6 were more complex. Andrey joined and wrote a compiler from ICFP to JavaScript. We almost grokked efficiency5 without some tiny detail, and after an enormous amount of different tries, we got it!

~/fun/icfp2024/icfpc2024 [main]$ printf "solve efficiency5 2147483647" | decode_s.py encode | req | decode_s.py decode
Correct, you solved efficiency5!

efficiency6 was still unknown, the only thing we roughly realized was that the answer would be somewhere between 40 and 100. Totally not proud of it, but here we go:

~/fun/icfp2024/icfpc2024 [main]$ for i in $(seq 40 100); do echo "$i"; printf "solve efficiency6 $i" | decode_s.py encode | req | decode_s.py decode; sleep 5; done
40
Your answer for efficiency6 was wrong
41
Your answer for efficiency6 was wrong
42
Correct, you solved efficiency6!

At this point, we were totally tired, but quite satisfied and in the top 100 (95)!!!111. Also, it was almost the contest closing time :)

Lessons learned

In no particular order:

1. This is joy, would do it again if I have the chance and a good team!
2. Teamwork matters — you need someone to talk to and share fun with :)
3. Don’t try to come up with the perfect solution (our interpreter improvements didn’t matter past some point — tasks were unsolvable directly anyway).
4. Be brave, don’t be a chicken. I shouldn’t have given up early with efficiency and waited for ICFP interpreter improvement. Looking at task source code earlier would have been beneficial.
5. Experiment a lot — don’t be lazy. One thing I realized late enough is that I might have progressed with 3d faster if I had written an interpreter for it on my own for quicker iterations. Moreover, I see some teams with better results went this route. However, I evaluated this idea and decided not to (and later spent several hours with literally zero progress).
6. Make sure your family is on board and tolerates an inadequate person speaking about lambdas, programming languages, and optimization at the dinner table :)

Links

• Contest
• Scoreboard (Ateam & dysfunctional piglets)
• ICFP language
• Source code
• Other writeups