ICFP Contest 2010

International Car and Fuel Production

This year's contest was under the theme of car and fuel production. The main goal of the contestents is to produce fuels using the most cost-efficient production method for as many cars as possible. For every car for which you can produce fuel, you get points every hour, the better your production facility the more points you get. The participants were also allowed to produce upto 72 own cars for which they also supply fuel.

The earlier you submit a new production method the longer you get points for it, but there were also taxes, so that the teams that cought up later still had a chance to win.

What the contest really was about is to find ranking functions for proving termination of string rewrite systems. A car is a string rewrite system and a fuel a corresponding ranking function. Of course, this was only explained after the contest was over.

Our team consisting mainly of two people, was quite successful, finishing on sixth place with almost half the problems solved.

Posting and Solving Problems

An interesting twist in this years contest was that every participant could post new problems, provided he had a solution for them. This gave a bit of dynamics to the contest. You could check regularly for more simple problems that you can solve. On the other hand you had to find a way to produce non-trivial problems with solutions.

While the idea is great, this lead to some drawbacks. Many of the posted problems were trivial to solve and to keep up your score you had to react fast. This problem got worse as the contest came to its end, because more and more teams managed to break the initial barrier and were allowed to post their own cars. Those teams did not even try to post serious problems. In the last hour of the contest over 400 new cars were posted and in the end there were 3784 cars. More than once during the contest the server was overloaded and the organizers had to find a way to reduce load.

In retrospect, it would have been better to limit the number of cars to ten per team (the limit was 72), and to limit the complexity of the cars. In between the server had a limit of 100 trits per car, which made producing challenging cars very difficult. The median of the car length was about 600 trits and the longest car had 22889 trits (which was not very difficult to solve).

Producing fuels

I think our success was largely due to our efficient way to produce fuel, which gave us top points for most of the problems we solved. In the contest, a fuel was a set of matrices encoded as ternary string. To make it more difficult for the participants, it was not possible to give this string directly, but you had to give a circuit that produced the string. The size of the circuit should be as small as possible. To make things even more difficult, most of the specifications were not given, but you had to derive them from the error messages you get from the server.

A circuit consists of gates using two input and two outputs. Every input must be connected to exactly one output. Every wire transports a digit 0, 1, or 2. There is an external gate with one output, feeding an unknown string of digits, and one input, where you need to send the encoding of the fuel with a fixed prefix. On each clock cycle the external gate produces first an input, then the gates are activated in their natural order, reading inputs and producing outputs. Finally, the value fed to the external gate is taken as trit for the fuel. If a wire goes from a gate with a higher number to a gate with a smaller number the value produced is only read on the next cycle. On the first cycle a 0 is read (which was not documented, but we guessed correctly).

We quickly derived the gate function by sending small circuits to the server, analysing the outputs and simulating them by hand. I do not go into the details of the reverse engineering process. Analysing the table revealed:

out-L = in-L + 2*in-R  mod 3,
out-R = in-L * in-R + 2 mod 3.

The next obstacle was to generate the circuit. We found an efficient way to produce for an encoded fuel a circuit that is only a few gates larger than the length of the fuel sequence. The basic idea is the following. The problem we solve is to find a circuit that takes a known input starting with a 2 and produces a certain output of length n. We split this problem into the simpler problem for length n-1 by adding a simple circuit that takes a 2 from the left and a 0 from the right and produces a sequence starting with a certain trit (there is one such circuit for every start value). Then we compute the input needed for this circuit to produce the correct result. The following diagram explains this.

The server input gets mangled by the first dummy register into the sequence 22022... starting with 2. We want to find a circuit that produces 11021.... We therefore start with the 1-trit circuit, that produces initially a 1. Then we can compute the input that the 1-trit circuit requires on the right-hand-side to produce 1021... in the next steps, which is 0010.... When this input is given the first circuit produces 2221.... We next use the 0-trit circuit to produce a sequence starting with a 0, etc.

Our algorithm requires to know the server input. We worked around this by delaying the server input (feeding it backwards through many gates), which increased the circuit complexity. Additionally we wrote a small script to guess the server input (trit by trit) by checking a specially crafted fuel, which gives clear error messages when the last trits were corrupted. In the end we had about 800 trits of server input, which is enough for most problems. After the contest, I learned that there is a simple circuit consisting of five gates that converts any input to a stream of 2, which would also solve this problem.

You can download a very minimalistic factory synthesizer written in ocaml. Give it the output sequence as argument and it will print the circuit to stdout. The generated circuit has exactly six gates plus one for each output trit.

Some teams used brute-force to generate circuits. While this will give shorter circuits (e.g. seven gates for a 22 trit trivial fuel), this method is not usable for larger systems. After the contest, I implemented a mixed approach of brute-forcing and the above method for circuit generation. This allows shrinking the circuit by 15 or more gates, but each additional gate that is removed increases the computation time by a factor of three.