Reflections on the ICFP Programming Contest 2008
In 2007, Tristan and I decided to enter the ICFP Programming Contest. We turned up at the right time, downloaded and read the spec, and promptly gave up. We instead spent the weekend hacking on a game we were writing.
In 2008, Tristan and I decided to enter the . This time, things would be different. We did some practise! We spent 12 hours straight on the 2005 contest (Cops and Robbers) and then did a 24 hour (with sleep) session on the 2004 contest (Ants). We were pretty pleased with how we did on those and went into the 2008 contest with a certain amount of confidence.
To cut a very long story short, we will have done badly, very badly. The results aren't out yet, but we know which way this will have gone. However, it was immensely fun, and we will be back next year to try and avoid coming last again!
So, being in the UK, the contest started at 8pm on the Friday. Our plan was to get all the basic infrastructure up before we went to bed as it's pretty straightforward and you don't have to think too hard. We used the same basic state machine pattern that we'd developed for the Cops-and-robbers contest and used Lazy ByteString to read off the network socket lazily - I really do think this lazy input pattern is lovely, though I can see how it's a real PITA to deal with errors. But we ignored errors which turned out never to be an issue anyway. We got to bed at about 2am.
Saturday morning came and we both charged into the office, brimming with ideas. We spent about 4 hours discussing and arguing about what we should do. We both agreed that the only way to win would be to move fast, which means that our route planning would have to be excellent. And so that's all we focussed on. We wrote a lot of code (over 3000 lines of Haskell in 72 hours between the 2 of us) and the vast majority of that was on route finding. Eventually, we realised that what we'd forgotten to do was to think about how to move the robot.
You see, in both of the contests that we'd looked at previously, the setup was that you could pretty much move arbitrarily: if you told the robber to go somewhere, he would do so, no questions asked. Whereas this martian rover did not behave in the same way. It could be told to accelerate, brake, roll, turn left or right, but it wouldn't accept orders to go to a particular coordinate, and it can't even maintain a constant speed, other than not moving at all or moving as fast as possible. And we rather forgot to think about the consequences of this. So at the end, we were able to produce some nice routes, but the rover wasn't really very good at following them.
So we used a quad tree, which sort of worked, though it's not perfect. Quad trees and oct trees are fine for storing points, but not as great for storing areas, which were the boulders and craters. But I kind of mashed through that so it basically worked. We then took the quad tree and turned it into a graph. Now we didn't really discuss this, but I think we should have spent some time trying to work out the best way to do this, because without thinking about the consequences too much, we just too the vectors of the edges of the leaves of the quad tree to be the edges of the graph (actually, that's not quite true. Tris then added lots of other edges so that the nodes on the boundary of a quad tree leaf were almost fully connected within that leaf. Or something like that), which I'm not sure is the right thing to do. And then when we had a graph, we ran shortest path on it, with some extra heuristics.
Which sort of worked. Except that I wrote some very complex heuristics, which would try to find a path across a region even if there were boulders in the region. And that maths turned out to be very expensive (though I may have just been doing it wrong), which very quickly meant that as soon as the quad tree got bigish, there were so many paths to consider and so much maths to do, that the shortest path algorithms would take far too long to complete, we'd loose sync with the rover, and it would all end badly. So I hacked bits out to cut the maths down, the rover sort of gained an ability to drive, and it was all pretty much a disaster. Still goood honest fun!
So below you have a screenshot from our GUI. The left hand side shows the quad tree and the chosen path and the rover and its direction. The right hand side shows the graph which was used for the shortest path algorithm.
