(Other accounts can be read at my friend's blog.)
I personally got hooked on doing the ICFP after reading about the previous competitions. It seemed like an enormous amount of fun - and I was not disappointed by the 2006 contest.
I got together two of my friends, both of whom I had gone to University of Chicago with. We decided to name the team "Pretend Robot Pants", a name that I have been using here and there after stealing it from an interview with the Brothers Chaps. Unfortunately, Jono had to work the first two days, so the beginning of the contest would have to be done mostly solo by myself and my other teammate. When they released the codex before the contest, I went nuts and tried to find every silly CBV reference they had put in there. There were some excellent references to Focault's Pendulum and Stephenson novels in there.
Finally, on the day of the contest, they released the task: build an emulator for this machine and run the codex. Simple enough? Not when you decide that the emulator should be written in Python. The unfortunate part, and the part that caused us to do as poorly as we did in the contest, was that we never realized exactly how fast the emulator had to be until it was too late. When we built the first version of it, and debugged it until it finally passed the tests, I happily let Python sit there and chomp away at running the codex. 15 minutes, then half an hour. That's way too long, I thought, and I thought that somehow our buggy code had gone into some infinite loop. So, I did the worst thing possible: I build a debugger.
The debugger worked quite nicely - it allowed me to step through the code, one instruction at a time, and even save and restore state. I had no idea that the intentionally huge "Sand tablet" programs we would be running would make this idea absolutely infeasible, and the nature of the contest make it pointless. The lesson I learned from this is that if you are entering a programming competition, you NEED to be confident that your code works. You waste too much time double-checking yourself. In a production environment, this is something you have to do. But if you're racing against the clock and 500 other teams, you need to make sure that you trust yourself.
Finally, I looked at the mailing list and noticed that people's codexes were running faster than ours. A LOT faster. So, I moved it into C. Finally, the secret codex popped out of the original codex. But it was still taking too long. Finally, I tracked down the source of the problem: we had previously assumed (this is a case of poor documentation, but we should have caught it) that we only needed to allow 32 spaces for memory storage. Turns out we needed 2^32. Unfortunately, in the previous code, the function that checked for free memory chunks simply iterated through a free list. This was fine when there were only 32 spaces. But now it was cycling through thousands of allocated spaces. Because of the rapid change, this problem went unnoticed until I finally did some profiling on the code. A linked list later, and we were up and running.
By this time, the contest was half-over.
We realized that we were never going to make it, but by this time Jono had time to devote to the contest, so we tried our hardest. We programmed our password "cracker" in roman-numeral-BASIC, and I ran through the adventure game garnering a few meager points, until I realized the game behind it.
This was an amazing contest. The game tested every facet of skill that a computer scientist should have: the emulator required streamlined C code to even start the game. The mini-games inside UMIX tested all the stuff you should know: the adventure game was an exercise that shows you the kind of things compilers have to deal with, there was a crazy rule rewriting game, and so much more. They even made up the most ridiculous programming language in the world, apparently to see just what you could do and how you thought. They called it BALANCE.
I am convinced that BALANCE is the sickest computer-related thing anyone has ever conceived of. It consisted of 4 "source registers", 2 "destination registers", 256 memory cells, the program tape, the instruction pointer, and the instruction speed. The speed, obviously, is how the machine moves the instruction pointer after each instruction (-16 <= IS <= 15). If the speed is ever set to 0, the machine halts. The tape also loops mod(length of code) if the pointer goes "off the end".
The strangest thing about BALANCE is that it never addresses anything directly (the instructions say that "all computer science problems can be solved by a level of indirection, and BALANCE provides this facility automatically"). So the register values are always pointers. In explaining this, M[reg] refers to the memory location pointed to by register "reg". Each operation usually affects more than 1 register as well. Also, when I say reg+1, I mean the next register. So for example, s1+1 = s2. Since there are 4 source registers, s3+1 = s0, and similarly d1+1 = d0. There are 4 operations:
So, I coded a ridiculously simple Perl script that would turn:
MATH 1,2,3 PHYSICS 01011 SCIENCE 00000 LOGIC 0,1,2into a "runnable" hex string. The first tasks we had to do all involved halting the machine. Fortunately, the solution I came up with for the first task, "halt the machine", worked for the next like 4 tasks:
PHYSICS 1 SCIENCE 0This will halt the machine as long as there is a nonzero value in memory. Just add MATH(0,0,1) if there's not.
But the real doozy (and I made sure and picked the hardest problem on the list) was to copy the value of a memory location to one of the registers. Think about that one for a second. You can only write a value to the registers if it's hard coded, and even when you do, the registers move around!! So the solution lies in creating a loop: basically the idea is that you want to subtract x from the memory location, add x to a register, and loop until the one memory location is zero. This will work because your loop will usually consist of a SCIENCE instruction that forces the program to jump to a SCIENCE 1 instruction set at the beginning of the loop. Then when that memory location gets to zero, hopefully s0 is set to that location, and it will skip the jump, falling into your halt trap.
Easier said than done. Good lord, was it even easier said than done.
All the registers are set to zero. Memory location 0 has the value, mem location 1=1. Here's the code:
PHYSICS 11110 // Sets d0 to 0x1e PHYSICS 00100 // Sets s3 to 0x4 PHYSICS 00001 // Sets d1 to 0x1 PHYSICS 00001 // Sets s0 to 0x1, d1 to 0x1 (because they rotate!!!) PHYSICS 00001 // Sets s0 to 0x1, d1 to 0x2 MATH 0 0 3 // M[d1] = M[s1] - M[s0], M[d0] = M[s0] + M[s3] // That is, M[0x2] = M[0x0] - M[0x1], M[0x1e] = M[0x1] + M[0x4] // 0x1e = 1, 0x2 = a-1. // Already, we see the first trick: Physics 00001 is a good accumulator. // The next deal: we need a memory location to equal 1 so we can subtract // from the memory location, until it equals zero. We stick it here because // of our strategy: keep writing the newest value to an increasing location // in memory. That gets the register to the right value and we win. PHYSICS 11010 // Sets d0 to 0x1b, s2 to d0 (0x1e), s1 to s2 (0), s0 to s1 (0) // Now we start this loop: set s2 to 1 so we can use it to subtract. s0 is // set to 0 so we can copy the number. // The rest is irrelevant. SCIENCE 1 // Start of loop MATH 0 3 1 // M[d0] = M[s3] + M[s1], M[d1] = M[s0] - M[s2] PHYSICS 00001 // s0 = d1, accumulate to d1 SCIENCE -3 // end loop // So this loop goes (0, 2), (2, 3), (3, 3), (3, 4), (4, 4)... // So, we should get to memory value a/2 for value a. Oops. MATH 0 0 1 // M[d1] = M[s1] - M[s2], M[d0] = M[s0] + M[s1] // or M[a/2] = M[0] - M[0x1e], M[0x1b] = M[a/2?] + M[0] // or M[a/2] = a - 1, M[0x1b] = 0? + a // So we're just gonna start over again. Good thing that a // value was still there! ;) SCIENCE 1 PHYSICS 00001 MATH 0 3 1 SCIENCE -3 // repeat loop // Add one for error PHYSICS 00001 PHYSICS 11110 SCIENCE 0 //end! Success!!OK. So technically it can break. But it's a probabilistic algorithm ;)