The ICFP Programming Contest is an annual international programming contest, hosted each year by a different programming language research group. It works like this: On a well-known date, the hosts release a problem, usually in the form of a specification, on the Internet. The participants (working alone or in groups) then have exactly three days to solve the problem and to submit their solutions. The solutions are then compared by the hosts (usually mechanically and very objectively) and at some point the results are announced.
The 2006 contest came to an end today and, as in the past five years, I’ve participated as a member of the glorious team “Funktion im Kopf der Mensch”. Last year we were not very motivated by the problem, so we kind of gave up. The four years before, though, we always finished in the top 10 percent.
This year’s problem was not directly specified by the task description. Rather, a virtual machine was specified, and a program to be run on that machine provided. The machine is very simple, so it took us only about an hour to get it running. The result of running the program (called the “codex”) on the machine is another, bigger program, obviously uncompressed by the codex.
The second program is a very simple, UNIX-like “operating system” (or rather an imitation of an operating system), called “UMIX”. The first thing you do is log in as “guest” and see what’s around. There are several home directories, but you don’t have the passwords for those users. However, the guest account contains a BASIC interpreter and part of a program for hacking passwords (similar to the well-known “crack”). Finishing and running that program gives you the passwords for a few users. The stuff in those user’s home directories gives you further clues, so sooner or later you have all the passwords.
The real problems, though, are specified in the user’s home directories. Most of them are in the form of a programming language, for which there is an interpreter, and specifications for one or more programs to implement in that language. For each subproblem you solve, the machine spits out a “publication”, which is a string that gives you points if you submit it on the contest website (though it’s too late for that now, obviously). Usually, the shorter your solution, the more points you get.
The first problem I worked on was the “O’Cult” programming language. O’Cult is a term rewriting system, but instead of having sane rules for how terms are rewritten, O’Cult has one particularly nasty twist: If the rule to be applied can be applied an equal number of times in the main term’s subterms, it is not applied at all, which makes it very easy to reach a deadlock-state, where, although in theory further rewriting could happen, it is not done. My solution was to introduce two new terms, “Down” and “Up”, and guarantee that the whole term always contains exactly one Down or Up. The rules can then be written so as to always include a Down or Up in the left-hand-side, thereby ensuring that no rule’s left-hand-side matches more than once. This problem was pretty easy once I figured out what needed to be done, which wasn’t too difficult either. Here are my O’Cult programs for multiplying two numbers and bringing an “XML”-Term into normal form.
My “big” problem was the “2D” language. It’s basically an ASCII-art language with very basic operations. Here’s how my programs for multiplying two number and reversing a list look like in 2D. I drew those by hand in an editor.
The third 2D-subproblem was implementing a one-dimensional raytracer. Drawing it myself seemed out of the question for me, so I implemented (in Common Lisp) a compiler for a higher-level (functional) language which emits 2D code. My mistake here was not sorting out the theory before I started, because I underestimated the difficulty of the compiler’s task. As a result I had to spend about twice the amount of time that I saved in the implementation of the language with writing the raytracer in a way that the compiler could compile without producing incorrect code. Nevertheless, I got it working, albeit with a bit of cheating. The raytracer is supposed to calculate a fix-point, i.e., apply a step repeatedly until the result doesn’t change anymore. I was much too lazy to implement that as well, so I just figured out how often I would have to apply my raytracer step to pass the verification program. The answer is 9. Here, then, is my 2D raytracer, automatically generated and then manually optimized!
As always, my teammates were at least as successful as I was, so we were at fifth place (out of 346) 8 hours before the end of the contest, when the hosts turned off the online score-keeping to make the last hours of the competition even more thrilling.
Overall, this was quite an exciting contest, although I have to say that I really missed the teamwork that usually comes with it. When you have four people and six problems to solve, the teamwork chiefly consists of figuring out who wants to give which problem a try. My favorite ICFP contest is still the 2004 one. Nothing’s more fun than watching your little virtual ants search for food on a hexagonal grid! ;-)
If you want to try out UMIX yourself or even give a few of the problems a shot, look no further! Download this package, which contains our UM interpreter, the UMIX code and the passwords to all the users.
Mostly Software 
Here is my shorter answer:
{ 9 rules. scored 167. one more point for cutting one rule. }
Add Z y => y;
Add (S x) y => S (Add x y);
{ define multiplication (Mult) here }
{ a*0 = 0 and a*Sb = (a*b) + a. }
Mult Z y => Z;
Mult (S x) y => Add y (Mult x y);
{ when all other computation is done }
Compute (Add x y) => Add (Compute x) y;
Compute (Mult x y) => Mult (Compute x) y;
Compute x => x;
S (Add x y) => S (Compute (Add x y));
S (Mult x y) => S (Compute (Mult x y));
. { end of rules }
I gave up after solving this problem, so I suppose your solution is more powerful in solving general problems.
It seems someone got 169 out of it – I’d love to see their answer.
Wow! Congratulations, looked like you guys kicked some serious butt!
I participated in the ICFP for the first time this year and was pretty taken aback at how difficult the whole thing was (I think we finished around 80, probably lower once the scoreboard is updated for the last time). I was actually hoping you had something to say about the BLACK problem. My intuition tells me it’s one of the easier problems but I was never able to get a good solution. I wrote a simple A* in C and quickly realized the search space is just too huge for anything other than the first problem.
I also wouldn’t mind looking at your 2D compiler source :) I figured something like that was necessary for the raytracing thing but didn’t trust myself to be able to finish it in time.
Thanks for you comments, guys!
Wei Hu: Interesting approach!
John: I wasn’t very involved with the Black problem, but as far as I know the solution was to do a bubble-sort to get all the marbles to their target positions, and to at every step check whether there were two adjacent marbles which both needed an additional plink, in which case they would be swapped twice (in addition to what the sort does). It took they quite some time to figure out and implement, so it’s certainly not an easy problem. We suspect that there’s a simpler solution, though.
Trust me, you don’t want to see my 2D compiler! What you can see, though, is the high-level source to my raytracer here.
As the one who did the black problem, I’ll attempt a small write up about that. The Black problem was about a ball game, where you can drop a ball into an input tube. It is then specified through which output tube the ball is to leave, and how many times it “plinks”. A ball will cause a plink whenever it goes through a crossing from left to right. Indeed straight pipes downwards and crossings between adjacent tubes are the only possible operations. The problem was to find a wireing that matches the requirements.
Just as schani with the 2d problem we did sort out the theory well enough before we started, but after about 6 hours of coding our solver (in O’caml) we came to the conclusion, that bubble sort was powerfull enough to get everyone to its destination (albeit very inefficient, since there is no parallelization). All that was left was to use up the additional plinks. Our principal approach here was to minimize the remaining plinks from the sides towards the middle. Unfortunately sometimes this process required “guidance”, that is handling of special cases, where our (very ugly) program got lost. Yet more code you don’t want to see.
Just to illustrate how stupid our programm is: for the problem set with 500 inputs it produced an 48 MegaByte output file with around 100000 (yes hundred thousand) lines taking about a minute. Verification in the UMIX system took around 5 hours, although I dare to claim that our VM is very fast.
One thing I forgot. Of course the contest is not all about programming, we solved all the ant-puzzles by hand, or rather by brain in around 5 hours. I still wonder why it was possible to use 10 different kinds of ants, when (the same) two where enough for the puzzle 8. You can find our solution here
Thanks for the writeup. I chose to ignore the raytracer and focus on other tasks, congratulations on creating that monster. My 2D list reversal program here.
martin: If I understand the Black problem correctly all solutions must have exactly the same length. You need exactly one crossing for each plink and the number of plinks is given by the problem set specification, so you can’t do with more or less crossings. Or am I missing something here?
schani: The number of crossings is fixed, yes. So noone could have done with fewer crossings. But, the number of lines is not. Because you could do more than one crossing per line, consider 4 pipes where all the positions are correct already but they are missing one plink each, then you could could do this in just two lines, with parallel exchanges, or in 4 lines, with one exchange per line.
I had planned to write a compressor, but since the points did not depend on the number of lines I decided against it, due to time constraints.
I see. Maybe I should have read the spec before contributing my “wisdom” here :-)
Dudes —
Cool, thanks for the input on Black! I actually just wrote a really simple (maybe around 100 lines?) python script that solves it! It essentially does a bubble sort, and then works left to right, performing swaps to use up the remaining plinks. It stops three columns from the right: if it kept going, you’re eventually left with just one marble with 20 plinks or whatever. Leaving three left on the right puts you in a situation that’s trivial to solve by hand or with an exhaustive search. I don’t think this algorithm is general enough to work for ANY plink puzzle, but it worked on all that I’ve tried (the first five and then the last one with 500 rows).
Can you tell us the score you got at advise ?
I got only 161 at arith, and it was after the end of the contest. I can not try your own program as is use too much memory due to the number of step involved. Your solution has a computation that takes 1350 steps and my UM crashes a few computation after because my PC has only 512M.
In my solution, the worst case in the test suite takes 178 steps.
Wei Hu’s program does not pass the testsuite.
We got 165 at arith, but I didn’t optimize it, so there might still be a few points to get there. I worked on a machine with 512MB as well, and it wasn’t really a problem – try out our VM, maybe it’ll work for you.
Hi,
Later I came up with an even better solution, however, someone also found it to fail, could you guys try it?
{ 7 rules, scored 169. }
Add Z y => y;
Add (S x) y => S (Add x y);
{ define multiplication (Mult) here }
{ a*0 = 0 and a*Sb = (a*b) + a. }
Mult Z y => Z;
Mult (S x) y => Add y (Mult x y);
Compute (op x y) => op (Compute x) y;
Compute x => x;
S (op x y) => S (Compute (op x y));
. { end of rules }
I put a adequately fast UM implementation by Peng Li at the following URL: http://www.cs.virginia.edu/~wh5a/personal/icfp06.
You can try this VM too.
Sorry, I see what’s going wrong.
% advise arith my.adv
does not always use the same set of tests, that’s why sometimes it can pass the test suite.
Sorry that I gave a partially correct answer.
I need to work on this again.
Finally I got this right. I believe my solution is very clear.
This time it has 8 rules, but the score doesn’t solely depend on the number of rules. It also depends on the size, so I got 167 points.
{ It is gauranteed that Compute appears at most once. }
{ rules for three operations: Add, Mult, and S }
Compute (Add Z y) => y;
Compute (Add (S x) y) => S (Add x y);
{ a*0 = 0 and a*Sb = (a*b) + a. }
Compute (Mult Z y) => Z;
Compute (Mult (S x) y) => Add y (Mult x y);
Compute (S (op x y)) => S (Compute (op x y));
{ force the evaluation order when coflict occurs }
Compute (op x y) => op (Compute x) y;
{ we’re stuck, so eval again from the outermost level }
op x y => Compute (op x y);
{ op x y => op (Compute x) y; }
{ x must be in normal form }
Compute x => x;
. { end of rules }
Very smart! Using the Compute label to do exactly one evaluation step, then reintroducing it again. I’m pretty sure that it can be generalized to work with rules with nontrivial patterns in both arguments, not just the first one. For example:
Op (A x) (B y) => Something;
becomes
Compute (Op (A x) (B y)) => Something;
Compute (Op (A x) y) => Op (A x) (Compute z);
Compute (Op x y) => Op (Compute x) y;
Why do’nt the organizers not publish all the entries. It would be useful to see the solutions and help more people participate by reading up previous years solutions.
Do you know?
I think they don’t want to mess around with the copyright issues, and probably want to give the contestants the right to withhold their code from the general public.
Lovely Blog!
Good blog
Hi
Very nice work, admin! Have advised. It is healthy.
It easy to remove one line from solution at post 17!
7 rules, size: 94, scores: 168
{ It is gauranteed that Compute appears at most once. }
{ rules for three operations: Add, Mult, and S }
Compute (Add Z y) => y;
Compute (Add (S x) y) => S (Add x y);
{ a*0 = 0 and a*Sb = (a*b) + a. }
Compute (Mult Z y) => Z;
Compute (Mult (S x) y) => Add y (Mult x y);
{ (S (op x y)) => S (Compute (op x y)); }
{ force the evaluation order when coflict occurs }
Compute (op x y) => op (Compute x) y;
{ we’re stuck, so eval again from the outermost level }
op x y => Compute (op x y);
{ op x y => op (Compute x) y; }
{ x must be in normal form }
Compute x => x;
. { end of rules }