2 Dec 2011 dangermaus   » (Journeyer)

Mauri is born! Marti now has a brother and we are all very happy to welcome him in our family :-) Might the source be with you, Luke.

In the following, some updates on our lone hackerland journey:

Runaway Robot

Probably some smart people go straight to the correct solution. For me, I walked through all stages of enlightment. I first developed a maze parser in Frepascal, then got a brute force solver in place which could solve up to about maze level 120. The solver started taking long times for each new level (up to 6 hours). I am a bit out of gear right now as we moved house, lost connection to civilization for some time, and still have to reactivate the server room, which will move from pavement to cellar. I remembered that spartacusII server got burned in a similar challenge and decided to upgrade the algorithm as soon as possible. With dynamic programming I restricted a bit the solution space. A first attempt with combinations failed, I tried to debug the way I create combinations, but could not find the mistake. I rewrote the algorithm and got a working solver for levels up to 153. Then again, the solver was taking too much time. Finally, I got a sort of Zen flash and found a way to retrieve the solution, as it would be just popping out from the maze. The new solver could solve any maze in less than a second, and easily moved up to level 513. When it solved level 514 (a level noone has solved), and was waiting the one minute delay to avoid server pounding before the solution is submitted, I got very proud. Too much proud, as the server answered: "Your solution sucked, maximum level for this puzzle is 513". This site is amazing, it does not forget to teach you to be modest :-) The whole story can be seen in this graph as well.

I then decided to attack another puzzle, Mortal Coil. Adapting the parser and getting a brute force solver in place was easy, as Runaway prepared the path. But now I am stuck at level 68. I found papers on the Hamiltionian path problem, which is NP-complete and now need to think on how to divide and conquer it.

Other challenges

On the Hack Virtual Machine, I worked out the meaning of the two commands ^ and v and such knowledge lead to some progress: by analyzing the solution of Execution Style, I finally cracked Hello Small World! Also revision 34 of my Labyrinth program could solve the three mazes, though it required several submissions. In fact, the limit of 40'000 cycles is very tight. The version which solved the challenge could solve the reference maze I was using only in about 53'000 cycles. The Labyrinth program is based on a wall following algorithm published in Nievergelt's book about Algorithms and datatypes.

I found in the depths of Internet an almost complete map of the challenges and it is clear now that to achieve some breakthrough, I need to work out Spiral Bits. The encoding is a bit hard, but by printing out the spiral on a piece of A3 paper, it is possible to work it out with some patience. The pathfinder solver I developed follows the spiral but keeps staying on the side, so I have to think a way to balance it a bit. To debug the breadcrumbs left by the program, I use this magnifying glass.

On Khan Academy, I am close to the Copernicus Badge, but the Atlas Black Hole badge moved again out of range from 250 to 500 challenges...

Some other news

Unrelated to the previous topic, a deltasql patch to branch from existing tags for 1.4.1 is published here.

And do not forget to check the Wikileaks Spy Files!

Let me finally point at a news on the Voyager probes measuring Lyman-alpha radiation (here). Amazing piece of irons, the Voyager space probes!

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!