D @ ICFP 2012

[bearophile]

Kazuhiro Inaba ("Dark Integers" Team) has reached position 6 in 
the prestigious ICFP 2012, it's not bad:

http://www.kmonos.net/repos/icfpc12/wiki?name=icfpc12

Code:
http://www.kmonos.net/repos/icfpc12/dir?ci=tip

Info on the contest and its results:
http://www.youtube.com/watch?v=5TCqUU3-GT0
http://icfpcontest2012.wordpress.com/

The winning entry was in C++, by "Frictionless Bananas" team:
http://www.sawicki.us/icfp/2012/

The C++ code contains some interesting parts:

>To represent multiple states efficiently, my program stores 
>diffs between states. Only one full grid is stored at a time. 
>Executing a robot command updates the grid and produces a diff 
>that represents the changes needed to restore the previous 
>state. Applying the diff will undo the changes and produce the 
>opposite diff that can be used to redo the changes. An entire 
>tree of states can be represented by storing each state as a 
>diff from an earlier state in the tree. To improve the 
>performance when reconstructing a desired state from diffs, 
>several diffs can be merged together to produce a diff that will 
>undo or redo several robot commands at once. My program merges 
>diffs in such a way that n commands can be undone/redone by 
>applying O(log n) diffs.<

>To avoid the exponentially increasing size of the state space, 
>states are grouped into buckets with similar characteristics. 
>Only the first state to be reached in a given bucket is kept; 
>other states in the same bucket are discarded and not explored 
>further.<

The C++ code, it's nice, about 67 KB:
http://www.sawicki.us/icfp/2012/submission2.tar.gz

Bye,
bearophile