17
3
Given the state of a square Game of Life grid, determine whether it could have evolved from any previous state, or could only have been created. That is, identify whether the state is a "Garden of Eden" state.
Input
A square grid of states, with 1 indicating "alive" and 0 indicating "dead". You may choose any two distinguishable symbols instead of 0 and 1 if you wish.
The side length of the grid will not be zero, but may be any natural number 1 <= N <= 20.
Any or all of the cells outside the input grid may be alive at this generation, and any or all of them may have been alive in the previous generation. The universe to be considered is infinite, so there are no boundary conditions. The edges of the input are not the edges of the universe. Specifically, the grid does not wrap.
The input may be in the form of a row delimited string, or a single string. If you wish, you may take the side length or the area of the grid as an additional input (before or after the grid).
Acceptable input formats:
010,101,010
010101010
010
101
010
3 010101010
Output
"Created" if there is no possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.
"Evolved" if there exists at least one possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.
You may use any two distinguishable strings or numbers instead of "Created" and "Evolved" if you wish.
Note that the possible previous state need not be distinct from the input. If a state has itself as the next generation, then it should be considered evolved.
Test cases
010
101
010 Evolved
0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created
The created test case is taken from Achim Flammenkamp's Game of Life Page.
Note
Thanks to trichoplax for writing this challenge and I adopted it from here
6Any complexity limitations? For an input of size
m
-by-n
, if I test all possible2^(m*n)
initial states the program complexity will be large, but it solves the problem by just checking if the result matches the input – Luis Mendo – 2017-03-28T21:40:28.490@Luis for the input? 20 by 20. For the program? no – Christopher – 2017-03-28T21:43:10.880
2
I can't be arsed to golf it, but here is an efficient implementation using an off-the shelf integer programming solver bundled in SageMath.
– orlp – 2017-03-29T18:35:19.273I assume that it doesn't matter whether or not the previous state (if existent) is a Garden of Eden state? – HyperNeutrino – 2017-04-16T08:59:31.003
@Hyper nope! Only what you get – Christopher – 2017-04-16T13:58:57.020
This related Sandbox post has potentially helpful information.
– mbomb007 – 2017-05-17T13:58:30.387