Vida: ¿creada o evolucionada?

17

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í.

Christopher
fuente
66
¿Alguna limitación de complejidad? Para una entrada de tamaño m-por- n, si pruebo todos 2^(m*n)los estados iniciales posibles , la complejidad del programa será grande, pero resuelve el problema simplemente comprobando si el resultado coincide con la entrada
Luis Mendo
@Luis para la entrada? 20 por 20. ¿Para el programa? no
Christopher
2
No puedo ser considerado para jugar golf, pero aquí hay una implementación eficiente que utiliza un solucionador de programación de enteros incluido en SageMath.
orlp
Supongo que no importa si el estado anterior (si existe) es un estado del Jardín del Edén.
HyperNeutrino
@ ¡Hola, no! Solo lo que obtienes
Christopher

Respuestas:

3

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".

tuskiomi
fuente
¡Agradable! Estoy de acuerdo en que es muy pobre para la complejidad del tiempo, pero bueno, es el único (no plagarizado) hasta ahora, ¡así que probablemente obtendrá la recompensa! Suponiendo que orlp no publica el optimizado :)
HyperNeutrino
2
@HyperNeutrino "Ganaste esta ronda, pero tengo un as en mi hoyo". - Phillip J. Fry
tuskiomi
¡Felicitaciones, esta solución se lleva la recompensa! :)
HyperNeutrino
@HyperNeutrino Sé que no es inteligente, y probablemente no sea lo que estás buscando, y esperaba inspirar otras soluciones con esta solución fácil de superar, pero espero que sea lo suficientemente bueno.
tuskiomi
1
también -1 no golfizado (jaja es broma, obtuviste un +1 pero aún así, se podían hacer golf triviales);)
HyperNeutrino