ICFP Programming Contest 2006

The Caml Riders

This is a short description of the ``Caml Riders'' entry to the ICFP Programming Contest 2006.

The riders are

We were participating for the fourth time to this contest. We got a total of 4553 points.

Our programming language of choice is Objective Caml.

The Universal Machine

Our UM is written in Objective Caml. Here is its code (172 lines).

2D

Our solutions, written by hand in emacs (using extensively the kill-rectangle/yank-rectangle commands). The raytracer was first written in Objective Caml. We compute the fixpoint, but it seems from other team pages that it was not necessary. We would like to know why...

Balance

We wrote a small program to find a set of PHYSICS to go from one state of the registers to another state. Here is the code (you have to patch the code manually and recompile). It uses an iterative deepening search to find the shortest path (but some PHYSICS can be commented out in the source to speed-up the search, resulting in a possibly longer path). It uses a generic search library.

Our solutions:

Black-knots

Our algorithm to solve this puzzle is as follows: first we sort the wires to get the expected permutation using some kind of bubble sort (yet, interestingly, it seems that bubble sort can be of some use, after all). The plinks that we get are still lower than the required values. Then we insert new transpositions, 2 by 2 to maintain the permutation, and thus increasing the plinks of two wires by 1 simultaneously. To find out where to perform these insertions, we build a matrix while during the bubble sort which says whenever (i.e. at what line) two wires appear consecutively during the sort. Then a brute-force search (DFS) is used to decrease the number of missing plinks to 0...0. Here is the code. It uses a generic search library.

Since it appeared that our solutions where far from optimal (in length) and that the verification was taking quite a lot of time (for the last puzzles) we also wrote a compacter to merge (and swap) lines.

Our solutions:

Ants

Adventure

We didn't make much progress in this one. We only reached the Museum (thus got 245 points), but were enable to understand what we were supposed to do with the blueprint. The puzzles have been solved by an Objective Caml program.

Advice

Our solutions: