ICFP Programming Contest coda

By the time scoreboard closed we had dropped to 24th place. Mostly the problem was that by Sunday most of us were pretty burnt out and didn't make that much additional progress. Still, I think we performed pretty respectably, and beat out more than ninety percent of the competition.

The contest was designed very differently than in previous years; I'm not sure if this was a good thing or not. As I mentioned previously, myself and others felt that it primarily encouraged hacking up throw-away code. Much credit goes to Luke and Peng for their work on our virtual machine: It appears to be one of the fastest around. I helped with a little bit of debugging of the virtual machine, but mostly I worked on trying to solve the ADVIS, BLNCE, and ADVNTR tasks.

The ADVIS task was essentially to develop a method of computing around the silly rewriting semantics they had chosen for "O'Cult". Most of the time I focused on trying to figure out a general method of compiling or transforming a more sensible language to O'Cult. In the end, I believe the general solution was approximately: use a continuation passing transform to ensure computation evaluates the way you'd like and use SKI combinators to write your continuations. It was apparently possible to do better by just attacking the problem directly, which is not surprising given that I was trying to develop a general solution so for the first part so I could use it to make writing the second part trivial. However, in the end I decided it was too much effort to write a tool to do all the work, so I mostly used some small bits of code to compute SKI encodings of λ-terms.

I also spent some time trying to figure out the "trick" behind the Balance programming language, which was essentially a very wacky 8-bit register machine. However, it is still not clear to me that there was any known methodology for solving the problem. The best I could figure out was to use brute force to find ways of synthesizing more sensible operations, and then build a little assembler on top of that. However, I did not have the time to try writing a program to do the brute force searching, so Brian wound up solving about half the problems by plenty of thinking and experimentation.

Peng worked out about the first half of the "adventure" game program, by writing a "robot" client in Haskell to find the appropriate parts and solve the constraints. After that though, came the extremely novel problem of having to reprogram the game's command processor to perform actions that would not be possible otherwise. I made some very good headway on this, but became fatally stuck on trying to figure out how to read a blueprint whose contents were block by the game's "Censory Engine". I spent just about all of Sunday afternoon trying everything I could think of to solve it, and Peng put in a bit of time too. I'm told by other contestants after the fact that I was actually on the correct track by trying to read the blueprint via indirection, but somehow we must have not gotten some detail quite correct and had abandoned that tactic too early.
It was certainly a nice distraction, and I look forward to seeing how they actually constructed their programs and solutions.


  1. Andrew said,

    July 26, 2006 @ 6:30 am

    I still don’t understand how the VM rules they posted result in this whole random list of crazy tasks people are talking about. I feel like I somehow didn’t find the real contest. The posted rules don’t correspond to any actual problem.

  2. Andrew said,

    July 26, 2006 @ 6:34 am

    Okay, you explain it below. Good. Kind of a shame that you don’t have any idea about what the contest is without participating in it.

  3. washburn said,

    July 26, 2006 @ 9:34 am

    Right. It was kind of annoying in some respects that the posted task didn’t really explain what the real problems were, but I think part of what made it fun was not necessarily knowing what other puzzles might remain to be solved.

RSS feed for comments on this post · TrackBack URI

Leave a Comment