Egér a Marson - ICFP contest 2012
v0.9

update 2: In the second round, we were also 13th, but on the final round (in which you could get 10 times as much points as in the first two rounds together, on only 2 maps) we fell back to the 34th place, most probably because we run out of time after handling only a very small portion of the map. However, we got the Judges' prize! So, it's official: we are an extremely cool bunch of hackers, hohoho hurray!

If you met me at ICFP and want contact, now there is a contact address: moire.misszio at gmail

update 1: The results of the first round are in: We were very bad (and eliminated) in the lightning competition, however, we are at the 13th place in the full competition, which is, honestly, almost too good to believe... However, our program is rather slow, which will be a disadvantage on larger maps.

As usual, the team consisted of B, V and H (all our first names start with the same letter, so some creativity was necessary to come up with distinct letters). Unlike all previous year, this year we were located in V's place, which is a nicer and bigger place than mine (me = H). Though my sound system is way better :)

Unfortunately, we still used three different languages (and three different operating systems, though that did not cause any serious issues). B used Python (though he toyed with the idea of node.js for an hour or so), V used Pascal, and H used Haskell (the alliteration is coincidental). This is of course not at all ideal - basically all three of us wrote completely independent and redundant code - but we still had fun. Both submissions were in Haskell, though, and this writeup will be also mostly from the Haskell perspective.

Before diving into the story, we have some code, in the unlikely case someone is interested:

• Haskell submission
• Pascal code

I have a git log, which will help me reconstructing the events; memories are not perfect, partly due to the 44 cans = 22 litres of beer we (mostly B and H) consumed during the contest - I think we would have a very good position if the points were multiplied by the number of beers swallowed :). Except that some hours in the first day are missing, since I, the newbie git user naively thought that the command "git commit -m message" will, you know, actually commit the changes, like a normal version control system? Alas, it didn't...

Anyway, according to the logs, I had a working interactive (simple console based) boulderdash game at T+6 hours. Nice roguelike style. This is actually commited since I added some new source file. Then I discovered that the git log is a bit short at T+9 hours... At T+11 hours I discovered the wonders of ANSI color codes, which is the second new thing I learned this year (after, well, the logic school represented by git). Color in the terminal is very cool, I have to admit. First I only used it for the water level (blue background, of course), then later for everything.

According to the logs, we had the first automatic robot at T+17 hours. This was extremely simple, just a depth-first search for 5 steps with some heuristic scoring (like lambdas collected, bonus points for not dying death penalty for dying). Our lightning submission was not much more complicated either: It used a pruned sequence of small DFS steps (of length 3).

The inner workings of this system (I cannot speak for the others...) was based on the idea that everything is pure functional, except the map of the mine, which was modelled as a mutable array (stupidly, a normal Haskell array, not even an unboxed character array, which must have costed us a lot of wasted CPU time, which was a rather critical resource...). This existed as a singleton state, and every change made was also undoed after. Continuation-passing style came into play quite naturally (make changes, call continuation, undo changes). I was quite happy with this idea (until much later I put a hard timeout on some part of the code, then wondered why impossible things happen randomly...).

I probably slept after the lightning submission. There were a few unplanned sleep sessions during the contest, to be honest... But V has a really nice sofa, and I brought a very nice blanket :)

After sleeping (T+29), I added the feature of interactively playing back a given sequence of moves, going back-and-forth in history using the left/right cursor keys. This was a perfect opportunity to introduce zippers in the code. Just after that trampolines were implemented. A few hours later later (T+36), beards and razors are supported (I mean, in the simulator, not in the solver...) with fancy ANSI colors and all. Then I crashed while thinking about search algorithms.

At T+44, I realized that it is so much easier to think about search algorithms after few hours of sleep and being sober. An A* implementation (or at least something similar) quickly followed. I have to admit here that B had an A* in Python quite a few hours earlier :)

At T+52, I had the first version of the "planner". It was a portion of code whose task was to, ehm, plan the future movements... The "deep thinking" this planner did was to try out different combinations of simpler search algorithms after each other. This was the moment when the hard timeout vs. singleton state bug manifested, though only I realised the reason later.

At T+53, I started the ongoing task of optimizing the code a bit, since it was not performing too bad for an ad-hoc heuristic, but it was rather slow. This mostly involved the data structure storing positions of lambdas and beards: originally a Set, then an IntSet (which was not a clear win because of the CPU time spent converting between an Int and 2D vector), finally at the end a 2-level radix tree consisting a Map of IntSet-s.

(I also wanted to use a Trie for the branching multiverse structure of the simulated future, but I was too lazy to think about how it actually intertwines the mutable state...).

Around this points, the commit messages start to be less descriptive (like "live fast!", "something", "not that bad" and "whatever?"). It seems that I slept Monday dawn (actually, I even remember sleeping Monday dawn!).

The final submission also included "last chance": when the planner decided it doesn't have a sensible plan anymore, and thus should abort, we tried a last chance strategy (which was actually quite the same as the lightning submission strategy :). The final version was also much faster than earlier version, but still too slow. Well, we will see. I still dare to compete with the fellow functional programmers on a "lambdas collected multiplied by blood-alcohol level" basis! Though Haskell is probably much more forgiving in this context, than, say, Befunge...

During the same 72h period, B and V also wrote their simulators, interactive visualizations (V's one was even graphical!), and simple strategies in Python and Pascal, respectively. V also wrote a memory manager (ahh, the familiar old scent of manual memory management... I think next year we should try x86 assembly, that would be some serious fun!¹ Not speaking about the huge speed advantage!) In the back of my mind there is also something about Freepascal/Lazarus Windows/Linux compatibility problems, though part of that may have been caused by the memory manager...

[¹ actually, I'm quite tempted to seriously do that - but we probably would have the same problem as with Haskell]