For most cellular automata there are configurations (states) that are unreachable: no state will produce them by the application of the evolution rules. These states are called Gardens of Eden for they can only appear as initial states. As an example consider a trivial set of rules that evolve every cell into 0; for this automaton any state with non-zero cells is a Garden of Eden.
In general, finding the ancestor of a given state (or the non-existence of such ancestor) is a very hard, compute intensive, problem. For the sake of simplicity we will restrict the problem to 1-dimensional binary finite cellular automata. This is, the number of cells is a finite number, the cells are arranged in a linear fashion and their state will be either 0 or 1. To further simplify the problem each cell state will depend only on its previous state and that of its immediate neighbors (the one to the left and the one to the right).
The actual arrangement of the cells will be along a circumference, so that the last cell is next to the first.
|[i-1]||[i]||[i + 1]||State|
|0||0||0||0||0 * 20|
|0||0||1||1||1 * 21|
|0||1||0||0||0 * 22|
|0||1||1||1||1 * 23|
|1||0||0||1||1 * 24|
|1||0||1||0||0 * 25|
|1||1||0||1||1 * 26|
|1||1||1||0||0 * 27|
Notice that, with the restrictions imposed to this problem, there are only 256 different automata. An identifier for each automaton can be generated by taking the New State vector and interpreting it as a binary number (as shown in the table). For instance, the automaton in the table has identifier 90. The Identity automaton (every state evolves to itself) has identifier 204.
The output for each test case must be in a different line.
0 4 1111 204 5 10101 255 6 000000 154 16 1000000000000000
GARDEN OF EDEN REACHABLE GARDEN OF EDEN GARDEN OF EDEN