Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Source code:
source.zip
Solutions:
solutions.zip
The Frictionless Bananas had only one team member this year. This page describes my 2024 ICFP Programming Contest entry.
This year’s task was to implement a programming language, use it to communicate with a server, and solve four independent sub-tasks which the server provides access to. The language is a simple functional language with lambda, apply, if, and various operations on integers, strings, and booleans.
Messages to and from the server take the form of programs in the functional language, which are to be evaluated before they are processed. Messages are often simple string literals, but they can also be complex programs.
A task with four independent sub-tasks is inherently parallelizable, and thus not ideally suited to a single person team, but I made progress on all sub-tasks and had fun along the way.
In Lambdaman, the goal is to find a path that visits all locations on a grid. The twist is that scores are not based on the length of the path, but rather the length of the program that produces the path. Therefore, the task is about finding short programs that generate longer output.
I implemented a compiler for a Scheme-like language that translates fairly directly into the contest language. In fact, I reused some of the S-expression code from my 2014 Lambda man solution. My language has a little syntactic sugar:
For example, here is a solution to problem 6:
(let ((triple (lambda (x) (concat x x x))))
(concat "solve lambdaman6 "
(triple (triple (triple "RRRRRRRR")))))
Many of my solutions are random walks: a simple random number generator produces a sequence of random moves. I started with linear congruential generators and later switched to generating every non-zero value modulo a prime by repeated multiplication of a generator element. Over time I found various tricks to make the implementation shorter, including using smaller integers, extracting bits from the seed more efficiently, and terminating based on the value of the seed rather than a separate count.
For example, here is a solution for problem 5:
(let ((solve (lambda (solve seed)
(if (= seed 1)
"solve lambdaman5 "
(concat (solve solve (% (* seed 14) 8831))
(take 1 (drop (% seed 4) "UDLR")))))))
(solve solve 14))
It generates values modulo 8831 (the largest prime representable with two bytes) using 14 as a generator.
For the maze problems 11-15, I encode the horizontal and vertical walls of the maze in integers and navigate using the right hand rule:
(let* ((getbit (lambda (getbit bits a b)
(if (> b 0)
(getbit getbit (/ bits 0b100000000000000000000000000000000000000000000000000) a (- b 2))
(if (> a 0)
(getbit getbit (/ bits 2) (- a 1) 0)
(% bits 2)))))
(solve (lambda (solve n x y dirX dirY)
(if (= n 0)
""
(let* ((newX (+ x dirX))
(newY (+ y dirY)))
(if (= 0
(if (= 0 dirX)
(getbit getbit 0b<OMITTED>00 newX (+ y newY))
(getbit getbit 0b<OMITTED>00 newY (+ x newX))))
(solve solve n x y dirY (- dirX))
(concat (take 2 (drop (+ (+ (* dirY 3) dirX) 3) "UULLRRDD"))
(solve solve (- n 1) newX newY (- dirY) dirX))))))))
(concat "solve lambdaman11 " (solve solve 5000 14 14 0 1)))
At the time I had the best scores, but later someone apparently figured out how to solve the maze problems without encoding the maze. I was never able to make random walks work for problems that large, so I’m not sure how it was done.
For 3D, my hope was to take a similar approach and implement a language that compiles to 3D. Generated solutions would not be as compact as hand-coded solutions, but a compiler should make solving the harder problems more feasible. The time warp capability of sending new values to an earlier time seems very similar to implementing iteration via tail calls, so my intent was to implement tail recursive solutions and compile them to 3D. These plans did not entirely work out.
I first had to find a set of primitives that can be assembled into solutions. I decided that all of my programs would use exactly two time steps: one to perform calculations and one to send the values back via time warp. One motivation is to reduce the time dimension, improving scores. Another is that the time warp operator can beam values to arbitrary locations, avoiding the need to route values around in space. All of my primitives are five units high and arranged horizontally in a row.
Here is a primitive for a binary operator that computes X + Y:
. Y . X + . . . . ? @ ? . 1 .
X and Y may be numbers, inputs (A or B), or may be set by another primitive via time warp. They may also be given initial values which are later overwritten by time warp. Cells marked ? specify where to beam the result.
Outputs can only be sent to one location, so if an output is needed more than once it must be duplicated. Here is a primitive that creates three copies of its input X, and a truncated version that produces two copies:
. . < X > . . . . < X . ? @ ? v ? @ ? ? @ ? v . . 1 . . . 1 . . 1 . . . . . ? @ ? . . . . ? @ ? . . . 1 . . . . . . 1 .
Halting and submitting an answer is typically done conditionally. Below are primitives that halt and return Y if X is 0 or 1:
. 0 . . 1 . X = . X = . . . . . . . Y + . Y * . . S . . S .
I ran into a few issues turning primitives into complete solutions. One is timing. Ideally all paths leading to a tail call should take the same number of steps so that all inputs to the next iteration will be available at the same time. Otherwise, we may start computing the next iteration with some old values and some new values. In practice it didn’t seem to matter much in hand-coded examples, but it is hard to reason about. Fixing it requires inserting extra delay primitives, harming the score.
A more significant problem is conditionals. The equal and not equal operators don’t output anything when they evaluate to false. I was planning to use that to stop future computations along some branches, including stopping the sending of new values to a tail call. Unfortunately, you can’t send “no value” through a time warp. If no value is sent in some time step, the computation still proceeds with whatever value was last sent on an earlier time step. One option is to allow all computations to continue unconditionally, and only conditionally stop sending values on the final tail call step. Another is to somehow use the values 1 and 0 for true and false (instead of using “no value” for false), and use multiplication by 0 or 1 to select between values. For example, “if A then B else C” could become A * B + not_A * C.
Without a complete design for how to translate complex computations to primitives, I never implemented an advanced compiler. I ended up with something closer to an assembler, manually specifying the primitives to use and how to connect them. I was able to solve the first seven problems that way, typically using unconditional recursion and conditional halting.
For example, here is my solution for problem 6 (primality testing):
b.INIT("n", A);
b.SUB("n_2", "n", 1);
b.SPLIT3("n_3a", "n_3b", "n", "n_2");
b.HALT1("n_3a", 1);
b.REM("r", A, "n_3b");
b.HALT0("r", 0);
It initializes n to A, then repeatedly subtracts 1 from n and calculates r = A % n. If r is 0, it returns 0 (not prime). If n reaches 1, it returns 1 (prime). Timing is important, because when n is 1 r will be 0 and both halting conditions will be triggered. Because n is tested one time step before r, the correct answer is produced.
Here is the compiled program, with spacing for readability:
. 1 . . . < . > . . . 1 . . . . . 0 . A - . -6 @ 0 v 8 @ 0 . = . A % . . = . . . . . 1 . . . 1 . . . . . . . . . . -5 @ 3 . . -8 @ 3 . . 1 * . -2 @ 2 0 + . . 1 . . . . 1 . . . . S . . 1 . . S .
I moved on to other tasks, hoping to come back to 3D later, but I never had the time.
Efficiency was a fun set of reverse engineering puzzles. I solved all of them. I first converted each problem into a Haskell-like syntax, and then picked it apart by hand using a text editor to help with indentation and parenthesis matching.
One helpful technique was to recognize the Y combinator, which was a clue that a recursive function follows:
(\v0 -> ((\v1 -> (v0 (v1 v1))) (\v1 -> (v0 (v1 v1)))))
Another technique was to recognize math that was computing something familiar, e.g. Fibonacci numbers or Mersenne primes, and then search for a list of numbers on a web page rather than computing anything.
The only problems that I wrote code to solve were the SAT problems and the problems with constraints on which digits of a number can be equal (which I did not recognize as sudoku until I looked at some after-contest spoilers). I wrote a program to extract the relevant conditions from the input and find the solution via a simple search.
I worked on Spaceship last, starting about 10 hours before the end of the contest (and 7 hours before I went to sleep), so I only had time for a basic solution.
To search for paths, I use a data structure that represents the set of positions and velocities reachable from a given state after a specific number of moves. For each of the two coordinates (X and Y) separately, I store the lowest and highest positions reachable, and for each position in that range I store the lowest and highest velocities achievable when ending at that position. I update the data structure one time step at a time and check whether any target locations are within the range of reachable positions. To check the target locations, I use a simple spatial index that divides space into a 32 x 32 grid.
I implemented two greedy strategies to search for paths. In the first strategy, I repeatedly travel to whichever target location is reachable in the fewest steps. In the second strategy, I first find the closest unvisited location (by Manhattan distance) and then travel there. The second strategy produced better solutions in most cases.
I was not able to find solutions for problems 23 and 24 with my code as is. My data structures are not efficient for problems with a large range of coordinates. I found a solution for problem 25 that takes 1,071,663 moves, but it was rejected by the server for exceeding the 1 MB request size limit, despite being well within the 10,000,000-move limit. I considered writing a program to decode the solution from a base 9 or 10 integer, but it was late and I chose sleep instead.
This was a fun contest. It was very programming language focused—appropriate for ICFP. It is always interesting to see what the task will be, since it varies so much from year to year.
Thank you very much to the organizers for all the hard work and for a well-run contest!