• bearophile (15/33) Sep 13 2012 Kazuhiro Inaba ("Dark Integers" Team) has reached position 6 in

"bearophile" <bearophileHUGS lycos.com> writes:

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