About this page
This is the page of the Freaks Unidos "FUN" team participating in the ICFP Programming Contest 2006.
- Alejandro Forero Cuervo (Blog entry about the contest)
- Sergio 10-points Garcia (Blog entry about the contest)
- Nelson Gastillo (Blog entry about the contest)
- Sebastián Gonzalez
- Igor Tamara
We are split over three different countries. We used IRC and a Subversion repository (which we've only made public after the contest ended) to coordinate our work.
Our final score was 1881 (Rank 53).
We had a lot of fun in this contest. It was very exciting.
UM
We wrote our UM in C initially (since, even though most of us prefer higher level languages, specially Common Lisp and Scheme, it seemed like C was a *perfect* match for this task, we didn't miss the constructions it lacks compared with higher level languages and it turned out to be reasonably fast).
We finished the UM in one hour but it had a bug that took us quite a while to find. In the end it turned to be a misinterpretation of the spec: Where it says:
The execution finger is placed to indicate the platter of this array that is described by the offset given in C, where the value 0 denotes the first platter, 1 the second, et cetera.
We thought it meant that if C is, say, 3, the execution finger should be set to 3. Instead, it should be set to the value in the register 3.
We managed to find this around 6 hours after the contest had started.
We were also working on a Common Lisp implementation but we abandoned it as soon as the C one was finished.
You can download our implementation from:
ADVIS
We solved all the ADVIS problems for a total of 266 points.
Arithmetic
The ADVIS.ARH problem was solved using the following set of rules, which was found by hand:
{ addition rules }
Add Z y => y;
Add (S x) y => S (Add x y);
{ multiplication rules }
Mult Z y => Z;
Mult (S x) y => Add (Mult x y) y;
{ disambiguation rules }
Add (Add (S x) y) => Add (S (Add x y));
Mult (Add (S x) y) => Mult (S (Add x y));
Add (Mult (S x) y) => Add (Add (Mult x y) y);
Mult (Mult (S x) y) => Mult (Add (Mult x y) y);
{ main rule }
Compute x => x;This solution scored 166 points.
XML
For the ARTH.XML task we found a not-so-nice solution by hand, worth 100 points only.
Other groups got as much as 335 in total, which makes us think that our ARTH.XML solution could be improved heavily. Perhaps other groups used automated rules generators?
ADVTR
For adventure we solved some of the puzzles in an entirely manual fashion. We used lots of Vim macros for quickly rewriting output of the program into inputs and some paper and ink for creating graphs of the dependencies of the objects.
We managed to get the downloader and most of the objects required for the uploader to work. You can see some of the notes we gathered here:
Given more time, we would have likely advanced further in this task. We didn't get stuck, but running it was taking way too long, even in our fast UM machine.
ANTWO
We solved 8 out of 9 puzzles, for a total score of 260 points. We got 5, 15, 30, 30, 20, 70, 30, 60 points out of each puzzle.
We used a Genetic Algorithm for this.
Sadly, our GA couldn't manage to solve the last puzzle.
The GA was based in this source code. It doesn't have recombination (only mutation). We guess that recombination could be useful in these problems. We tried to use GALib, but it wouldn't compile in Linux.
We used a simple binary genome, about 200 individuals in the population and low mutation rates. We used elitism in the GA.
You can see some HTML animations with the solutions of these puzzles
BLNCE
We solved all the BLNCE problems except multmem and fillmem for a total of 558 points.
We noticed that the spec to fillmem had changed to one that made it easy to solve only a few minutes before the end of the contest. Sadly, we couldn't get a solution in time.
For balance we used genetic algorithms to produce certain states in the registers based on certain input states. For example find some code that, if the registers are set to ( 0, 1, _, a ) ( 0, 255 ), leaves them at ( 0, 1, _, a + 1 ) ( 0, 255 ). Note that our machine supports using both literal values as well as constants in our registers.
We also implemented the balance machine, in order to efficiently test our programs (since running step_balance sometimes took way too long).
Both the GA and the balance machine where implemented in Chicken Scheme.
You can see the code we used at:
Note that it is very disorganized. Code clarity was not one of our goals while writing it. It includes lots of comments and an implementation of the balance machine (which, as we said, supports initializing registers to constants and adding numbers to them).
We used the GA to solve the different problems. Basically, we split problems into sets of "easy" problems. In the following descriptions of solutions, literal strings were found by the GA.
addmem (AMM)
We got 40 points:
627c2300
Here 627c sets regs at ( 01 02 03 00 ) ( 02 05 ) and (math 0 0 3) does the addition.
addmem2 (AMM)
We got 46 points, using a solution based on a tweak to addmem:
627c2370622500
copymem (CMM)
We got 180 points:
6171037f0001706c617961647474646464646466663c087f00
This corresponds to:
- 6171
- Intialize regs to ( 00 01 00 00 ) ( 00 F1 )
- 10 ((science 1))
- Make sure the speed is back to normal.
- 706c61796164747464646464646666
- Increase the counter.
- 3c ((math 1 3 0))
- Decrease memory.
- 08 ((science 1 3 0))
- Skip back to right after initialization of registers (unless M[0] = 0, in which case we go on).
- 7f00 ((physics -1) (science 0))
- If M[0] = 0, rotate registers (to make M[sR[0]] > 0) and halt.
copyreg (CRE)
We got 182 points:
71637e7c617f09017b72616b617b61012b0a6400
We figured an interesting way to solve copyreg: For every 0 <= i < 256, set m[i] = i + 1. That is, load all possible values in memory and stop. This is interesting because it always produces the same state, regardless of the value of the input (which it totally ignores). We are not aware of any other way to solve this problem.
Our solution corresponds to:
- 71637e7c617f
- Initialize registers to ( 2 _ 0 1 ) ( 2 2 ).
- 09 ((science 9))
- Jump to the right place to start (skip the increase of registers)..
- 01 ((science 1))
- Make sure speed is normal.
- 7b72616b617b61
- Increase registers.
- 01 ((science 1))
- Make sure speed is normal (this is where the previous (science 9) lands).
- 2b ((math 0 2 3))
- Set m[i + 1] = m[0] + m[i] = 1 + m[i].
- 0a ((science x))
- If we didn't write a zero, jump to the first (science 1) operation, to iterate, otherwise continue on the next instruction.
- 6400 ((physics 4) (science 0))
- Since we just wrote a zero, we can stop, as we have all possible values loaded in memory. We rotate registers (to make m[sR[0]] non-zero) and halt.
clearreg (CRR)
We got 97 points:
727f307c7e7d6e7b00
We found that 727f7c7e7d6e7b sets all registers to zero. However, we needed a way to get non-zero in M[0] in order to halt. That is easy: we just insert a math operation at a point where we have a 0 in any of the dR registers. So our solution becomes 727f, (math 1 0 0) 7c7e7d6e7b00.
stop (STP), stop1 (ST1), stop127 (S27), stop128 (S28)
We got 10, 10, 20 and 15 points for stop, stop1, stop127 and stop128 respectively.
For stop we used the trivial solution: rotate to get sR[0] = 1 (hence M[sR[0]] > 0) and we halt ((science 0)).
For stop1, stop127 and stop128 we used exactly the same solution:
7f7f7f7f7f7f00
This is just like stop, but we use 6 rotates/adds to make sure we get sR[0] > 0 (hence M[sR[0]] > 0). Actually this could be shorter, but we were given the maximum points, so we don't want to waste time improving it.
swapreg (SR2)
We got 50 points with a 100% GA solution:
71616f7000
swapmem (SWM)
We got 40 points with a solution made-by-hand:
2a633000
This corresponds to (math 0 2 2), (physics 3), (math 1 0 0), (science 0).
swapreg (SWR)
We got 50 points:
766200
The 7662 was found by the GA and the 00 ((science 0)) added to cause it to stop.
BLACK
We got stuck here.
We tried using an optimized (in the sense that it would avoid duplicated computations) backtracker (written by Alejo in Scheme), another backtracker (written by Sergio in Common Lisp) as well as GA (written by Nelson in C) to no avail. The backtrackers only manage to solve the first puzzle and the GA manages to solve the first and the second.
We suspect we are missing some obvious property of these machines that would greatly simplify our task.
BASIC
We finished the loop in Basic using two variables, one for each digit. This wasn't that difficult so we didn't use any tools to assist us (other than a text editor, of course!).
You can see our code here:
CIRCS
There were three problems:
MULT implementation is here: http://freaks-unidos.net/svn/icfp/src/ohmega/mult.2d
and REVERSE is here: http://freaks-unidos.net/svn/icfp/src/ohmega/reverse.2d
The problemas were rather easy. The difficulty came from the fact that programming in the ASCII-art-based language was really painful (mostly because editing it was really slow, not because of the cognitive effort), so developing the raytracer seemed like a very long task.
Last update: 2007-07-02 (Rev 11951)