John Fremlin's blog: ICFP Contest 2009 - debrief

I was part of a team which participated in the Twelfth ICFP Programming Contest. It was a really fun problem over three days. The winner, as chosen by the organisers, was Shinichiro Hamaji, and the winner on points was pepsiso (we came seventh on the final scoreboard).

We weren't expecting to do so well in this contest; it was my first year, and now I have become much more interested in it. We should have been more dedicated!

I was very interested in meeting shinh, the winner (also the Code Golf champion), as he is also living in Tokyo. In the end, it turned out that at least four of the top ten teams were in Tokyo (here is a list of many Japanese team blogs) and that shinh is well connected to them — he arranged a really stimulating meeting at a bar with representatives from many of the serious teams.

(The Ukraine was also well represented in the contest with at least two teams; there were also at least two teams from the US.)

Scoreboard first — pepsiso (including source code) had a nearly perfect solution for the problems; it was hardly possible to compare it with our sloppy efforts.

They hand-entered the thrusts for each solution with the help of a really good visualiser and the ability to save and restart the simulator state to try a bunch of ideas. The solutions from these guys is absolutely amazing; even more so as they achieved it by thinking about each thrust individually. They weren't at all restricted to Hohmann jumps, and could achieve a really beautiful energy-saving curve collecting all the debris in, more or less, one swoop. They quip that their solution demonstrates that the mind is superior to machine. :-)

Amazingly, this two person team (half of team kuma from last year) discovered that you could score points by touching the fuel station. The organisers' specification kept changing the number of satellites but by my reading, it does not suggest that touching the fuel station would be rewarded. As pepsiso demonstrate there is no need to refuel to collect all the debris satellites, so teams that did not spot this could be at a disadvantage.

San from team THIRTEEN disassembled the binary's scoring, which seems to confirm this idea. I was in touch with Professor Gill of the organising team before, but he has not replied to my email about it.

Scoreboard second (and second prize) — THIRTEEN (videos and source code in svn://hub.kharkov.ua/ICFPC2009 --username guest --password guest). This team from the Ukraine didn't come to the meeting obviously. I think I spoke to one of them on IRC after the competition. They had an awesome solution that would deliberately change the angular speed of the satellite to be the reverse of the target satellites for a faster pick up. Wish we had thought of that!

They were quite a large team and had people joining in through the contest.

They had excellent spaceflight not limited to Hohmann jumps, using a Lambert transfer in Java (first prototyped in Matlab). They developed quite a comprehensive solution to the traveling salesman satellite chasing at the end, but it was not robust enough to complete all sub-problems of the verification stage, and they had to use a second solving approach for one.

They tried many approaches to generating a fast VM and even developed a way to make a sort of readable disassembly of the binaries.

Beautiful spaceflight! Congratulations.

Scoreboard third — wiiphonies (no idea). Please comment if you know about this team.

Scoreboard fourth — Intercaml (including source code) were a relatively large team with four members, and a certain degree of team-name fraud — they used C++ and Java, not any kind of ML. Their solution was actually quite general and they were let down by an unfortunate bug which caused their satellite to crash into the moon in the validation stage (the contest organisers tested each of the top ten teams with a second problem 400x binary). Their development style was rather like ours with lots of copy paste and multiple strategies to solve each subproblem, but they were much faster than us and got many more points. If it weren't for this really unlucky bug they could have been well placed to take the prize.

Their spaceflight was limited just to waiting for and then making Hohmann jumps. They used complex numbers to represent points in the 2D physics, and only considered meeting the target debris at their perigees. They implemented the physics by themselves and used that for predicting where the targets would be, but ran the simulator itself to confirm the solution.

Their visualiser took the spaceflight logs from their main program and drew really pretty pictures. After the contest they even wrote an awesome JavaScript visualiser!

Scoreboard fifth (Judge's prize) — when i was 4 years old i was (censored) by a giant pig. Apparently, partly in Matlab with the usual C++ compiled VM. A team of engineers and interns from facebook.com.

Scoreboard sixth — Side Effects May Include... (no idea about this team). Please comment if you know about them!

Scoreboard seventh — dysfunkycom (including source code), us, the only top-ten team that didn't use C, Java or C++ at all? We bisected to find the optimal Hohmann wait time from actually running the simulator (which was compiled via Lisp to machine code).

Scoreboard eighth — Cult of the Bound Variable, team from CMU? Pretty regularly do very well in this contest.

Scoreboard ninth (first prize) — shinh's (including source code) winning solution was very instructive. He was working alone, and according to my impression, was very careful reading the rules. This was the sixth year he participated and consistently does very well.

He implemented the simulator according to the description of the physics in the ruleset and discovered (was first to discover?) a bug in the physics of the VM for problem 4. Of course, he also implemented a binary-to-C translator to run the VM fast.

We (well, actually, I) wasted a huge amount of time trying to grab the debris orbiting the moon; shinh wisely estimated the points that could be achieved for this and determined that it probably wasn't worth the effort. He also tidied up his code and did a lot of tests(!) to make sure it would be robust for the verification stage, hoping he would make the top ten.

His orbital transfers were done by simply waiting for the right time to make a Hohmann jump to catch debris and then some final fine-tuning to touch the satellite, instead of trying more complex spaceflight. He used a sort of simulated annealing with manually specified constants to find the wait time.

Instead of hand-tuning his solutions to 400x, he ripped out all the sneaky special casing and wrote a straightforward greedy algorithm with an extra condition that the spacecraft should not run out of fuel. It was a carefully thought-through and well polished solution, with, of course, the awful risk that by not hand-tuning and fiddling special cases it might not make the top ten! His effort seems to me (from the source code of the other entries I saw) to have been the least confused and the most disciplined — also probably the bravest, in terms of not compromising simplicity to get easy points. Congratulations!

Scoreboard tenth (lightning prize) — jabber.ru, a single programmer from the Ukraine. Also won the lightning prize last year.

Special mention for scoreboard twelfth — Mr Tanaka from the team Purely Functional Infrastructure also came along to the meeting (no source code, but a presentation in Japanese). There were also four(?) people on this tea. Their automatic solution was quite interesting: it would accelerate in the direction of travel harder than necessary for a Hohmann jump to catch the target satellite (see the videos).

I guess they were optimizing across more than one variable: both wait time and boost magnitude; we and most other teams just optimized the wait time. Unfortunately, they went back to the fuel station after catching each target satellite and this must have cost them a lot of points, as it was unnecessary and took a lot of fuel.

General remarks — All the successful teams I know about had a great visualiser, and generally a good textual description of the simulator state. They also had some way to run the physics simulator fast, often with multiple approaches to achieve this (their own physics implementation in addition to fast compiled VM, usually converting the binary to C, with caching). Using the hint from the warm-up problems to use Hohmann jumps resulted in suboptimal spaceflight but was easily sufficient for the top ten.

The most important thing was to sedulously read the specification, as many top teams muddled various details (for example, we thought for a while that we couldn't score on problem 4 without collecting all the debris). Reading specification was a good start, but as there were bugs in the implementation, you had to use your common sense as well.

Physics — People were very worried about errors building up from the discrete physics approximation: these errors were very small and using analytical solutions was generally fine. (Note, that we optimized the Hohmann time to the best integer step possible using the exact output of the binary, but still often finished the jump more than 1 km from the target so it was necessary to implement some fine tuning, i.e. chasing; these apparently contradictory findings can be reconciled by noting that 1 km was generally minuscule in proportion to the distance traveled in the jump, e.g. fifty thousand km.) The self-implemented physics taking the initial position and velocity from the binaries worked very well.

Surprises. — One and two person teams could be very successful: producing more code more quickly did not necessarily give any advantage; one had better spend time thinking about the right thing to do.

Many high-scoring teams did not increase their performance much in the last few hours; I wonder why? We imagined that other teams would also boost their scores a lot after the scoreboard froze.

Like real-world programming, the specification was wrong in a few details (for example, the moon gravity initially not affecting the controlled satellite). To get the top score, an intimidatingly complete understanding of the nuances was required.

Request. Most of the teams were non-native English speakers. I hope that next year the contest organisers will take this more explicitly into account and produce a less wordy specification.

Thanks to everybody who came to the meeting to share ideas, to everybody who released source code and videos, and especially to the organisers for setting up and running the contest (and for so quickly making bugfixed binaries)!

Update 20090921 — added links to team THIRTEEN's new English blog post; thanks Sanny!

Update 20090927 — corrected the idea that pepsiso were wrong to collect the fuel station. Of course, pepsiso were right. My apologies for ever doubting them, and thanks to San from team THIRTEEN for helping investigate the issue.

[If you have more info about these teams or other remarks about the comments, please comment below; I shall try to update this page.]