ICFP Programming Contest 2010

As has become customary for me, I participated in the annual ICFP programming contest this weekend. I participated as a lone coder this time with the team name "rmathew". The contest this year was irritating and frustrating, not to mention quite humbling (as usual).

The task description was obtuse and it took me at least a couple of readings to even understand what we were supposed to do. Even after understanding it, I didn't feel motivated to solve it as it seemed to have been devised simply to frustrate people. I still went ahead with it as I had already set aside some time for this year's contest.

The overall task was to create cars and fuel for such cars. You had to create cars for which it would be difficult for others to supply fuel and you had to supply fuel to as many other cars as possible. The engines of the cars were provided as streams of "trits" (ternary, or base-3, digits) for which you had to figure out the encoding. Fuel had to be created using circuits that used ternary logic gates for which you had to figure out the encoding of the circuits, the logic used by the gates, the input stream provided to the circuits by the server and the validating key in the output stream without which your circuits were rejected.

The worst part was that you had figure all this out by using educated guesses and by looking at the error messages spewed by the server hosted by the organisers. Needless to say, the server didn't stay up for long and had issues throughout the contest.

The gates took two input trits (left and right) and produced two output trits (left and right). My guess about the format used for encoding the circuits turned out to be right and after a couple of trials it became apparent that there was only one type of gate. I could not figure out a programmatic way of determining the logic used by the gates, so I used pen and paper with a few simple circuits to figure out the logic using the error messages from the server as a guide. The truth-tables (left-input varies by rows, right-input by columns) turned out to be:

Which boils down to:

    LO = (LI - RI + 3) mod 3
    RO = (LI * RI + 2) mod 3

The nice structure of the left-output table also allows you to then determine the input stream used by the server. Using this information, I coded a simple circuit simulator that I then used on the key circuit given in the task description to find out the key sequence desired in every output stream.

To proceed further, I needed to figure out how to create a circuit that can convert a given input stream into a given output stream. This is where I hit a dead-end - I just could not work out how to approach this problem without using brute force and that seemed quite prohibitive considering the possibilities. To distract myself I created a simple circuit visualisation tool that converted a description like this:

    0L:
    X3R0#1R2L,
    1L0L0#1L3L,
    0R2R0#3R2R,
    1R2L0#X0R:
    3L

into a file that could then be converted by Graphviz into this image:

Coming back to the circuit-construction problem, I noticed that because of the structure of the left-output truth-table, you can work out the right-input and right-output streams for a gate for fixed left-input and left-output (LILO) streams. I toyed with the idea of stitching such "Lilo" nodes together to construct a solution using a solver programme named "Stitch" (Ha!), but that didn't get me anywhere.

I then decided to give up on this year's contest. I hope next year's contest is better. (I still fondly remember the contests for 2006 and 2007.)

If you're interested, you can see the source-code on Bitbucket.

Tweet