Garden of Eden
a reference solution

See Garden of Eden for a complete description of the problem.

The purpose of this document is to further describe the problem for people who cannot figure out how to use the inputs to define and execute the model for a solution. When I first read the problem described by Miquel Revilla, I just couldn't seem to grasp how the arguments defined the model. The point I was missing was that the sample table, that describes eight inputs with eight possible outputs, was just an example of a rules table, that could be reconstructed from the bits of the automaton identifier. Furthermore, the automaton is defined by this number, which actually defines the rules that will be applied to each generation of the cells to get the next generation.

Therefore, the inputs to the problem could better be defined like this...

for each line of inputs ...

• Arg 1: an 8 bit number that identifies the evolution rules of the automaton
• Arg 2: the number of cells in the automaton
• Arg 3: the goal state that must be either found to be reachable from another state or not reachable from any other state.

My example does not adhere to the input specification of the problem, in that I did not bother to read and parse multiple lines of input from stdin. Rather, I simply take 3 command line arguments, compute the result from those arguments, and exit. My example still serves to describe the computational steps involved in solving the problem, and it can be used as a reference to further understand the parameters of the problem and the purpose and handling of the input arguments.

my reference implementation

Of course, there is no warrantee of correctness, and optimization may be possible. This example is offered only as a reference to clarify the problem.

Happy computing!
Douglas Toltzman