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.”
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.
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.
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.