Biorąc pod uwagę stan kwadratowej siatki Game of Life, określ, czy mogła ewoluować z dowolnego poprzedniego stanu, czy mogła zostać stworzona. Oznacza to, czy państwo jest stanem „Garden of Eden” .

Wejście

Kwadratowa siatka stanów, gdzie 1 oznacza „żywy”, a 0 oznacza „martwy”. Możesz wybrać dowolne dwa wyróżniające się symbole zamiast 0 i 1, jeśli chcesz.

Długość boku siatki nie będzie wynosić zero, ale może być dowolną liczbą naturalną 1 <= N <= 20.

Każda lub wszystkie komórki poza siatką wejściową mogą być żywe w tym pokoleniu, a niektóre lub wszystkie z nich mogły być żywe w poprzednim pokoleniu. Wszechświat, który należy wziąć pod uwagę, jest nieskończony, więc nie ma warunków brzegowych. Krawędzie wejścia nie są krawędziami wszechświata. W szczególności siatka się nie zawija.

Dane wejściowe mogą mieć postać łańcucha rozdzielanego wierszem lub pojedynczego łańcucha. Jeśli chcesz, możesz wziąć długość boku lub obszar siatki jako dodatkowe dane wejściowe (przed lub po siatce).

Dopuszczalne formaty wejściowe:

010,101,010

010101010

010
101
010
3 010101010

Wynik

„Utworzono”, jeśli nie ma możliwego stanu poprzedniego (w tym stanów większych niż siatka wejściowa), który doprowadziłby do stanu wejściowego następnej generacji.

„Rozwinięty”, jeśli istnieje co najmniej jeden możliwy poprzedni stan (w tym stany większe niż siatka wejściowa), który doprowadziłby do stanu wejściowego następnej generacji.

Możesz użyć dowolnych dwóch rozróżnialnych ciągów lub liczb zamiast „Utworzono” i „Rozwinięto”, jeśli chcesz.

Zauważ, że możliwy poprzedni stan nie musi różnić się od danych wejściowych. Jeśli stan ma się jako następna generacja, należy go uznać za rozwinięty.

Przypadki testowe

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

Utworzony przypadek testowy pochodzi ze strony Game of Life Achima Flammenkampa .

Uwaga

Dzięki płaskowce do pisania to wyzwanie i przyjął go z tutaj

Java - 1254 bajty - bardzo słabe rozwiązanie

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

Przyjmuje dane z wiersza poleceń.

Co to robi

Żadnych wymyślnych sztuczek, po prostu rozwiązanie brutalnej siły. Przechodzi przez każdą możliwą początkową tablicę w rozmiarze X, Y i iteruje ją raz przez algorytm Game of Life i sprawdza ją na tablicy wejściowej. Zajmuje to BARDZO długi czas, ponieważ każda tablica o rozmiarze x przez y ma 2 ^ (x * y) możliwych kombinacji. Uruchomienie tablicy 4x5 zajęło prawie 10 minut. Głupio głupio jak na coś prostszego niż jest.

Jeśli jest możliwe, że była to rozwinięta plansza, drukuje „ewoluowała”, a jeśli nie mogła być ewoluowana, drukuje „stworzona”.