Étant donné l'état d'une grille Game of Life carrée, déterminez si elle aurait pu évoluer à partir de n'importe quel état précédent, ou aurait seulement pu être créée. Autrement dit, déterminez si l'État est un État "Jardin d'Eden" .

Contribution

Une grille carrée d'états, 1 indiquant "vivant" et 0 indiquant "mort". Vous pouvez choisir deux symboles distincts au lieu de 0 et 1 si vous le souhaitez.

La longueur du côté de la grille ne sera pas nulle, mais peut être n'importe quel nombre naturel 1 <= N <= 20.

Une ou toutes les cellules en dehors de la grille d'entrée peuvent être vivantes à cette génération, et toutes ou toutes peuvent avoir été vivantes dans la génération précédente. L'univers à considérer est infini, il n'y a donc pas de conditions aux limites. Les bords de l'entrée ne sont pas les bords de l'univers. Plus précisément, la grille ne s'enroule pas.

L'entrée peut être sous la forme d'une chaîne délimitée par des lignes ou d'une chaîne unique. Si vous le souhaitez, vous pouvez prendre la longueur du côté ou la zone de la grille comme entrée supplémentaire (avant ou après la grille).

Formats d'entrée acceptables:

010,101,010

010101010

010
101
010
3 010101010

Production

"Créé" s'il n'y a aucun état précédent possible (y compris des états plus grands que la grille d'entrée) qui conduirait à l'état d'entrée sur la prochaine génération.

"Evolved" s'il existe au moins un état précédent possible (y compris des états plus grands que la grille d'entrée) qui conduirait à l'état d'entrée sur la prochaine génération.

Vous pouvez utiliser deux chaînes ou nombres distincts au lieu de "Créé" et "Évolué" si vous le souhaitez.

Notez que l'état précédent possible n'a pas besoin d'être distinct de l'entrée. Si un État a lui-même la prochaine génération, alors il doit être considéré comme évolué.

Cas de test

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

Le scénario de test créé est extrait de la page Game of Life d' Achim Flammenkamp .

Remarque

Merci à trichoplax d'avoir écrit ce défi et je l'ai adopté à partir d' ici

Java - 1254 octets - une très mauvaise solution

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;}}

Il prend l'entrée via la ligne de commande.

Ce qu'il fait

Pas de trucs sophistiqués ici, simplement une solution de force brute. Il passe par tous les tableaux de départ possibles de taille X, Y et l'itère une fois via l'algorithme Game of Life et le compare au tableau d'entrée. Cela prend très longtemps car chaque planche de taille x par y a 2 ^ (x * y) combinaisons possibles. Il a fallu près de 10 minutes pour exécuter une planche 4x5. Bêtement stupide pour quelque chose de plus simple que ça.

S'il est possible qu'il s'agisse d'une carte évoluée, elle imprime "évoluée" et si elle n'a pas pu être évoluée, elle imprime "créée".