Dado el estado de una cuadrícula de Juego de Vida cuadrada, determine si podría haber evolucionado desde un estado anterior, o si solo podría haberse creado. Es decir, identificar si el estado es un estado del "Jardín del Edén" .

Entrada

Una cuadrícula cuadrada de estados, con 1 que indica "vivo" y 0 que indica "muerto". Si lo desea, puede elegir dos símbolos distinguibles en lugar de 0 y 1.

La longitud lateral de la cuadrícula no será cero, pero puede ser cualquier número natural 1 <= N <= 20.

Cualquiera o todas las celdas fuera de la cuadrícula de entrada pueden estar vivas en esta generación, y cualquiera o todas ellas pueden haber estado vivas en la generación anterior. El universo a considerar es infinito, por lo que no hay condiciones límite. Los bordes de la entrada no son los bordes del universo. Específicamente, la cuadrícula no se ajusta.

La entrada puede tener la forma de una cadena delimitada por filas o una sola cadena. Si lo desea, puede tomar la longitud lateral o el área de la cuadrícula como una entrada adicional (antes o después de la cuadrícula).

Formatos de entrada aceptables:

010,101,010

010101010

010
101
010
3 010101010

Salida

"Creado" si no hay un estado anterior posible (incluidos los estados más grandes que la cuadrícula de entrada) que conduciría al estado de entrada en la próxima generación.

"Evolucionado" si existe al menos un posible estado anterior (incluidos los estados más grandes que la cuadrícula de entrada) que conduciría al estado de entrada en la próxima generación.

Puede usar dos cadenas o números distinguibles en lugar de "Creado" y "Evolucionado" si lo desea.

Tenga en cuenta que el posible estado anterior no necesita ser distinto de la entrada. Si un estado se tiene a sí mismo como la próxima generación, entonces debe considerarse evolucionado.

Casos de prueba

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

El caso de prueba creado se toma de la página Juego de la vida de Achim Flammenkamp .

Nota

Gracias a Trichoplax por escribir este desafío y lo adopté desde aquí.

Java- 1254 bytes- una solución muy pobre

import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
if(r==x*y){System.out.println("evolved");return;}}System.out.println("created");}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

Toma entrada a través de la línea de comando.

Que hace

No hay trucos sofisticados aquí, simplemente una solución de fuerza bruta. Atraviesa todos los tableros iniciales posibles de tamaño X, Y y lo itera una vez a través del algoritmo Game of Life y lo compara con el tablero de entrada. Esto lleva mucho tiempo, ya que cada tabla de tamaño x por y tiene 2 ^ (x * y) combinaciones posibles. Tomó casi 10 minutos ejecutar una placa de 4x5. Estúpidamente tonto por algo que es más simple de lo que es.

Si es posible que fuera un tablero evolucionado, imprime "evolucionado", y si no pudo haber sido evolucionado, imprime "creado".