Egér a Marson - ICFP contest 2010

We participated in the ICFP contest (which is my favourite programming contest by far) this year again, the fourth time. This time it was a team of two, H and B, though in practice it was more like 1.5 persons. We ended up at the 14th place, which is not quite bad, given the circumstances. Haskell was the primary language, with upload/download scripts written in Python.

One can read many opinions on the internet (for example, at reddit) saying that this year's contest was quite bad, not worth to spend time on it, etc. While I agree with many of the objections, and I prefer the problems given in 2008 and 2009, I don't think the situations was as bad as some people write. Especially that many of these people really liked the 2006 contest, which seems to me was even more puzzle driven (we participated first in 2007, but I started to solve the 2006 problems once).

About the issues:

• the obfuscation was a bit too much. It was not easy to figure out everything, and it took a long time, leaving not much for the "real" problem.
• the real problem was an unsolved mathematical problem. Giving an unsolved problem for a weekend project is not a good idea. For example, I had no idea how to approach it (even though I'm a mathematician by training), neither the time to work on it, given all the puzzles necessary to reach there.
• the contest favoured bigger teams, as there were many more-or-less independent aspects of the task. For example, the only top-5 team I know about at the moment was a big team. Last year, a one-person team won; I'm willing to bet that this year's winner team will be a larger one.
• the scoring favoured early submissions. Getting through the puzzles fast was more-or-less a question of luck. It took us 2 days out of the 3 figuring out everything (though we got some points earlier, since there were many cars with trivial solutions; even though I didn't understood what my submissions meant :). Also, for example, about 6 hours before the end I implemented a fuel encoding which halved the size of all our submissions; but this didn't mean much that late.
• Server problems. Sunday afternoon the server was basically in non-working state for many hours.
• the scripting part was a bit too real-world, with HTML forms and POST requests and session cookies and parsing the resulting HTML and reversing the HTML escaping and whatnot. I mean, since the time was limited, and there were many other obstructions, this could be just a bit friendlier. I ended up pasting session cookies into the code by hand (even though B implemented an automatic login/logout framework, the server was just dead that time, so I opted to not to send more requests than strictly necessary).

About the subproblems:

• The circuit. The circuit format was rather easy to guess, and the circuit design had some nice Arrow-ish and/or FRP-ish feeling. Even though I still don't quite understand arrows. I flirted a bit with the idea of understanding them during the contest, but then implemented a more traditional "tying-the-knot" framework for composing circuits (which we didn't really took advantage of). I too implemented a graphviz visualizer, but then we found it's much easier to use pen and paper to understand what's going on. The semantics of "backward" / "forward" was the trivial one, but as others, I was driven by elegance, and at first I was sure that the order of the nodes does not matter. Designing efficient circuits is probably an interesting problem in itself, though we did the most straightforward thing, and simply encoded any stream of N trits with 3N gates (it is not hard to produce three 3-gate circuits which prepend 0, 1 or 2 to the input stream), and later on, with about 3N/2 gates, which is a trickier variation of the first one (see below).
• The ternary encoding. With hindsight, it's rather nice, though having two different encodings for natural numbers is a bit excess. It was only Sunday afternoon I managed to completely understand the encoding of both cars and fuels.
• Designing cars and solving cars. We had no real ideas (or time to work on) here, so I just employed the trusty Random(tm) method, which was surprisingly effective: To solve cars, I just generated lots of random 0-1 matrices (later also matrices with elements from the set {1,2,3}), starting from 1x1 and continuing with 2x2 and 3x3 (experience showed that it is meaningless to try larger random matrices). This worked in about half of the cases, maybe a bit more. We solved about 2100 cars this way. To design cars, I employed a similar strategy.

All in all, the contest was fun, even though it was often quite frustrating, for different reasons. I learned quite a lot from the previous contests; this year's personal take-home message seems to be "understand arrows at last", but I still have to work on that :)

Some details

The ternary encoding can be described as follows (with Haskell-inspired pseudocode):

Stream 
  = List Stream 
  | (Stream , Stream)
  | Nat2

List Stream = (n::Nat1) : Stream^n

(Stream , Stream) = (x::Stream) : (y::Stream)

Nat1 
  = 0 
  | 1 
  | 22 : Nat2
  
Nat2 = (k::Nat1) : Digit^k

Digit = 0 | 1 | 2

Bool = {0,1} :: Nat2

Car  = List (List Nat2 , Bool , List Nat2)
Fuel = List (List (List Nat2))

Maybe it is not the most elegant description out there, but still. The following table may help understanding it:

n	Nat1	Nat2
0	0	0
1	1	1|0
2	22|0|	1|1
3	22|1|0	1|2
4	22|1|1	220|00
5	22|1|2	220|01
6	22|220|00	220|02
7	22|220|01	220|10
8	22|220|02	220|11
9	22|220|10	220|12
10	22|220|11	220|20
11	22|220|12	220|21
12	22|220|20	220|22
13	22|220|21	2210|000
14	22|220|22	2210|001
15	22|2210|000	2210|002

The scheme for encoding any stream of N trits witd a circuit of approximately 3N/2 gates is also rather nice (and I believe that the bound 3N/2 is optimal for such a general scheme).