The task
The goal of the contest was to write a virtual machine, to execute some given code: the code itself was a UMIX system, where we add to hack inside (cracking some passwords and so on) and solve the problems found there.
Here is a list of some problems:
- Balance: a language containing only 4 instructions is given. Each instruction performs two actions, making everything hard to implement, as when you want to do something, something else is also done as a side effect.
- Ants: maps are given where some ants must reach some food. Ants are programmed by changing directions in 7 different situations. Unfortunately, these situations most of the time involve interacting with another ant, which is not always easy...
- BlackKnot: boards had to be written, where pipes go from one side to another side. The information given is the starting position and ending position of each pipe, and the number of right turns it does. A pipe turning always involved another neighbour pipe turning in the opposite direction.
The Score : 4203
| INTRO 30 | CIRCS 1264 | BLNCE 959 | BLACK 1000 | BASIC 100 | ANTWO 100 | ADVTR 225 | ADVIS 325 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
The Schedule
- Friday 18:00 - We all read the contest task, gathered at INRIA Rocquencourt.
- Monday 18:00 - We could not submit our solution to Ants:Puzzle 4, juste for a few seconds... finishing with 4203 points.
Contributions: Fabrice Le Fessant
The processor
Of course, I wrote my own processor. At the end of the contest, we had three of them. Mine was not the fasttest one, but I still did some interesting stuff:
- Just-in-time optimizations: constant propagation in the evaluated code, dead code elimination.
- Tracing of code.
- First access to code or memory locations: I could for exemple detect that changing the position "1992467" in the decompressed archive to 1992799L would eliminate directory access checks, allowing one to read all files in the system as user "guest". We didn't use the trick as the team discovered all the passwords in the meantime.
The Balance problems
I wrote the solutions to all the problems except two by hand. The last two problems, "fillmem" and "multmem" were harder to solve for me. I finally decided to write a tool that would help me change the values of the register from state to another. The tool would only use 4 registers (two sources and two destinations), without bothering about the values of the 2 other source registers: it would just explore all the possible states that could be reached by assembling any number of PHYSICS instructions, and stop as soon as the wanted state was found. In most cases, it would find a transition in 5 to 6 instructions, but I had sometimes to change the starting or ending state. The other problem was to find how to perform a multiplication with only ADD, SUB, AND and XOR, and without any "1" number. I found the solution on monday morning in the bus going to INRIA, and wrote the previous tool and the code till 1pm. I used the tool to solve "fillmem". The tool was also able to evaluate and certify the the programs I wrote, which was easier than to run the simulator in UMIX.
Here are my solutions by hand: addmem2 , copymem , stop1 , swapreg2 , addmem , copyreg , stop127 , stop swapreg , clearreg , stop128 , swapmem and my program generated solutions: multmem and fillmem .
The BlackKnot problem
For the BlackKnot problem, I just wrote a compressor in 10 minutes on monday, between the "multmem" and "fillmem" problems of Balance: the other team members had found the solutions for all problems, except that the solutions of the last two problems were too big to be fed to the certifier. I thus wrote the compressor that would move the pipes swappings as up as possible, and remove lines with no swappings any more. It turns out to be efficient enough to divide the sizes of the solutions by 10, making them very fast to be evaluated by the certifier. Moreover, it helped find a bug in the solver, who didn't insert newlines correctly at one point.
The Ants problems
I had 2 and an half hour remaining at the end of the contest: I decided to try to solve some ants puzzles, since my team had given up after solving puzzles 1 and 7. After thinking for 1 hour and 1 half, I finally found the solution to puzzle 3, leading to immediate solution for puzzles 2 and 5 (by Boris). The trick was to use two different kind of ants side by side.
I solved puzzle 4 at the last minute, but the certifier refused to give me the point, because I used the title of puzzle 3, changing the 3 to 4, whereas is was also expecting the "Turning with fewer programs". Changing just that prevented me to submit in the last minute :-(.
Contributions: Alain Frisch
The processor
We had two UM simulators written in OCaml, one by Fabrice, and the other by Nicolas and myself. Both were operational shortly after the task was submitted and they allowed us to decode the codex and to start playing with UMIX. Berke rewrote another implementation in C which was about 10 times faster.
I wrote the memory manager and the evaluator for the UM and Nicolas wrote the opcode decoder. We played with various implementations for the memory manager. Our best implementation stores the table of allocated blocks in a double dimensional array (because arrays are severely limited in size in OCaml) and uses a freelist to reuse released blocks.
Cracking passwords with BASIC
A BASIC program to crack some passwords was available in the guest account. It was necessary to patch it in order to try passwords of the form guessDD where each D is decimal digit. So it was just a matter of doing two nested loops in BASIC without for-loops and with roman numerals. Here's the code.
The BlackKnot problem
I wrote the code to solve all the BlackKnot puzzles. Jean-Baptiste and Berke contributed key ideas and insights. Berke also wrote an interactive Blackknot game to help us get some intuition on the problem.
For the small puzzles (000,010,020,040, but not 030), I used a brute force approach (with backtracking and memoization) with some heuristics. I was amazed that it worked fine for 020 and 040. This was an indication that the problem might not be so hard and that either good heuristics or a really simple algorithm could do the job. In particular, the solver did not backtrack a lot. It used several ways to cut down the space search: decomposition in connected components (see below); the fact that a pipe cannot go to the right more than n if n is the number of plinks to do; the fact that the number of plinks to do for a pipe must be greater than the number of other pipe which must still cross this pipe from the right to the left (because such a crossing-over uses on plink).
The final solver, which could crack all the puzzles in a few seconds proceeds along these lines:
- A first pass consists in sorting the pipes, with a selection sort: the pipe that should arrive at the last position is sent there; then the one that should arrive at the previous position; and so on. At the end, each pipe is at its correct final position, and we did not use too many plinks.
- Now, it's a matter of adding enough plinks for each pipe, without changing the permutation. Two "X" at the same column, one above the other, creates one plink for two adjacent pipe. We use this approach to reduce the overall number of plinks to do, but stopping before the number of plinks for a pipe goes below 4. Otherwise, we could arrive at a problem without solution or which is too difficult to solve.
-
Now, we must make non-adjacent pipes work together to reduce their
number of plinks to do. To do that, we use trapeze-shaped diagrams:
X X X X X X X X X X X X X X(or the symmetric shape.) Such a diagram produces the following sequence of plinks: (n + k, 1, 1, 1, ..., 1, n), where n is the number of double X in the middle and k is the number of intermediate pipes. We then use a heuristic driven exploration (with backtracking and memoization), trying to use such trapezes to reduce the total number of plinks to do. Some points to note:- We can work in each connecyed component separately, where a connected component is a maximal sequence of adjacent pipes with positive (non zero) numbers of plinks to do.
- The total number of plinks to do in a component must be an even integer.
Fabrice wrote a compressor for solutions, so that the UM would accept it more rapidly.
See here for the list of problems and solutions found by the solver, and the code for the two solvers. You can clearly see the three successive phases, e.g. on this solution.
The advise problem
The task was to implement simple functional transformations using term rewriting. Fewer and shorter rules gave more points.
The difficult point was that the rewriting engine had a stupid rule to apply redex deeply in terms. Note that it was not necessary to really implement the required transformation: just passing the built-in tests was enough.
I wrote these two scripts: xml.adv and arith.adv.
The 2d problem
The task was to implement simple functions in a crazy language made of boxes connected by wires, drawn on the plane in ASCII art. I only contributed to the solution for the raytracer puzzle. It was out of question to solve it by hand, so we used the following approach:
- The raytracer function was written by Boris in a very limited subset of ML. He could thus test the function and simplify it (e.g. it seemed that 2 iterations were enough) quickly.
- Nicolas wrote a parser from a subset of ML. The parser uses the actual parser for revised syntax from Camlp4, and produces a simple AST. This parser can make the name of modules shorter.
- I wrote a compiler from this subset of ML into an abstract description of boxes connected by wires. The compiler produces for each module an array of boxes such that wires only go from one box into a box which appear later in the array. There is nothing fancy in the compiler. I just needed to be careful about duplicating variables which are not used linearly and to combine multiple value constructors in a single box. Just as I write these lines, I realize that I've been stupid: a "match" statement in ML is compiled into a "case" box. In order to prevent the branch which is not choosed to produce a result (which is invalid), I introduce some kind of "transistor" to block the output of this produce. In many, this introduce many useless boxes. Oh well.
- I also wrote an ML module to actually draw boxes and wires in ASCII art. Boris helped me to improve it by suggesting ways to simplify wires.
The final submission was very slighlty optimized by hand.
See: all the code. The output of the parser is fed to the compiler by a little script which produces one file for each module. Another script actually combines all the modules horizontally.
Contributions: Jean-Baptiste Tristan
UMIX administration and the whole game
I've spent time at the beginning digging as much information as possible about the game and describing the tasks to my teammates (occupied hacking the implementations of the um).
The BlackKnot problem
I've given ideas and insights, as Alain already said above
The adventure game
I've played the adventure game, Unfortunately I began late so I couldn't finish it. The contest stopped right after I finished building the downloader and uploader so I didn't get enough time to crack the censorship engine. I solved all the problems by hand altought I designed a solver which Berke tried to implement using Boris applyomatic, unfortunately, I finished before it was ready to unleash its power (Hum...). I got all the information from the game to solve the problem and produced scripts using a ruby script written by Nicolas.
Contributions: Boris Yakobowski
I joined the rest of the team on saturday afternoon, after having convinced myself that the contest was going to be really fun. At that time, I had written my own (somewhat hackish) UM machine in OCaml, solved the BASIC problem, and started looking at the 2d langage.
The 2d problem
I wrote the mult.2d and rev.2d versions we submitted, optimized by hand. I was also responsible for writing the ML code for the raytracer. I used a very limited subset of functional ML, which made explicit destruction of pairs explicit and used no complicated pattern matching. As it turned out the langage was too low-level, as Alain's compiler was quite smart and dealt with pairs by itself. The first version of the code version was essentially untyped; I merely used polymorphic variants to encode the value type of the boxes, in order to avoid pattern-matching warnings. In a second time, I constrained the polymorphic variants to encode the structure invariants of the program. This gave us a fully-typed version, and caught a stupid bug.
When we ran the script, we realized that reaching the fixpoint took too much time. However, since the subset of the problems checked by the antomaton executable is limited, two iterations of the update functions were sufficient. This is what is implemented in the translated (non-ML) version. After that, Nicolas wrote a piece of code which renamed the functions name into one character to gaim some place, and we ran Alain's compiler on it to obtain the final file.
The adventure game
We never discovered the "switch goggles" instruction during the game, which explains why everything was solve by hand by Jean-Baptiste. Indeed, parsing everything seemed much more complicated than actually solving the sub-problems...
At some point during monday afternoon (GMT+1), Berke and Jean-Baptiste managed to automatically parse the inputs. We then feed the constraints to a tool called applyOmatic which I had written two years ago to enumerate all the lambda-terms of a given type (this is described in an article by Joe Wells and myself). Unfortunately, while it was able to solve the USB cable, the EPROM burner proved to be too big. While I tried to cut down the search space, Jean-Baptiste finished to solve it hand.
After this, we tried to modify the robot's code to teleport to the museum. Unfortunately, there was only 10 minutes left. Trying to see if we should use room_of_name (and guessing what was the right name) or the function neighbor, as well as getting accustomed to the horrendous syntax of the langage proved to be too much for us, and we ran out of time.
The ants
Everything was done by hand. I managed to solve the 7th problem (which was quite easy), but miserably failed on all the other (the first having already been solved by Jean-Baptiste). Afterwards, after Fabrice had found the solution for puzzle 3, it was straightforward to adapt it to puzzles 2 and 5.
Contributions: Nicolas Pouillard
Mailing list and Subversion repository
I setup a mailing list for the team using Mailman. I also managed the repository administration, I used Subversion and plugged svn-notify to drop commits as beautiful emails to the mailing list.
The processor
I wrote the opcode decoder, as Alain already said above. I also played with different modules for the memory management using dynamic arrays from the Extlib and patricia trees of Jean-Christophe Filliâtre.
The 2d language
After having written by hand the two first problems of the 2d language (multiplication and list reversing), I wrote a parser of a ML subset in order to have a translator that produces 2d code. In fact I used the camlp4 parser and made transformations using the concrete syntax (quotations). I also wrote a first version of the compiler. After that Alain wrote a better and simpler one and we just kept my parser. Finally I also started to wrote a type checker for our ML subset, in order to find a bug in our ray-tracer but Boris found it before I finished it. For the fun I finished it after the contest (showing that a function was never called, and that we could get 11 points more :/ ).
Contributions: Berke Durak
A little bit of polishing for the Ocaml UM interpreter
I added some command-line parsing. I functorized the State modules and added some statististics functions in order to get information on the size of allocated blocks.
The C UM interpreter
As running adventure with the Ocaml UM interpreter was painfully slow, we decided to implement an interpreter in C, which I did. The interpreter is a no-frills implementation which is totally unsafe - no bounds or other safety checks of any kind. It runs the Sandmark in about 56 seconds on my 3.0 GHz Xeon and it uses about 200-300 MB of RAM using adventure.
Blacknot
I didn't like the heuristic approach to solving Blacknot, so I looked for an algorithmic one. I remembered from my math classes that permutations can be decomposed as products of cycles, and it is easy to represent cycles using crosses (e.g., transpositions of the form (i,i+1)). I implemented the cyclic decomposition hoping to get a sub-solution (that is, a solution where the permutation is done and only the number of plonks remains to be decreased). Unfortunately, for most problems, this decomposition was eating too many plonks. We got the insight while discussing with alain, which gave us the idea of using some kind of bubble sort to move all the inputs to the right. This gave a nice sub solution (e.g., with only plonks to do). I wrote a simple graphical interface using the Graphics module. We then explored various ways of reducing plonks. I implemented a greedy trapezoid strategy. Unfortunately it did not converge. I then had to go and Alain found the good heuristic in the night.
Adventure
As we hadn't discovered the switch goggles directive, I wrote a parser for the description of the conditions of the objects. I then called Boris's applyomatic to solve the puzzles. It worked on the simplest one, but on the other ones it failed to terminate in a reasonable time. I then started writing an ad-hoc solver but Jean-Baptiste finished solving those puzzles by hand.
After he found the robot's RML file, I started hacking it and managed to read the manifesto by using a side-effect on the world : going to the Junk room or going to the Room with a Door depending on the value of the character.
Other teams
Tuesday, July 25, 2006