Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Official submission:
submission.tar.gz
(mistakenly contains 64-bit binary)
Corrected submission:
submission2.tar.gz
(contains 32-bit binary)
The Frictionless Bananas had only one team member this year. This page describes my 2012 ICFP Programming Contest entry.
My submission is written in C++. It contains a representation of the mine state, a simulation of the rules for updating the state in response to robot commands, and a strategy for finding a good sequence of commands. I also implemented a text-only visualization of the mine state using ANSI escape sequences for color and a tool to interactively control the robot.
To update the state efficiently, my program stores a set of locations containing falling rocks and another set of locations containing growing beards. This makes it possible to execute a robot command without scanning the entire grid.
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.
My program uses breadth-first search to find mine states reachable from a given state. 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.
States are primarily grouped based on robot position, with different robot positions falling in different buckets. Thus the search is focused on reaching as many positions as possible using as few commands as possible. The buckets are further subdivided based on whether the last command was Wait, Shave, or Move, making it possible for the robot to follow paths that require waiting for a falling rock or shaving a beard that blocks the path. An early version of my program used the number of collected lambdas to further subdivide the buckets, allowing the search alone to find reasonable solutions for some maps.
My main strategy consists of continually refining a “plan” for the robot to execute. The key idea was to find a representation of the plan where incremental changes can produce incremental improvements in the resulting solution.
A plan consists of a set of positions for the robot to visit. To execute the plan, a breadth-first search is performed from the current state until the search reaches a position in the plan that has not yet been visited. The search proceeds again from that state, continuing until it is not possible to reach any more positions in the plan. It is a greedy strategy that always travels towards whatever position can be reached in the fewest steps.
By default, any point-earning position (a lambda or an open lift) is automatically considered part of the plan, including lambdas that dynamically appear due to shattered higher order rocks. Additional positions can be explicitly added to the plan, for example to force the robot to excavate under a rock to allow it to fall. Plans can also contain two types of relationships between positions: a position can be excluded from the plan until another position in the plan has been visited, and a position can be required to be the very next step after another position.
My program starts with an empty plan (containing only the default point-earning positions and no relationships) and continually makes random modifications, keeping the changes if the score is improved and sometimes keeping the changes if the score remains the same. It repeats this in a loop until SIGINT is received.
Incrementally updating a plan carries the risk of getting stuck in a local maximum when a different set of initial choices would have resulted in a better solution. To combat that risk, my program works on multiple plans in parallel. A list of 16 plans is maintained, with different amounts of time spent on each plan: 25% of the time is spent on the first plan, 25% of the remaining 75% is spent on the second plan, etc. Plans are kept sorted based on score so that higher scoring plans receive more time.
These are the highest scores I have seen from running my submission on each of the sample maps with a 150 second time limit. Note that due to randomness my program does not always achieve the same score. In particular, it usually doesn’t solve flood4.
My program achieved a score of 4527 for beard2, which is higher than the highest score of 4522 submitted to the validator during the contest.
My submission made it into the top ten in Round 1 so I don’t know my official scores, but these are the best scores I have seen with a 150 second time limit.
Just for fun, I ran my final submission on the lightning round maps. (I didn’t make a lightning round submission.)
After the contest, I discovered a couple of bugs in my simulation:
Luckily neither problem is severe. They just cause the robot to be a little more cautious than necessary in obscure situations. Of course it is possible to construct a map where the solution depends on the precise behavior (beard5 seems to be such a map), but hopefully it will make little difference in the maps used for judging.
I implemented a simple text-based program to interactively control the robot. It supports undo and redo, thanks to the diffs provided by the simulation engine. A binary is included in the corrected submission package submission2.tar.gz. Run with “./play mapfile”.
I built a statically linked binary on my own machine and submitted it (submission.tar.gz) without testing it on a virtual machine. Only after the contest did I realized that a 32-bit binary was required but I submitted a 64-bit binary. I am hopeful the judges will be willing to compile the supplied source code instead. All it takes on the Debian Testing image is “sudo apt-get install g++” and “./build” in the src directory.
I prepared a corrected submission containing a 32-bit binary (submission2.tar.gz). It also contains binaries for the interactive robot control tool (“./play mapfile”) and a test version of the lifter that prints information about its progress (“./test < mapfile”).
This paper (pdf) lays out a framework for proving NP-hardness of various classic Nintendo games like Super Mario Bros. We can apply the same framework to lambda mining. The framework requires constructing a few “gadgets” that can be combined to form a reduction from 3-SAT—see the paper for details. Below are the necessary constructions for lambda mining.
The Variable gadget corresponds to assigning a value of true or false to a particular variable. When the robot enters from the bottom, it can make a choice to exit either through the top left or top right, permanently blocking the other exit.
## # ## ## # ## # * * # # ### # # # ### ### ### ###
The Clause gadget corresponds to a clause being true if any of the variables in the clause has the required value. If the robot enters from any of the three lower paths, it can release a rock which unlocks the upper path.
# ###### # # ###### # # * # ##*####### ##*####### ##* # ##** # ##*** # ##**** # ##***** # ##****** # ##*******# ##*##*##*# # .# .# .# # ## ## ## # ## ## ##
The Crossover gadget allows two passages to cross without leaking into one another. If the robot enters from either of the bottom passages, it can only exit through the opposite top passage.
## ########################## ## ## ####################*##### ## ## .##### ## ####################### *### ## #########################*### ## #########################*### ## #### *### ## #### ####################*### ## #### ##################*#*### ## #### ##################***### ## #### ##################..* ## #### ############* #*# #### #### ############*#######*###### #### ############*#######*###### #### #### *#######*###### ####### ## ####*#######. ## ######## #####*####### ### ## ######### ######*####### ### ## ######## #####*#*##### ### ## ####*## ## ####***######### ## ####. #### *..######### ## ## ########## #*# ## ## ##############*########### ## ## ##############*########### ## ## .########### ## ## ############## ########### ## ## ############## ########### ## ## ############## ########### ## ## ########################## ##
So, this year’s task is provably hard!
(In retrospect it would have been easier to use the Traveling Salesman Problem combined with a falling rock or growing beard that makes the lift inaccessible after a specific number of moves, but constructing the gadgets was more fun.)