Жизнь: создана или развита?

17

Учитывая состояние квадратной сетки Игры Жизни, определите, могла ли она эволюционировать из какого-либо предыдущего состояния или могла быть только создана. То есть, определить, является ли штат «райским садом» .

вход

Квадратная сетка состояний, где 1 означает «живой», а 0 - «мертвый». Вы можете выбрать любые два различимых символа вместо 0 и 1, если хотите.

Длина стороны сетки не будет нулевой, но может быть любым натуральным числом 1 <= N <= 20.

Любая или все ячейки вне входной сетки могут быть живы в этом поколении, и любая или все из них, возможно, были живы в предыдущем поколении. Рассматриваемая вселенная бесконечна, поэтому нет граничных условий. Края входа не являются краями вселенной. В частности, сетка не переносится.

Входные данные могут быть в форме строки с разделителями строк или одной строки. Если вы хотите, вы можете взять длину стороны или площадь сетки в качестве дополнительного ввода (до или после сетки).

Допустимые форматы ввода:

010,101,010

010101010

010
101
010
3 010101010

Выход

«Создан», если нет возможного предыдущего состояния (включая состояния, большие, чем входная сетка), которое привело бы к входному состоянию в следующем поколении.

«Развивается», если существует хотя бы одно возможное предыдущее состояние (включая состояния, большие, чем входная сетка), которое привело бы к входному состоянию в следующем поколении.

При желании вы можете использовать любые две различимые строки или числа вместо «Создано» и «Развито».

Обратите внимание, что возможное предыдущее состояние не обязательно должно отличаться от ввода. Если государство имеет себя в качестве следующего поколения, то оно должно рассматриваться как развитое.

Контрольные примеры

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

Созданный контрольный пример взят со страницы игры жизни Ахима Фламменкампа .

Заметка

Спасибо Trichoplax за написание этого задания, и я принял его отсюда

Кристофер
источник
6
Есть ли какие-то сложности? Для ввода размера m-by- n, если я протестирую все возможные 2^(m*n)начальные состояния, сложность программы будет большой, но она решит проблему, просто проверив, соответствует ли результат вводу
Луис Мендо,
@ Луис для ввода? 20 на 20. Для программы? нет
Кристофер
2
Я не могу обойтись без него, но вот эффективная реализация, использующая готовый решатель целочисленного программирования, включенный в SageMath.
orlp
Я предполагаю, что не имеет значения, является ли предыдущее состояние (если оно существует) состоянием Эдемского сада?
HyperNeutrino
@ Гипер Нету! Только то, что вы получаете
Кристофер

Ответы:

3

Java - 1254 байта - очень плохое решение

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

Требуется ввод через командную строку.

Что оно делает

Здесь нет хитростей, просто решение грубой силы. Он проходит каждую возможную начальную доску размером X, Y и повторяет ее один раз через алгоритм Game of Life и проверяет ее по входной доске. Это занимает ОЧЕНЬ много времени, так как каждая доска размером x от y имеет 2 ^ (x * y) возможных комбинаций. Потребовалось почти 10 минут, чтобы запустить доску 4х5. Глупо глупо за то, что проще, чем есть.

Если возможно, что это была усовершенствованная доска, она печатает «развитая», а если она не могла быть развита, она печатает «созданная».

tuskiomi
источник
Ницца! Я согласен, что это очень плохо для временной сложности, но эй, это пока единственный (не плагиат), так что он, вероятно, получит награду! Предполагая, что orlp не публикует оптимизированный :)
HyperNeutrino
2
@HyperNeutrino "Вы выиграли этот раунд, но у меня есть туз в моей дыре." - Филипп Дж. Фрай
tuskiomi
Поздравляем, это решение получает награду! :)
HyperNeutrino
@ HyperNeutrino Я знаю, что это не умно, и, вероятно, не то, что вы ищете, и я надеялся вдохновить другие решения с помощью этого легко победимого, но я надеюсь, что это было достаточно хорошо.
Tuskiomi
1
также -1 не игра в гольф (хаха, шучу, ты получил +1, но все же, тривиальные игры в гольф могут быть сделаны);)
HyperNeutrino