digitalmars.D.announce - D ICFP 2012
- bearophile (15/33) Sep 13 2012 Kazuhiro Inaba ("Dark Integers...
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
Sep 13 2012