The 2010 ICFP Programming Contest

Introduction

Last weekend several hundred programming teams all over the world participated in the 2010 ICFP Programming Contest. Among them, of course, the glorious team Funktion im Kopf der Mensch.

The task

This year’s task was multi-layered. There was a core problem, but to even get to the point where we could submit part of a solution to it, we had to first make our way through a couple of secondary tasks.

The core task

The primary task was to submit “cars” and “fuels” to the organizers’ submission server. “Cars” are data structures describing operations performed on vectors called “air”, parameterized by matrices, called “fuel”. The thing of importance here is that cars don’t necessarily work with any fuel. Points were awarded only for fuel. The less fuels submitted for a specific car by different teams, the more those few teams scored for their fuels. Between fuels submitted for the same car, the one that was “shortest” scored the most.

Encodings

Cars and fuels could not be submitted directly, however. Both had to be encoded as ternary strings, in an undisclosed format. What’s more, before we could submit a car we had to submit a fuel for an existing car first, and fuels had an additional encoding step added – fuel factories.

Fuel factories

To submit a ternary fuel string it had to be encoded as a “fuel factory” first. A fuel factory is a circuit of individual gates of identical function. Each gate has two inputs and two outputs, all of which have to be wired. The whole circuit has one input and one output. The gate function was not disclosed.

To make the task of figuring out how gates work possible, the submission server would accept circuits and give back the first 17 “trits” of the circuit’s output. By submitting an empty circuit, wiring the circuit input to the output directly, without any intervening gates, we learned the first 17 trits of the input. Next we let the server produce the output for all circuits containing one (wired) gate. Those four output strings were enough to determine the gate function by brute-forcing (trying all possible gate functions and seeing which ones fit). We assumed (correctly) that the gates have no state.

The key

Another roadblock on the way to submitting fuels was that the fuel circuit had to produce a string that contained not only the encoded fuel but a 17 trit prefix – the “key” – before it. In order to gain the rights to submit a car we first had to produce a circuit that output this prefix. We brute-forced this circuit as well, trying all combinations of gates until we found one that generated the key. The shortest ones have 6 gates.

Now that we could submit cars as well as fuels, we had two problems to work on in parallel: How are cars and fuels encoded, and how do we produce a circuit that generates a given, arbitrarily long, ternary string?

Cars

We knew from the task description that cars were encoded as a combination of lists, tuples, and natural numbers. Discovering the actual encoding was aided not only by the availability of one sample car and several cars already submitted by other teams, but also by the contest organizers’ server, which gave helpful error messages for incorrectly encoded cars.

Here are a few examples of numbers and lists of numbers. Note that the encoding assumes that the type of the encoded object is known, i.e., the encoding of a particular list and some number might be the same, but since it is known which one of the two types is expected, that is not a problem.

Thing	Encoding
0	0
1	10
2	11
3	12
4	22000
7	22010
13	2210000
()	0
(1)	110
(1 2)	2201011
(1 2 3)	2210101112

Generator circuits

We had several ideas for how to generate circuits to produce arbitrary ternary strings. The one we settled on was to reverse-chain together a sequence of adding sub-circuits. Consider this circuit:

One thing I haven’t mentioned about circuits yet is that transfer along forward wires is instantaneous, but is delayed by one step along backward wires. In the first step, all backward wires carry the value 0. What that means for this circuit is that in the first step, the one-adder gets an input of 0 and produces 1, which is the first step’s circuit output. Also, the two-adder produces a 2, but its delivery to the one-adder is delayed until the second step, at which point the one-adder produces a 0 (because 1+2 is 0 modulo 3). The output for the third step already depends on the circuit input from the first step. This circuit, then, will, no matter what the input, always produce the two trits 10 in its first two steps. It is easy to see how to extend this pattern to produce an arbitrary string, given only the three adders as building blocks.

Of course we didn’t have the three adders starting out, but it was not too hard to brute-force them, like we did for the key generator. In fact, we even went so far as to brute-force circuits that combined up to three of those adders, reverse-chained together, to make our circuits shorter. Our adders also had a delay built-in, which made the last sub-circuit superfluous.

Fuel encoding

At this point we could use the server’s submission system to figure out the ternary encoding of fuels, which turned out to be quite simple – a list of lists of lists of numbers. With that done, we could concentrate on the actual task of the contest, namely the production of cars and fuel.

Producing fuels

The only way to score points was to produce fuels, either for our own cars, or for the cars of others, which we could download. As it turned out, a sizable proportion of the cars other teams submitted worked with one out of a handful of very basic fuels, so we wrote scripts that automatically tried to submit those fuels for any new cars that showed up.

We had two strategies for solving cars that didn’t give in so easily, both of which were rather unsophisticated and give away our complete lack of any deeper understanding of the problem.

The first approach, which I worked on, was to employ a genetic algorithm. The second was to translate the constraints a car placed on a fuel into a series of inequalities and feed them into Mathematica, hoping it would spit out a solution. Both approaches yielded a number of matching fuels.

Producing cars

My approach to producing cars was the same as for producing fuel – a genetic algorithm. We have a running joke in our team: For every problem that comes up I first suggest a genetic algorithm, even if it’s completely unsuited. This year was the first time a genetic algorithm was actually a somewhat feasible approach. The problem with producing a car this way is the fitness function. We had the idea of generating a random pool of fuels and then scoring cars so that they came out on top if they matched exactly one of those fuels, hoping that would make finding a matching fuel harder. The cars produced with this approach were solved by about 20 to 25 other teams.

Another approach, which I was not involved with and therefore cannot describe in any detail, was more successful: Only 5 or 6 teams solved those cars, so we ended up not using the genetically-produced cars much – there was a limit of 72 cars per team.

The result

We finished the contest in 23rd place. Around 210 teams ended up with a non-zero score, with the total number of participating teams probably considerably higher.

Contest organization

This contest was organized quite well, more so in contrast to last year’s debacle. The biggest organizational issue was the submission server, which was down often, as a result of being hammered by hundreds of teams, most of which probably used scripts to automatically download cars and submit fuels. In fact, for the first few hours of the contest, the server was completely unresponsive.

The organizers tried to remedy the situation with a variety of approaches, at one point limiting the length of submitted cars to something ridiculously low – around 100 trits if memory serves me right.

Still, I do not think that we were significantly held back by these problems, at least not more so than all the other teams.

Suggestions to future organizers

I’ve been thinking a bit about what I liked and didn’t like about the ICFP contest tasks over the past 10 or so years. Here are a few wishes to the organizers of future contests:

Visual

I found that having a problem that can be visualized makes it much more enjoyable to work on. The best example for this is probably 2004’s contest, where we had to write software for ants’ brains that had to work together to search for and gather food and to defend against attackers. Watching those ants move about and improve with each version of the code was a joy.

Despite all the other issues, I did like this aspect about last year’s task, as well.

Programming

The task should really be a programming task at heart. The contest is, after all, a Programming contest. This year’s task, after you stripped all the intentional obscurity, was a mathematical problem. I’m not saying that mathematical problems aren’t nice or interesting. Neither am I saying that there shouldn’t be any math involved in the contest, but don’t make the core problem a mathematical one.

No obscurity

It seems that all the obscure bits that were put into this year’s task had the purpose of disguising the fact that, as already mentioned, the core task was not first and foremost a programming one. Please don’t do this in the future! Give us a task where all the non-essentials have been stripped, where the hard and interesting part is actually the task, not all the stuff you have to go through to finally get to it, discovering that it wasn’t all it was cracked up to be.

Last year’s task also had a bit of completely unmotivated obscurity – the format of their VM instructions was slightly different depending on whether the instruction address was odd or even. Why, oh why?

Self-containment

The more we have to rely on the contest organizers’ servers to go about our task, it seems, the more problems crop up. Last year was a total failure due to a bug in the submission system, and this year the server was down or at least very hard to reach for considerable stretches of time. Please give us something self-contained again! If you must have some interaction, make is as simple as possible. The submission system for the 2006 contest, for example, only required sending a short hash for each solved sub-problem, and it worked very well.

Don’t show off

You’re smart, we know, but that’s not what the contest is about. The contest is about how smart we are, so please refrain from making the task a monument to your intellect, as was the case in 2007.

Clojure

After our disillusionment with OCaml we had been looking for a language to replace it with as our first choice. To my surprise and joy we managed to settle on Clojure, which turned out to work quite well for us.

We stumbled across some rough edges, most of them having their roots in the integration of Clojure with the JVM, but they posed no significant obstacles, and will most likely be ironed out soon. The biggest problem with Clojure right now, and this is generally acknowledged in the community, is the lack of its error reporting, which can make finding bugs quite an ordeal sometimes, until one accommodates, at which point it is still at best bearable.

On the positive side most of us found working in Clojure fun and, after some learning period, quite productive. Having an interactive environment like Emacs/SLIME certainly accelerates not only the learning process, but development in general.

Clojure’s dynamic nature allowed us to do stuff we hardly would have considered with, say, OCaml. A few weeks before the contest I put together a simple job distribution service which allowed us to interactively distribute several workloads over a number of computing nodes with relative ease.

The dynamicism does come at a price, though: Like many Lisps, Clojure’s performance model is non-intuitive. It is not clear, at least without considerable experience, which operations, under which circumstances, are cheap and which are expensive, the gulf between which can be vast. As a result, we have resorted to implementing a few critical pieces of code in Java, which, to be fair, was quick, easy, and gave us efficient code.

I am looking forward to using Clojure more in the future.

The Code

All the code we wrote for this year’s contest is available on GitHub. If you need any assistance with it, please email me.