Monday, June 29, 2009

icfp 2009 contest

Here's a quick technical writeup about our entry for this year's ICFP contest.

Our team of 4 is called "xor eax, eax". i.e. myself, Loftie Ellis, Pieter Holtzhausen and Albert Swart.

After a bit of discussion, Loftie and I set to work coding up the virtual machine specification in Python. We used the builtin array type to manage the bytecode, but later switched to numpy. Albert translated it to a C version, which Pieter hooked into Python code with ctypes. I wrote a simple GUI in opencv.

We encountered a few issues switching between our 32bit and 64bit machines. We had an 8x2GHz machine to our disposal, but ended up not really using it.

Pieter wrote the basic Hohnmann transfer code, which Loftie used to manually determine target orbits for the first 2 problem sets. I used Python structs to write the submissions file.

We finished it well within the lightning round time. In fact most of the work happened in the first 8 hours. At one stage we where fourth on the leader board. Unfortunately we spent too much time on the manual tweaking Saturday and was only able to do problem sets one, two and a single scenario of problem set 3 for the lightning round.

We decided to approach problem 4 as a series of jumps between different orbital radii. In other words: to reach a target we need to do a Hohnmann transfer to a radius that will cause the target and our ship to meet. We did not have enough sleep and energy to explore the optimal sequential order of the jumps in too much detail.

So Sunday I set to work on setting up scipy's optimization library to search for the optimal radius. We tended to primarily use the Golden section search. That worked well and converged in around 35 iterations on average.

Monday we didn't really do anything (except for playing a game of starcraft). The last update of the score board placed us at position 77. Since then we raised our score to around 2200, if I recall correctly, by primarily completing the remaining scenarios of problem 3.

(Edit: The final scores are in. We finished 70th out of 328 with a score of 2275.)

We should have spent less time manually tweaking behavior and rather try to find a more general solution. We also should have looked at the scenario's in more detail, since we later discovered them to be simpler than the assumptions we were working with. I think these two factors sucked more of our energy than we should have allowed it to.

I was hesitant when we began writing the VM in python, but it was surprisingly efficient. The C version was around 5x faster I would guess. Some of the other members were surprised by some python's scoping strangeness. It's interpreted nature allowed us a lot of experimentation, however. We used a local subversion repository, which worked out well.

All things considered it was a good competition. The only major upset was a re-release of the problem 4 binary, which invalidated a few hours of our work. I have never really read about astrodynamics before this contest and found it very interesting.

During the competition I continuously captured one image every minute from a webcam I mounted on the wall with sticky tape. Using mencoder I compiled it into a 25fps video. So each second in the video represents the passage of 25 minutes.

No comments: