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