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: