This is part 2 of this article, where I share my experience in the ICFP 2024 Contest.

Warning: the next part contains spoilers for the ICFP 2024 Contest.

In the first part of the article I wrote about my participation in the ICFP contest 2024, together with Filippo Testini, and the first two challenges we had to tackle: Hello (build an interpreter for a functional language called ICFP) and Lambda-man (solve Pac-Man-like mazes, with no ghosts but many more pills).

There was a third task unlocked at the beginning: Spaceship.

This task was a twist on the "classic" computer science problem, the Travelling Salesman Problem, where you must visit multiple locations in an optimal order.

In this case the Salesman was driving a Spaceship, with two independent engines: one for vertical movement and one for horizontal movement (that could be turned on at the same time, giving a diagonal movement). Each turn, you could turn on an engine, increasing the speed of the ship in that direction (or decreasing it, if it was opposite of the actual direction), or turn it off, leaving the speed unchanged (since this is space, with no friction).

You were given in each problem a number of "space coordinates" you had to visit, the faster (less turns used) the better.

Solving this problem actually meant solving two sub-problems:

Filippo was in charge of this problem for most of the time, and with a combination of "classic" algorithms (Dijkstra's algorithm, A* Search) and a sprinkle of math (Gauss summation formula) we made good scores. 

Some of the problems were actually programs written in the ICFP language, that your interpreter had to decode. One of them contained an easter egg (which we found!): a link to a secret section of the server, giving you an encrypted password of a fake administrative user! Decoding the password (it was "lambda" by the way), was a backdoor giving you immediate access to problem four: 3D. Otherwise you had to wait for the fourth problem to unlock on day 2 of the contest.

Now things got interesting... We were introduced to another strange computer language called 3D, and you were supposed to program the solution to classic problems, like finding Fibonacci numbers or checking if a number is a palindrome, with it.

This language was a very simple language, character based, but on a 2D grid! Other than numbers and the classic mathematical operators, you had operators to "move" numbers on the grid in a direction. Here's a simple program that adds 1 to the input number (variable A, let's say it was 3), and returns it as a result (+ is the sum, v "moves" the upper number down). If you squint you could see the numbers moving.

.....     .....     .....     .....  
..A..     ..3..     .....     .....
.1+..     .1+..     ..+4.     ..+4.
..... ==> ..... ==> ..4.. ==> .....
..v..     ..v..     ..v..     ..v..
..S..     ..S..     ..S..     ..4..

If this wasn't crazy enough, this language has an operator, called "@", that performs time travel (the third dimension of 3D)!
This operator allows you to go back in time, rolling back to a previous board state, except for a single number that could be different compared to the past.
In this way you could implement recursion, but it was easier said than done... for many problems you needed multiple time travels, that you had to synchronize.

Anyway, we solved half of the problems: we could have done more of them, but unfortunately we got stuck on the fifth task... the real end-game boss... EFFICIENCY.

This task cost us many places in the final ranking.
Apparently, this problem involved running ICFP programs that tested the performance edge-cases of the simulator.
I spent more than one full day optimizing the simulator to no avail... It couldn't solve even the first problem.

While trying to optimize the simulator, I began to understand what the problems were trying to achieve, despite the absurd ICFP language.
That thing multiplies by 0... that thing looks like a Y-combinator (it's other lambda calculus stuff)... oh look, this seems like the algorithm for calculating Marsenne primes... so I managed to solve a few problems by hand, but it felt like cheating. After a few problems I decided to stop and try to optimize the simulator even more, but with no results: the program just kept running forever.

After the end of the contest I asked the other contestants how they managed to solve those problems, and the answer was unexpected: all of them solved the problems by hand, nobody was able to optimize the simulator enough, and as a matter of fact (and by admission of the organizers themselves) it wasn't really possible, as the problems were designed to be awfully inefficient!
So solving them by hand was the right path, and all the fine-tuning and optimization part was wasted time. 

This happens when you stubbornly continue to pursue a failing path instead of evaluating alternative approaches. Lesson learned!

This contest tested the limits of our knowledge of the "format" of the challenge, of combinatorial algorithms and how to work together for this kind of tasks.
What we learned:

We are rather satisfied of our score (we were 61st of about 300 teams), but now we have a full year to get prepared... next time we want to do better than that!