Życie: stworzone czy ewoluowane?

17

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

Krzysztof
źródło
6
Jakieś ograniczenia złożoności? W przypadku danych wejściowych o rozmiarze m-by- n, jeśli przetestuję wszystkie możliwe 2^(m*n)stany początkowe, złożoność programu będzie duża, ale rozwiązuje problem, sprawdzając tylko, czy wynik pasuje do danych wejściowych
Luis Mendo
@Luis dla wejścia? 20 na 20. Do programu? Nie
Christopher
2
Nie mogę się na to zgodzić, ale tutaj jest wydajna implementacja przy użyciu gotowego solvera programistycznego do programowania liczb całkowitych dołączonego do SageMath.
orlp
Zakładam, że nie ma znaczenia, czy poprzedni stan (jeśli istnieje) jest stanem Garden of Eden?
HyperNeutrino
@Hyper nope! Tylko to, co dostajesz
Christopher

Odpowiedzi:

3

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

tuskiomi
źródło
Ładny! Zgadzam się, że jest bardzo kiepski ze względu na złożoność czasu, ale hej, jak dotąd jest to jedyny (nieplagaryzowany), więc prawdopodobnie dostanie nagrodę! Zakładając, że orlp nie opublikuje zoptymalizowanego :)
HyperNeutrino
2
@HyperNeutrino „Wygrałeś tę rundę, ale mam asa na swoim dołku”. - Phillip J. Fry
tuskiomi
Gratulacje, to rozwiązanie wymaga nagrody! :)
HyperNeutrino
@HyperNeutrino Wiem, że to nie jest sprytne i prawdopodobnie nie to, czego szukasz, i miałem nadzieję zainspirować inne rozwiązania tym łatwym do pokonania, ale mam nadzieję, że było wystarczająco dobre.
tuskiomi
1
także -1 nie grałem w golfa (haha żartujesz, że masz +1, ale wciąż można zrobić trywialne golfa);)
HyperNeutrino