Ninth annual ICFP Programming Contest

This page is about the ICFP Programming Contest of the year 2006,
lived and experienced by the team called

 
SECTIONS

 

PLOP
Intro
Circs
Blnce
Black
Basic
Antwo
Advtr
Advis
Concl
 

About PLOP

The PLOP team is composed of four members :

• Benjamin Canou
• Alexis Darrasse
• Nataliya Guts
• Philippe Wang

Our programming language of choice is Objective Caml.

intro

Our UM is written in about four hundred lines of the C programming language.
It is the main problem that caused our lack of time since we passed about eight hours to debug some weird programming errors...
It is not especially fast nor slow : 2 min 50 to run the sandmark benchmark on a Linux - AMD Athlon XP 3200+.
We wrote a second version (with no checks) which takes 1 min 30 on the same machine, however it has to run on a 32bit system. It is 80 lines long.

• original VM (endianness safe): vm.c
• unchecked VM (endianness safe but 32bits): vm_unchecked.c
• (local copy) the umix system: umix.um
• (local copy) the codex: codex.umz
• (local copy) the vm in um: um.um
• (local copy) the um specifications: um-spec.txt
• (local copy) the original message: message.txt
• how to get 230 points : intro

The other languages used were Objective Caml, Perl, and Bash.

circs

We resolved all the puzzles manually, the raytracer is the 2D version of our experiments in Caml, it doesn't work on some tests, but since the tests seem to be generated from the submitted program and the current version (version means the actual ascii art, not the program) passes them, it's ok :-p.
However, when a version failed on a test, the Caml program found the good result with the given data, so it seems to be just a transcription problem, and since there are only three colors, it seems that there's no real need for a search for the fixed point...

• list reversing: rev.2d
• multiplication: mult.2d
• raytracer: ray.2d
• raytracer model in Caml: ray_model.ml

blnce

We wrote a little printer in Caml in order to have a more readable concrete syntax...
We didn't write any program to optimise the PHYSICS use, so they were all written by hand and some programs are far from perfection since we used repetitions of patterns found for some standard behaviours...
We didn't have enough time to complete this task, we didn't manage to program fillmem and multmem.

7F00

407F267F3300

7F64716100

7F617F00

7F61616200

627C2300

627C237F615500

7F7F247E7D7C7B6100

6162627C61617F7F61617F7F61612B03
01610161617F7F61617F7F6161616102
10017F7F61612B610461610001021201
61617F7D61617F7F61617F7F6111

617F7F6161686261012E61617F61617F
616161617F6112617F61617F61617F7F
7F7F7F7F7F116400

• All the solutions in one script : balance

black

We solved the first puzzle on paper and the next, up to 300, manually with the help of an ever evolving perl script. The solutions becoming too long, we transformed the script to a solver. The algorithm it implements is the folowing:

1. Sort
2. Cut the list in blocks of three.
3. If the last block contains less than three items, empty the items in it.
4. Print the commands executed up to here.
5. For every block, if the sum of the plinks remaining in it is odd, remove one plink from the last item of the block.
6. For every block:
   1. If the first has more plinks than the second, equalize them by descending it twice and then getting it back to place, as many times as needed.
   2. If the second has more plinks than the first, equalize them by descending it once and then getting it back to place, as many times as needed.
   3. Empty the third by going twice up and twice down, as many times as needed.
   4. Empty the first two items.
7. Print the rest of the commands, putting in parallel the commands of the different blocks.

• The solver : black.pl
• 000 : black.000
• 010 : black.010
• 020 : black.020
• 030 : black.030
• 040 : black.040
• 050 : black.050
• 100 : black.100
• 200 : black.200
• 300 : black.300
• 400 : black.400
• 500 : black.500

basic

• The solution : hack.bas
• To get the publication : basic

antwo

All the puzzles were solved by hand since they were not too hard after we defined the two main patterns which are: a group of two ants which walks at an average speed of 0.5x the speed of one ant, and another pattern which follows a diagonal.

• Puzzle 1 (Simple) : 1.ant
• Puzzle 2 (Rock climbing) : 2.ant
• Puzzle 3 (Turning) : 3.ant
• Puzzle 4 (Turning with fewer programs) : 4.ant
• Puzzle 5 (Basketball) : 5.ant
• Puzzle 6 (Tight Turn) : 6.ant
• Puzzle 7 (Threshing Machine) : 7.ant
• Puzzle 8 (Trading Places) : 8.ant
• Puzzle 9 (Diagonalia) : 9.ant

advtr

We resolved all the puzzles manually, with the aid of vim to generate the commands easily. We didn't try writing a parser because we advanced fast enough and we hadn't discovered the "switch goggles" tip that would simplify the eventual parser.

In order to circumvent the censory engine we encoded the censored message in the condition of an item. Every character of the string is transformed to a kindlist of a length equal to the value of the character. The kindlists are chained in a condition encoding the string. A decoding function inverts the process and returns the original message which this is not censored.

Our solution is in two files, with the commands that we wrotte manually. The only interesting part is the modified robot mind source, also provided seperately.

• First part : adventure
• Second part : adventure_sequent-sequel
• Robot mind source : gc.rml

advis

We implemented addition and multiplication according to the corresponding classic recursive primitive functions. To minimize the length of the code we factorized it using a specialized if-then-else construction inspired by that in Lambda-calculus.

• The rules for arith (168 points) : arith.adv

concl