I once again participated in the ICFP programming contest. This year I ranked 25th, which is one of my better performances.
One of the first tasks was dealing with a two trit input / two trit output logic gate where a trit is like a bit, but can be one of three values: 0, 1, or 2. There was a server where you could upload circuits designs built from these gates. Each output lead could be only hooked to exactly one input lead. There was one input lead for the circuit and out output lead which you could read values. There were also "backward" links in the circuit that would delay the signal by one clock cycle. The problem was to figure out what the gate does. After uploading your circuit you can see the output, of some unknown input stream.
To figure this out I first uploaded a circuit with one gate and observed its output. Then I hooked another gate up to that gate. This allowed be to observe the output of a known input and start deducing the logic table for the gate. Eventually enough testing of this sort reveals the entire logic table for the gate (especially by (correctly) assuming the initial value of the backward links are 0). There are only 18 unknowns to fill out. Apparently the circuit outputs (L-R,2-L*R) where L and R are the input values (all computations are modulo 3), but I didn’t realize this at the time.
The next step was to build a circuit that outputs a given key string. To begin I built three basic circuits. The +0, or identity circuit which passes the input to its output, the +1 circuit which adds 1 (mod 3) to its input, and the +2 circuit which, you guessed it, adds 2 (mod 3) to its output. At first I defined the +2 circuit as two successive +1 circuits, but because more points will be scored later with smaller circuits I eventually made a specialized +2 circuit.
To output the key string I backchained a series of these basic circuits together. Each backwards link delays the output by one, so with enough back links I can delay the meaningless input long enough to output by key string (or any string at all). At the beginning of my back chain I put the +n0 circuit where n0 is the first digit I want to output. The input of the backlink to this first circuit is 0, so I first output n0. The second circuit in my chain is +(n1-n0). On the first clock pulse the backlink input to this circuit is 0, so it outputs n1-n0 which is feed back to the first circuit, but delayed by one cycle. On the second clock plus the first circuit takes this input and outputs n1 as desired. The successive circuits in my back chain are defined in a similar way.
This (plus some other small omitted tasks) took me about 10 or 12 hours to do. I believe I was the third person to submit a solution that generates the key string.
The next task was to decode a specification for a car engine that was encoded in some unknown trinary self-delimiting code. We are told that the code can encode arbitrary natural numbers, and tuples, and tuples of tuples, etc. We know a car engine consists of a series of chambers and each chamber consists of two pipes, and each pipe consists of a series of segments, and each segment is connected to one of up to 6 fuel tanks. Each chamber is either a main chamber or an auxiliary chamber.
To crack this code you can submit your own attempts at encoding cars as trinary strings and read the error messages. First up was to understand the code for natural numbers. After a few trials I eventually got error messages about large numbered fuel tanks being not properly connected. Things like "… tank number 74 …". This means somewhere I have a 74 encoded in my string. By fiddling with the trits, I eventually gained some control over this tank number. For example, I saw that the substring "2210010" encoded the number 16, while "2210011" encoded the number 17. In fact, here the last three digits are part of a standard(ish) trinary number system, so "2210222" is the number 39. Eventually I found to get one more than this the prefix needs to change. The string "22110000" represents the number 40, and here the last 4 digits follow a standard trinary encoding. With more fiddling I found the smaller numbers are represented without a "22" prefix. "0" represents 0, "10" represents 1, "11" represents 2, and "12" represents 3. Finally we get the "22" prefix with the number 4, which is represented by "22000" Here the last 2 digits follow a standard trinary encoding.
I noticed that the after the "22" there was an code that represented the number of trinary digits that would follow. So "22" followed by "0" is followed by 2 trinary digits. "22" followed by "10" is followed by 3 trinary digits. "22" followed by "11" is followed by 4 trinary digits. And, not surprisingly, I found that "22" followed by "12" is followed by 5 trinary digits. The big break through is that "22" followed by "22000" is followed by 6 trinary digits! So the string following the "22" is a encoding of a number that represents the number of digits less 2.
With numbers out of the way, it was time to tackle tuples. They were encoded in a similar way "2210" is followed by a tuple of 3 things (such as numbers). "220" is followed by a tuple of 2 things. "1" is followed by a singleton and "0" is the empty tuple. Surprisingly I never make the connection between numbers and tuples that was pointed out to me after the contest. The numbers are encoded as tuples of digits!
I had the encoding figured out by about 14 hours into the contest or so, and I went to bed.
The final part of contest was to build cars and fuel cars. To fuel a car required building a matrix for each tank (of dimension of one’s choosing). A pipe multiplies together all the matrices from the fuel tanks it is hooked up to. A chamber runs when the top pipe’s matrix output is greater than to the bottom pipes output at every coefficient. Main chambers also require the top-left matrix entry of the top pipe’s output to be strictly greater than the bottom pipe’s corresponding entry. I never got around to building my own cars since I couldn’t decide on a good way to design cars that were hard to fuel.
This left me with the task of fueling cars, which I found very difficult. Eventually I designed a very simple program that checked if there was a subset of tanks that always occurred in greater numbers in the top pipes then in the bottom pipes. In this case there was a simple solution of assigning the matrix [[2]] to these tanks and [[1]] to the other tanks. This solved a disturbingly large number of the user submitted cars.
The other trivial solution I had was to try all 2×2 matrices of 0s and 1s. (for technical reasons that I glossed over, the top-left entry of a matrix always had to be at least 1, which simplifies this search). I also tried all 3×3 matrices for cars with no more than 3 tanks. This was slow, but did solve a number of cars as well.
I solved a few other cars by hand, but that is all the innovation I had.
The real challenge was keeping up with the sumbitted cars! Each team could submit up to 72 cars, and soon the submissions where getting out of hand. Uploading by hand because tedious. I lost track of which cars I had solved and which cars I hadn’t. I needed to bring some order and automation to this process.
One problem was that I could only download car specifications while logged in. So now was finally the time to learn to use HTTP 4000’s cookie support. Actually, it was so easy to use, there isn’t really anything to say about it. I would log in by hand and copy my cookie into my program that downloaded all cars.
To ease uploading I learned to use xclip. My solver would automatically put the solution into my copy/paste buffer, making pasting into the web form a snap. This didn’t last too long, as it was still too tedious. Soon I switched to using HTTP 4000’s form support. The form support is experimental, undocumented, but is pretty trivial and does work. Now my solver could upload solutions directly to the server.
I really enjoyed the contest, but that is probably because I did so well. The ICFP contests are often more like puzzle contests that involve programming than programming contests. But I really like these sorts of puzzle contests, so I hope they keep this sort of style.