Team name: Frictionless Bananas
Team members: Jeremy Sawicki, Mieszko Lis, Nirav Dave
Full submission:
frictionless-bananas.tar.gz
UM just-in-time compiler:
jit.tar.gz
This page describes our 2006 ICFP Programming Contest entry.
We wrote our initial UM simulator in Haskell. It ran the codex in about 15 minutes, and was enough to get us started on the puzzles, but it eventually became clear that more speed would be helpful. We wrote another version in C++ which was a great improvement, and later on tweaked it to use raw pointers for array identifiers, giving us yet another speed boost (and restricting us to 32-bit machines in the process).
After the contest proper, Jeremy decided it would be fun to implement a just-in-time compiler to see how much speed was possible. It can boost the speed by another factor of 2 to as much as 4 in some cases, though on other examples the speed of the compiled code is not able to make up for the time spent compiling.
These are the times to run SANDmark on a 2GHz machine:
Haskell interpreter: runs out of memory -- we must have a leak
somewhere
C++ interpreter: 78 seconds
C just-in-time compiler: 27 seconds
The just-in-time compiler first runs the UM code for a while in "profiling mode," which is a standard interpreted UM implementation that collects statistics about which instructions (that is, which values of the program counter) are executed most often. Then it creates a C source file that contains compiled code for the most commonly executed instructions as well as an interpreter to be used for the instructions that were not compiled. The C file is compiled as a shared library with GCC and dynamically linked into the main program. Then UM execution continues using native code. Typically it will compile about 5000 instructions that represent somewhere between 70 and 95% of the executed instructions, depending on the task.
Periodically the program switches back into profiling mode to see whether the set of commonly executed instructions has changed. If it finds that recompiling will increase the percentage of instructions executed using native code by enough to make the compilation time worthwhile, a new C source file will be generated and compiled.
The JIT compiler is only known to work under Linux on 32-bit x86 machines. Mieszko tried it on a Mac but found that the method of compiling and linking a shared library did not work.
We took an approach of first sorting the marbles into the correct order using as few swaps as possible, and then adding more swaps to get the correct number of plinks. It is easy to do the initial sort in as few moves as possible by greedily swapping any pair that is out of order -- once there are no more such pairs, they must be in the correct order.
It is possible to construct examples that cannot be solved by the approach of sorting first. For example:
0 -> (2,2) 1 -> (1,2) 2 -> (0,0) 3 -> (5,2) 4 -> (4,2) 5 -> (3,0)
The first three marbles and the last three marbles need to reverse their order. Marbles 1 and 4 need one extra plink, and none of the other marbles do. That means the only way to solve the problem is to partially sort the left and right halves, then swap 1 and 4 twice, then finish the sort. For example (using a notation where the marbles are numbered based on their final order):
210543 |><><| 201453 ||><|| 204153 ||><|| 201453 ><||>< 021435 |><><| 012345
Furthermore, it is not possible to start with an arbitrary initial sort and then insert plinks in the middle of the sort. In the above example there are valid sorts that move marbles 1 and 4 to the outside rather than the inside, but in this case only the inside will do. Fortunately, the problems in the contest were not as devious.
To think about the second stage of the solution, it is useful to describe the problem in terms of the number of additional plinks that each marble needs after the initial sorting, with the numbers listed in the order of the final locations of the marbles. In the above tricky example, the list is [0 1 0 0 1 0], which clearly has no solution.
For all of the problems in the contest, we found that the lists contained no zeros. Our initial idea was to proceed from left to right, producing one zero at each step. Suppose at the current stage the list is [... 0 0 a b c d ...]. If a<=b, we can swap a and b (2*a) times, producing the list [... 0 0 0 (b-a) c d ...], and proceed to the next step. If a>b, we can swap a and b (2*b-1) times, producing the list [... 0 0 1 (b-a) c d ...]. Ignoring the 1 and the fact that the pair is now in the wrong order, we can move onto the next step, solving the rest of the problem, and then in the end swap the pair one more time. We initially (incorrectly) thought that this would solve any problem where the list did not contain any zeros, so we coded it up, along with an extra optimization that greedily swaps as many pairs as possible without producing zeros before sweeping from left to right.
What we failed to realize was that we could end up with a final list like [0 0 0 ... 0 0 a] and not have a way to eliminate the last number. We then observed that it is possible to do the same process from the left and right simultaneously, with the two meeting at any point, for example [0 0 a b 0 0 0 0]. If we get lucky, there will be some point where they will meet up as [0 0 0 0 a a 0 0] instead, and then we can swap the remaining pair. It turns out we get lucky for about half of the contest problems this way. From there, we hoped that if we just tweaked the input by performing swaps in various arbitrary ways after the inital sort, we should eventually get lucky on all the problems. We already had the optimization code that greedily swapped as much as possible without producing zeros, and that optimizer produced many intermediate steps, so we decided to test those intermediate steps. We found that on all of the contest problems, at least some intermediate step (typically on quite a few of them) we would get lucky and find a solution. In fact, it turns out that we always get lucky with the final output of the optimizer, so that is what we coded in the end.
Our solutions:
000 - 8 lines
010 - 34 lines
020 - 55 lines
030 - 94 lines
040 - 116 lines
050 - 179 lines
100 - 333 lines
200 - 814 lines
300 - 1369 lines
400 - 1781 lines
500 - 2376 lines
We coded these by hand. They aren't particularly well optimized.
Our solutions:
mult - 34 points
rev - 37 points
raytrace - 1221 points
We never saw the right approach for this. We solved arith (which may be luck rather than a correct solution), but not xml.
Our solutions:
arith
xml (not solved)
Our solutions:
stop - 10 points
stop1 - 10 points
stop127 - 20 points
stop128 - 15 points
copymem (not solved)
copyreg (not solved)
swapmem - 35 points
swapreg - 50 points
swapreg2 - 50 points
addmem (solution missing) - 44 points
addmem2 (solution missing) - 40 points
multmem (not solved)
fillmem (not solved)
clearreg (not solved)
We solved 7 of the 9 ant puzzles.
Our solutions:
puzzle 1
puzzle 2
puzzle 3
puzzle 4
puzzle 5
puzzle 6
puzzle 7
puzzle 8 (not solved)
puzzle 9 (not solved)
We wrote a Haskell program to interact with the adventure game in an automated way. It would issue commands, observe the responses, and issue more commands based on the responses. The main thing it was able to do was look at the contents of a room and come up with a sequence of commands to obtain a given object in a given configuration. We used this to obtain all the parts needed to build the downloader and the uploader. (The program was unable to build the RS232 adaptor for some reason, so we solved that one by hand.) Unfortunately we never noticed the ability to switch goggles, so we had to parse the English text.
By the time we had the uploader, we were running out of time. We wrote a program to extract one bit of information from a censored object by moving to one of two rooms, and used it to read the manifesto, but by then the contest was over.
First of all, thank you to the organizers for all their efforts putting together such a good contest. It was fun, and quite creative -- on the technical side, the story threading throughout the contest, and the operational aspects.
Having a collection of smaller tasks had pros and cons. It was nice being able to choose an interesting problem to work on from among a few options, but this also makes the contest highly parallelizable and therefore gives larger teams an advantage, which doesn't seem like a good thing.
The puzzles were certainly fun and interesting, but they made the contest a little more puzzle-focused and a little less programming focused than would be expected for a programming contest. Still, it doesn't hurt to have a slightly different take on the contest each year. With the ICFP contests, you never quite know what you are going to get, and the result this year was generally positive.