ICFP Contest Retrospective
This past weekend was the 2010 ICFP programming contest. After a few years of just watching, I finally decided to get a team together to compete again. This blog post is a description of my experiences, and what I think can be taken out of the experience for the future.
This year’s task was to design efficient ways of producing fuel for automobiles. The description starts out giving an abstract description of a car engine. It then describes how various fuels act in the engine, and what the criteria are for a car to work with a fuel. Finally, it describes a production factory for building fuels. The task is essentially to build the smallest possible production factories to produce fuels that work in the various cars. To keep things more interesting, teams were allowed to design and submit their own cars, and then other teams were given points for designing fuels to power other teams cars. So in addition to searching for fuels for other cars, there was also a component of the task centered around designing cars for which you know an efficient way to produce fuel, but think that other teams may not be able to find it.
How did we do? Well, the scoring was all weekend long, and as of the time we quit, we were in the top 30 or so teams and had been all weekend. Scores shot way up toward the end, though, so I just checked this morning and our final position was less impressive. If you want to look us up, the team name is “focos.”
The Good
There were some really great aspects of this year’s ICFP programming contest.
Designing efficient factories was a challenging and fun task. These were described in terms of circuits built from a fixed (ternary, 2×2) logic gate. There were several pieces to this task: (a) experimentation to find out what the behavior of that logic gate was, (b) designing a technique for producing your own circuits that produce desired output, and (c) the ever-present quest to build smaller and smaller circuits to produce desired outputs.
The other main parts of the problem looked interesting as well. Since fuels essentially work by matrix multiplication, there was a task of finding non-negative matrices which, when composed in one order, always take input vectors to larger output vectors (for some definition of larger) than the same matrices composed in a different order. Then there was the other side: finding composition orders which were difficult to use to satisfy that criteria. Unfortunately, our team never quite reached these problems.
It has to count in the “good” column that the contest happened, the task got announced, things ran to completion. It’s a huge effort to produce an ICFP contest, and it’s wonderful that there are people out there willing to put in that kind of effort.
The Bad
It’s relatively easy to point to the server problems as something that could have been thought out better. As of the time my team gave up on Sunday, it was impossible to even submit new solutions. That said, I’m unconvinced that the problem was the server implementation. I’m sure that could have been better, but the root cause here is as someone suggested in the #icfp-contest IRC channel: the problem was essentially designed to encourage hundreds of people to execute a DDOS attack on the contest server. Contestants were rewarded with additional points for doing so. So the server problems go in the “bad” column, but are also completely understandable, given the task.
It was also deeply, deeply disappointing that the contest (even the non-lightning component) gave extra points to teams that submitted things early. There are remarkably few consistent rules for ICFP, but I’d always thought that one of the rules was that teams would be judged on what they submit by the deadline at noon GMT on Monday, not by what they did to get there. This was exactly the opposite. If I’d had the best possible solution to every car in the system at 11:50 am GMT on Monday, it would have counted for almost nothing. In this case, my team was not really planning on beginning seriously until Saturday (in U.S. time, so late Saturday in GMT); but after reading the problem description, we scrambled a bit to try to get some kind of an earlier effort in place. This led to a few miscommunications. Some team members missed the chance to be part of the circuit experimentation at all. Some got discouraged and did not come back for the rest of the weekend, and there were really only two of us – me and my brother – for most of the competition. I do wish that could have been avoided.
The Ugly
Ultimately, though, I’m guessing the thing that will stick in everyone’s mind is that this year’s ICFP contest was the one where ICFP was about incomplete task descriptions and guesswork. Unfortunately, I was a bit charitable in describing the task above. That’s what I very much wish that the task had looked like. Instead, there were a lot of extraneous things in there:
you guessed it, we won’t tell you more about the encoding here, so you just have to make some educated guesses, based on the error messages of the stream parser on our server.
…
You guessed it, we do not give the semantics of the gates here, and neither the syntax of circuits. Instead, we refer to an example…
and on the contest organizers’ blog
The circuit design, and the ternary coding, were really there just for the fun of obfuscation.
(My note: there was a huge difference between circuit design, which was an interesting problem, and ternary coding, which was arbitrary and capricious.) It’s difficult to understand why this year’s contest organizers felt the need to hide them behind a bunch of stuff that was: (a) not programming related at all, (b) very arbitrary, and (c) frankly, a bit petty.
By not programming related, I mean that I was unable to see any way to approach the obfuscation bits as a programming problem. Judging from conversation on IRC and with other people, I don’t think most people did. Instead, people spent hours and hours staring at various examples trying to make some sense of it. I did talk to one person that thought it was fun…. and dozens who found the weekend among the more unpleasant in recent memory. Our team finally gave up because we were sick of it. Here’s the blog of another team that did the same. I imagine we’re not the only ones.
By arbitrary, I mean that when we did make progress, it wasn’t because there was some underlying neat organization we discovered in a flash of intuition. It was because we discovered yet another of the ad hoc rules that were used for the encoding. Each one was ultimately uninteresting; just allowed us to get one step closer to understanding a few more streams.
By petty, (and yes, I realize it’s a loaded word, but I can’t help but think it’s appropriate here), I mean that it’s difficult to see the encoding as being anything other than outright hostility toward those participating in the contest. I’ve admired previous years’ ICFP problems for being elegant. They presented hard problems, but those problems were hard for deep reasons. Contest organizers have posed the problems, and then tried to be as helpful as they could in describing them clearly and getting people to the point where they can tackle the hard problems. This year was, to say the least, very different. We never even tried the core problems, because, like I think the great majority of other teams, we never figured out what ternary encodings were about.
I’m not sure if I’ll organize another ICFP team in future years. If I do, it’s my sincere hope that the tasks don’t turn out to be like this one.
Sententia cdsmithus 
As regards the ternary encoding: I was one of the rare people who really enjoyed puzzling through it, and in hopes that I can convince you that the encoding did have an underlying neat organization, I will present to you the schema I worked out for it, written in pseudo-ML-datatypes. Note that the representation of the tuple (‘a * ‘b) is just the representation of ‘a, concatenated with the representation of ‘b.
car = chamber list (* No, we don’t know how to represent ‘a list yet… *)
chamber = tank list * bool * tank list
tank = nat
bool = nat (* restricted to 0 or 1, with 0 being true *)
Now here’s where it starts to get weird:
nat = trit list
trit = 0 | 1 | 2
So a nat is just a list of trits. But how is a list encoded? And how do you convert such a list into a numeric value? Tackling the second question first,
value([]) = 0
value([0]) = 1
value([1]) = 2
value([2]) = 3
value([0,0]) = 4
value([0,1]) = 5
… and so on.
Now, on to how lists are encoded. I will call the encoding of list lengths “wnat” for “weird nat”, since that’s how it looked to me at first.
wnat = 0 | 1 | 22 * nat
Where the numeric value of the wnat is 0, or 1, or the nat plus 2.
And now we represent a list of N elements as the wnat N followed by the elements concatenated together:
‘a list = N : wnat . ‘a ^ N
in very rough made-up notation.
That together should be enough information to encode and decode cars, and to get a sense of why I, at least, think the encoding is actually pretty elegant.
Thanks for the detailed explanation. I now see that the reason we didn’t figure this out was that it never occured to us that list lengths were encoded differently from the rest of the numbers. So while we managed to decode what you call “wnat” fairly early, we then proceeded thinking this was the number format, and just got ourselves very confused for a day or so!
I second many of your observations. Like decoding the car/fuel descriptions was an uneccesary high hurdle, and the server ending up DDOSed was a forseeable consequence.
Previous years’ problems have had the characteristic that you could make some progress very easily, but doing well was very hard — the reward was linear with the effort you put in. I didn’t find that this year — the threshold for getting started was too high.
Congratulations anyway, you did far better than i did :-)
Could you please explain to me how one was supposed to find the fuel circuit for the first car (219) ?
Or is there somewhere an explanation ?
I found such a circuit with 34 gates at http://github.com/schani/icfp-2010
But there is no explanation.
I hope brute force was not the way …
If you want a circuit with 34 gates to produce the prefix, then yeah, brute force was going to have to be a big part of it. But if you just wanted *a* way to produce the prefix, then there are compositional ways to solve that problem.
First, you want to generalize the notion of a circuit from the contest’s “one input, one output”, to a more general “n inputs, n outputs”. Then you want a way to take two circuits, and combine them by wiring the outputs of one to the inputs of the other. Since forward and reverse wires act differently, the order of the circuits matters, too.
Once you have that, you just start building circuits that do interesting things. Out initial approach was something like this.
1. We decided, arbitrarily, to start out considering what we ended up calling “formally combinatorial” circuits: circuits with absolutely NO wires going backward. Furthermore, since there are no formally combinatorial circuits with only one input and output except for just a single wire, we considered those with two inputs and two outputs. Turns out the only possible circuits of this form (you can write a simple proof of this, left as an exercise for the reader) are obtained by taking a sequence of gates 1 through n, and wiring each gate directly to the next gate. So the only variation is in: (a) number of gates, and (b) whether the wires from gate i to gate i+1 are crossed (left to right, right to left) or straight through (left to left, right to right). So it’s relatively simple to write a search function that tries a bunch until you find one whose combinatorial logic function matches what you want.
2. We developed circuits “constant 0”, “constant 1”, and “constant 2”. These circuit take one input, but ignore it, and produce a constant “0”, “1”, or “2” on the output line. Just run the search function from step 1 to find circuits where either of the output lines is always the same. Then take the other output line and wire it back to one of the ignored inputs. The result is a circuit that ignores its one input line, and produces a constant output. We found circuits with 7 or 8 gates each.
3. We built a few more simple combinatorial circuits by wiring constant circuits to inputs of gates and just staring at the gate function to see what happens. Some examples include the “decrementor” (maps an input a to a-1, mod 3), the “dupper” (takes (a,b) to (a,a)), and so on. These can be built from gate functions, and one or two extra gates.
4. We set out to develop what we called the “switch” This is a circuit with three inputs and three outputs. If input #2 is 0, then output #0 is equal to input #0. If input #2 is 1, then output #0 is equal to input #1. The last two outputs are trash, and only there because all circuits have the same number of inputs and outputs. We also don’t care what it does when input #2 is 2; we’ll just arrange for that never to happen when we care about the result. Building this one was tricky, but an hour or so with pencil and paper solved the problem.
5. Once you have constant functions and a switch, outputting any string you want is easy. Proceed inductively as follows. If you don’t care what the output is, you just want a gate with one of the wires wired back to the input. (It’s important to use a gate here rather than just a sraight-through wire, so that when we use this inductively, the wire coming out can go backward.) Now, to prepend a digit to the output you want, build the circuit for the suffix (except for the first character, and then add the following: a constant circuit producing that digit, wired to input #0 of a switch; a constant circuit producing 1, wired *backward* to input #2 of the switch, and the whole suffix circuit, wired *backward* to input #1 of the switch. Connect the two trash outputs of the switch to the inputs of the two constant circuits just to get rid of them. Now you’ve got a circuit that outputs the string with that new digit at the beginning.
Once you’ve got this far, you can output any string you want. The resulting circuits are not neat and small, though; the one to output the prefix is maybe something like a couple thousand gates, I believe? So there’s plenty more work we did improving the result… but hopefully I’ve given a fully motivated description of a plausible initial attack on the problem.
Thank you for your answer !
I understand your explanation, it’s logical :-)
But i still don’t understand how to know that the desired prefix was 11021210112101221
Was it written somewhere ?
I miss something but i don’t know what it is
Thanks
This was in the task description. If you wrote a simulator for the circuit they gave, and ran it against the *other* input string they also gave, then the first 17 digits of output were the prefix you needed.
You have been linked from my writeup: http://tapani.homeftp.org/icfp2010/
Our team had the same sort of issues. This was my fourth time participating in the ICFP and fell well behind the other 3. We did the same thing as you and gave up, though we didn’t get as far. It took us one day to match the prefix, and another day to be able to build circuits for sequences, and we had so little idea about the sequence formats at the start of the third that it wasn’t worth continuing – even if we got anywhere we’d have no time to gain score. Pretty disappointed – I think this year’s organisers missed the point a bit. It’s not just that it’s a hard problem, it’s the nature of the problem and the continuous ability to improve solutions that matters.
I also second many of your thoughts.
Another bit of criticism: If you looked up the organizing team (http://www.htwk-leipzig.de/de/presse/veranstaltungen/event/details/icfp-programming-contest/, Prof. Dr. J. Waldmann) the main focus could be guessed pretty well…
What was really missing this year was the fun that made the previous ICFPCs so different.
Last words: They should have read this (http://www.cs.cmu.edu/~tom7/papers/tr-06-163.pdf ) especially 2.2 before.