Archive for the ‘ICFP’ Category

ICFP 2008 Final

Friday, September 26th, 2008

Well, the final results are up. We were disqualified in the 10th of 11 rounds. Judging by the results (but not looking at the actual map they used, even though they link to it), this one tested whether or not people’s entries correctly tracked and dodged martians. Ours ignored them entirely, of course. Counting places from the top, we came in 29th. Not bad for our first try at a time-limited team contest where we had terrible organization. We’re all excited for next year and hope to do even better, whatever the task is.

ICFP Scoring

Friday, August 15th, 2008

So far we’ve passed the 8th round of testing, as listed on the official scoreboard. So far we’re tending to be in the middle-ish of the pack of entries that survived each round. I’m actually impressed at how well we’re doing. Certain kinds of maps would completely destroy us, given the way we find paths. We could never navigate a maze, for example, nor could we evade martians if they put them directly in our path.

Here’s to victory!

ICFP 2008 Postmortem (Belated)

Wednesday, July 30th, 2008

Drew, Dion and I participated in the ICFP contest this year. It’s a 72 hour programming contest with something interesting to do every year. This year’s project was based on steering a rover around on Mars.

Pregaming

On the couple of days before the contest, I set up a trac instance. Not actually what my “secret project” I was working on in prior posts. Drew and Dion also created some sort of thing that they thought might be useful based on some of the things in recent contests but we didn’t end up using at all.

Friday

We were all at work at 12:00 PM Pacific time, so we didn’t start working right away. None of us were completely swamped at work, so we did take a little look at the project. After work, we discussed things a bit more and then got together with our associated ladyfriends/wives and watched Hellboy 2 together and went to Bertucci’s. Over food, we divided up tasks a little bit and then went home.

We started working that night and shortly after midnight Drew checked in a basic framework and we all went to bed.

Saturday

Drew came over to my house the next morning and we started churning away at getting things rolling. The morning was mostly made up of parsing all the information we got from the server and some basic data structures.

In the afternoon we started doing the necessary math to determine obstacles in the way of the rover so that we could calculate a path to the goal that doesn’t involve running into anything.

Drew wrote a utility that displays the internal state of the map so that we could visually debug the pathfinding.

Sunday

It wasn’t until the next morning that I turned on our actual pathfinder. Unfortunately, once I started optimizing it a bit I got smashed my stack and wasted most of the day trying to track down where. Drew was gone for much of the day at a baptism and Dion was taking care of his son’s birthday party. When Drew got back he set me straight.

Before bed we switched the GUI off as the program needed to be able to run without X.

Monday

The next morning we actually started trying to get the program to run in their environment. It turns out that we were using QT 4 but they only had QT 3. We submitted around noon (Eastern).

Wrapup

Our program did more or less work. It certainly won’t win, but I expect that we’ll not come in last, either. The pathfinder is fairly braindead. It does a local greedy search to find the path and then tries to smooth it out afterwords. Any number of simple traps could get it stuck. I did make sure that it just stops if the path it’s generating gets too long so it won’t crash. We also completely ignore all martians chasing the rover, so I’m sure that some maps they use to test us will catch us on that.

If I hadn’t gotten stuck and if we’d had more man-hours over the weekend we probably could have stepped up to a better pathfinding algorithm.