John Fremlin's blog: ICFP Programming Contest 2009

The ICFP Programming Contest has finished. Our final score was over 4000, and we placed seventh overall, according to the final ranking at the ICFP.

The git repository for our team, dysfunkycom is on github. We actually managed to grab the satellites on the surface of the moon, but only sometimes, and after 2e6 seconds so it didn't count. The changes are destructive but fun on the moon branch.

Our main problem was that we had no experience working together on the same program and a lot of time was wasted because of it. However, Peter and I had both some experience working with other people before and we started to establish a technical rapport though it was only the second or third time we had met.

When we started at about 11am on Saturday Tokyo time, we arrived to a great email from Paul with a fantastic VM binary system. Seeing as this was some of the best code in our final system, it's a real shame that Paul was too busy with other things to give us more time and the three of us were left to do the rest of the problem.

I got the visualiser up in a few hours. Unfortunately, I got the sign of the enemy positions the wrong way round so that confused us a lot.

Peter fixed the skeleton up according to endianness and other details, and Peter and I debugged it and got it up and running about three hours after starting. Peter wrote the submissions system.

Jianshi got the problem 1 jumper out.

Then we got stuck it and took us ages to get to problem 2. We were all tired out.

Finally, I bullied Jianshi's jumper into the jump time working about half an hour before the lightning round deadline. We got a score from running the binary. I was very excited as we would have made a decent position on the leaderboard. But the submissions kept coming back as CRASHED. I had broken the submissions by not zeroing out the thrusts after thrusting.

We got pretty drunk after the lightning round, figured out the problem and sent out the new submissions a few hours after the deadline. This put us in seventh place if I remember rightly, and as we hadn't actually improved the spaceflight since half an hour before the deadline, I feel rather sick about it.

On Sunday I concentrated on building up a lot of infrastructure for letting us cache the exact positions of enemy satellites in the future, caching orbit VM compilation, and running speculative simulations.

Peter wrote a fantastic submission visualiser, so you can watch the actual submission binary in the visualiser, use (visualise-submission "file").

As the problem 1 binary actually rewarded you for wasting fuel I made an orbit jumper that would actually waste as much fuel as possible. You can see it with (visualise-scenario 1001 :controller 'problem-1-controller-superburn).

Peter built an awesome ellipse solver with his linear solver and then built a great ellipse jumper which we bullied into working well but we couldn't get problem 3 because we didn't have a chaser to adjust our positions to the enemy satellite.

In summary, this day was spent in reducing the technical debt and building stuff for problem 4.

Monday came round and I wrote out the chaser (using the real future position as calculated from the real VM) and new brute force time estimator for jumping to the next satellite, and Peter got the refuel system working and started bullying the code into working for problem 4. Jianshi tried to figure out how to get to the fuel station on the scenario with the reversed angular velocities. I tried to get us to the moon and managed it but not collecting the satellite on the surface of the moon, as I didn't realise it was so close to the surface.

The chaser was great for problem 3 where we needed to stick with a satellite but as the problem 4 only need to get within 1km of the satellite it was a waste of fuel, so I made a new touch chaser. About 6 hours before the end, I rewrote the brute jumper to bisect the jump time and optimize it to the best step. This let Peter's system get us most satellites quite reliably. I was so tired I nearly fell down stairs.

Then we had to move office which took about an hour, and Peter and especially Jianshi did fantastic work hand tuning the problem 4 scenarios for a good score.

I went on a mission to fix up the moon problem and after a bit of code bullying got the simulation and visualisation to recenter on the moon, and then saw that the target satellite was actually on it, explaining the crashes. In the end, I actually got to safely touch the satellite on the surface of the moon by orbiting a little above it and then grabbing it when it was close. But, unfortunately, the initial jump to get into lunar orbit was unreliable and even when it worked generally took more than 2e6 seconds so the score timelimit was up. Maybe this could have been improved, but I stupidly didn't realise the timelimit would be a problem. Basically, I massively screwed up the moon grabbing by not realising what the problems with it were until about half an hour before the submission deadline, so it was waste of time going for it at all.

In terms of improving:

— More planning and thought about the way we were going about solving the problem and spending a few hours to learn a little about orbital mechanics might have kept us out of some blind alleys and given us a much improved attack on problem 4.

— Some practice working together as a team would have made us massively more efficient. We duplicated effort and rarely got into the great state of collaboration where the work is discussed, understood, broken up and then the independently developed pieces of the solution all fall into place together.

— If we had got a good function for printing a textual description of the scenario state then maybe we would have caught the visualiser bugs and got out problem 2 faster, and also understood the moon issues more quickly. I think this would have been really helpful for the problem 4 system as well, as we could have described the state conveniently in our debug output.

— The visualiser was worth the time spent. But I designed it badly. I was initially wary of mixing up the visualiser with the simulator. I should have integrated the visualiser into the simulator more closely (perhaps via an unobtrusive function pointer called every few steps) so we could play problems as they were solved, not replaying traces after getting the output of the controller. That would have sped up our development cycle significantly.

— Having the submission checker was great and maybe we should have written it before. (Very much in hindsight perhaps.)

In conclusion, we got out reasonable submissions to all the problems so we did okay, especially as we didn't know anything about using our graphics library or orbital mechanics. Our approach was to brute force optimal wait times to do a Hohmann transfer to the exact target satellite position from a cached run of the simulator (this was usually suboptimal for the orbital transfer as it took a long time to wait for the jump and stabilising to a circular orbit was costly in fuel).

It was great fun, and many thanks to the organisers, to Starling Software for letting us use their office and to all the people on the Haskell team for sharing ideas, to MSI for the paid holiday, and finally to my great teammates.

Update 20090730 — just heard from the organisers that we made the top 10!

Update 20090905 — updated with our final position from Liyang Hu's photo of the team rankings from the ICFP.

Update 20090919 — described many of the different teams solutions.