I participated in the ICFP Contest 2024 from June 28th to July 1st, 2024.
The ICFP Contest is an annual computer programming competition, held in conjunction with the International Conference on Functional Programming. It was the first time that Filippo Testini and I participated in this contest, which was both entertaining and challenging.
In my day-to-day job, managing people is more important than computer programming, so this contest was a breath of fresh air for me! Our objective was not to win (since our two-people team was too small) but to have fun.
We imposed an additional restriction on ourselves: we would develop the main part of the contest in Forth, an obscure, low-level language from the seventies, not your classic "let's smash a couple of ready-made libraries with a sprinkle of Stack Overflow wisdom" programming language, and definitely not a common choice for a programming contest in 2024. (Are you intrigued? I will talk about Forth in a future post!)
The first challenge was deciding the team's name. We settled for Forthissimo. The second choice was "Forth? WHAT???", that was Filippo's initial reaction to my proposal of using Forth.
Without further ado, let's get to the meaty part: the contest's tasks.
Warning: the next part contains spoilers for the ICFP 2024 Contest.
The ICFP Contest is an annual computer programming competition, held in conjunction with the International Conference on Functional Programming. It was the first time that Filippo Testini and I participated in this contest, which was both entertaining and challenging.
In my day-to-day job, managing people is more important than computer programming, so this contest was a breath of fresh air for me! Our objective was not to win (since our two-people team was too small) but to have fun.
We imposed an additional restriction on ourselves: we would develop the main part of the contest in Forth, an obscure, low-level language from the seventies, not your classic "let's smash a couple of ready-made libraries with a sprinkle of Stack Overflow wisdom" programming language, and definitely not a common choice for a programming contest in 2024. (Are you intrigued? I will talk about Forth in a future post!)
The first challenge was deciding the team's name. We settled for Forthissimo. The second choice was "Forth? WHAT???", that was Filippo's initial reaction to my proposal of using Forth.
Without further ado, let's get to the meaty part: the contest's tasks.
Warning: the next part contains spoilers for the ICFP 2024 Contest.
First task: Hello
The first task of the contest was to implement an interpreter for a simple language based on lambda-calculus (called ICFP), which was going to be the main way of communicating with the server.
To give you an idea of the language, this is the implementation of a function that multiplies a number by 2, applied to the number 4:
To give you an idea of the language, this is the implementation of a function that multiplies a number by 2, applied to the number 4:
B$ L# B* v# I" I$
It was a fairly easy task, that showcased some real Forth strengths, except for one crucial part: implementing the beta-reduction step of the lambda calculus with a call-by-name convention.
For the non initiated to the lambda calculus (or computer programming), here’s a simple analogy: imagine you have a recipe (the lambda expression), that calls for chopped onions. The beta-reduction is the process where you actually chop and put the onions in the bowl, following the recipe. Usually you prepare the ingredients and put it in the bowl one by one, but this time you decide to put the onions on the counter, write down on a note "chop the onions" and wait until the latest minute (just before putting the recipe in the oven) to actually chop the onion and mix them in.
This is more or less what happens with the call-by-name convention.
For the non initiated to the lambda calculus (or computer programming), here’s a simple analogy: imagine you have a recipe (the lambda expression), that calls for chopped onions. The beta-reduction is the process where you actually chop and put the onions in the bowl, following the recipe. Usually you prepare the ingredients and put it in the bowl one by one, but this time you decide to put the onions on the counter, write down on a note "chop the onions" and wait until the latest minute (just before putting the recipe in the oven) to actually chop the onion and mix them in.
This is more or less what happens with the call-by-name convention.
Needless to say, we had a lot of onions to chop at the end...
I won't go in too much detail here, but it was not simple. Anyway by Saturday morning the beta-reduction was running smoothly, and we used our brand-new interpreter to ask the server for the next two problems.
Second task: Lambda-man
For this task we had to play a Pacman-like game, without ghosts but with HUGE mazes and plenty of pills to eat. Your score was calculated based on the number of characters that you submitted to the server as a solution (the lower the better).
For example, the solution for this maze (# is a wall, . a pill and L is our Lambdaman):
For example, the solution for this maze (# is a wall, . a pill and L is our Lambdaman):
##### #L..# ###.# #####
was "RRD" (Right, Right, Down).
At first we thought that the key to win this task was to use a super-optimized algorithm to find the shortest path, after all a short path is a short solution, right?
That worked until the sixth level, where we faced a maze like this:
At first we thought that the key to win this task was to use a super-optimized algorithm to find the shortest path, after all a short path is a short solution, right?
That worked until the sixth level, where we faced a maze like this:
############################################################################## #L...........................................................................# ##############################################################################
(it was actually 200 pills long)
So we thought: super easy! You just go right (R) 200 times, it's a piece of cake!
Our score was 200, but then we saw other teams with scores of around 70... we were puzzled! Were they using teleportation skills? How could they eat 200 pills in around 70 moves?
Then it dawned on us: we could communicate with the ICFP language, not just with strings!
So we started to write a compressor in Forth and a decompressor in the ICFP language (we could fit any direction in just 2 bits).
This was the decompressor, feel the pain:
So we thought: super easy! You just go right (R) 200 times, it's a piece of cake!
Our score was 200, but then we saw other teams with scores of around 70... we were puzzled! Were they using teleportation skills? How could they eat 200 pills in around 70 moves?
Then it dawned on us: we could communicate with the ICFP language, not just with strings!
So we started to write a compressor in Forth and a decompressor in the ICFP language (we could fit any direction in just 2 bits).
This was the decompressor, feel the pain:
B$ B$ L" B$ L# B$ v" B$ v# v# L# B$ v" B$ v# v# L$ L% ? B= v% I! S B. ? B= B% v% I% I! SO ? B= B% v% I% I\" S> ? B= B% v% I% I$ SF SL B$ v$ B/ v% I%
This definitely improved our scores, as we could send compressed moves! We were back in the game!
(We'll dive into the other mind-bending tasks in part 2.)