Stabilna gra życia

19

Wyzwanie:

Biorąc pod uwagę macierz (lub tablicę 2d) 0 i 1 s, wypisz liczbę kroków, jakie musi upłynąć, aby gra życia Conwaya osiągnęła stan stabilny, lub -1, jeśli nigdy go nie osiągnie. Stan stabilny to stan, w którym żadne komórki nie są włączane ani wyłączane na każdym kroku. Gra musi działać w podanej matrycy, z połączoną górą i dołem oraz połączonymi bokami. (tzn. biorąc pod uwagę macierz 4x3 powinien on działać na torusie 4x3). Matryca wejściowa nie będzie większa niż 15x15.

Uwaga: Jeśli macierz zaczyna się w stanie stabilnym, wyjście powinno wynosić 0.

Próbki:

Wejście:

[[0,0,0],  
 [0,1,1],  
 [0,1,0]]

Wynik:

2)

Proces: (nie musi być wyświetlany)

[[0,0,0],
 [0,1,1],
 [0,1,0]]

[[1,1,1],
 [1,1,1],
 [1,1,1]]

[[0,0,0],
 [0,0,0],
 [0,0,0]]

Wejście:

[[0,0,1,1],
 [0,1,1,1],
 [0,1,0,0],
 [0,1,1,1]]

Wynik:

2)

Proces:

[[0,0,1,1],
 [0,1,1,1],
 [0,1,0,0],
 [0,1,1,1]]

[[0,0,0,0],
 [0,1,0,1],
 [0,0,0,0],
 [0,1,0,1]]

[[0,0,0,0],
 [0,0,0,0],
 [0,0,0,0],
 [0,0,0,0]]

Wejście:

[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

Wynik:

-1

Proces:

[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

[[0,0,0,0],
 [1,1,1,0],
 [0,0,0,0],
 [0,0,0,0]]

[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

powtarzanie na zawsze

Wejście:

[[0,0,0,0],
 [0,0,0,1],
 [0,1,1,1],
 [0,0,1,0]]

Wynik:

4

Proces:

[[0,0,0,0],
 [0,0,0,1],
 [0,1,1,1],
 [0,0,1,0]]

[[0,0,0,0],
 [1,0,0,1],
 [1,1,0,1],
 [0,1,1,1]]

[[0,1,0,0],
 [0,1,1,1],
 [0,0,0,0],
 [0,1,0,1]]

[[0,1,0,1],
 [1,1,1,0],
 [0,1,0,1],
 [1,0,1,0]]

[[0,0,0,0],
 [0,0,0,0],
 [0,0,0,0],
 [0,0,0,0]]

Wejście:

[[0,0,0,0],
 [0,1,1,0],
 [0,1,1,0],
 [0,0,0,0]]

Wynik:

0

Proces:

Stan początkowy jest stabilny.

Zasady gry w życie

Jeśli komórka, która jest wyłączona (0) znajduje się obok dokładnie trzech komórek na (1), jest włączona. W przeciwnym razie jest to pominięte. Jeśli komórka, która jest włączona, znajduje się obok 2 lub 3 na kwadratach, oznacza to, że jest włączona. W przeciwnym razie zostanie wyłączone.

poi830
źródło
Więc co powinno być generowane, jeśli wzorzec powtarza się na zawsze?
Pozew Fund Moniki w dniu
2
Możliwe formaty wejściowe? Jakieś granice rozmiarów matryc? Jeśli nie, co jeśli mamy matrycę 100 x 100? Powinieneś również umieścić w pytaniu podsumowanie zasad Gry o Życie, aby była ona samodzielna.
El'endia Starman
3
Rozumiem. Źle odczytałem jeden z przykładów. Kolejne pytanie - w którym momencie należy założyć, że nie staje się stabilne? Ponieważ jestem pewien, że istnieje wiele wzorów, które stabilizują się po setkach lub tysiącach iteracji. Jest nawet kategoria: Metuszelach
pozew fundacji Moniki
18
Jestem prawie pewien, że to wyzwanie polega zasadniczo na „rozwiązaniu problemu zatrzymania”.
Mego
6
Jako kontrprzykład pokazujący, że 250 pokoleń nie zawsze wystarcza: dla matrycy 15 na 14 pojedynczy szybowiec na pustej arenie potrzebuje 15 * 14 * 4 = 840 pokoleń, aby powrócić do swojego pierwotnego stanu. Jeśli koniec tej długiej ścieżki jest blokowany przez blok 2 na 2, szybowiec unicestwi pozostawiając stabilną konfigurację. Będzie to kilka rzędów przed końcem ścieżki, aby uniknąć zniszczenia szybowca na samym początku, ale nadal znacznie ponad 600 pokoleń przed stabilnością.
trichoplax

Odpowiedzi:

10

Mathematica, 130 129 bajtów

#&@@FirstPosition[Partition[CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,2^Length[Join@@#]],2,1],{x_,x_},0,1]-1&

Nie polecałbym wypróbowania więcej niż 4x4 wejść, ponieważ zajmie to wieczność (i dużo pamięci).

Wyjaśnienie

To po prostu symuluje grę w życie dla 2 N kroków, gdzie N jest liczbą komórek na wejściu. Gwarantuje to, że jeśli system ustabilizuje się, osiągniemy go. Następnie znajdujemy pierwszą parę kolejnych identycznych stanów w symulowanej historii.

Przejdźmy przez kod:

2^Length[Join@@#]

Oblicza to 2 N , ponieważ Join@@służy do spłaszczenia listy 2D.

CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,...]

To symuluje grę w życie dla 2 N pokoleń. Matryca 3x3 określa sąsiedztwo totalistycznego automatu 2D i 224jest liczbą reguł w standardowej grze w życie. Napisałem o tym, jak obliczyć tę liczbę tutaj na Mathematica.SE .

Partition[...,2,1]

Otrzymuje to wszystkie kolejne (nakładające się) pary pokoleń.

FirstPosition[...,{x_,x_},0,1]

Znajduje pierwszą parę identycznych generacji, domyślnie 0jeśli nie zostanie znaleziona żadna i ogranicza wyszukiwanie do głębokości 1. Jeśli taka para zostanie znaleziona, wynik jest jednak zwracany na liście. Więc używamy:

#&@@...

Aby wyodrębnić pierwszy element z tej listy ( 0nie ma to wpływu na domyślną wartość bycia atomem).

...-1

Na koniec odejmujemy jeden, ponieważ wyzwanie oczekuje 0wskaźników opartych -1na niepowodzeniach.

Martin Ender
źródło
8

Lua, 531 509 488 487 464 424 405 404 bajtów

Kto chce masowego poddania się? \ o /

Edycja: Poprawiłem, ale nie wiem już, jak grać w golfa, więc ... wyjaśnienia nadchodzą komentarze dodane :)

Zaoszczędzono ~ 60 bajtów przy pomocy @ KennyLau

małe golfowe cięcie o jeszcze jeden bajt poprzez zmianę nazwy ana, Yaby zapobiec wbudowanej konwersji szesnastkowej

function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]Y={}for i=1,#m do k=m[i]p[#p+1]=t(k)Y[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1Y[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=Y[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end

Nie golfił

function f(m)                -- takes a 2D array of 0 and 1s as input
  c={}                       -- intialise c -> contains a copy of each generation
  t=table.concat             -- shorthand for the concatenating function 
  ::z::                      -- label z, used to do an infinite loop
    c[#c+1]={}               -- initialise the first copy 
    p=c[#c]                  -- initialise a pointer to this copy
    a={}                     -- initialise the 2D array of adjacency
    for i=1,#m               -- iterate over the lines of m
    do
      k=m[i]                 -- shorthand for the current line
      p[#p+1]=t(k])          -- saves the current line of m as a string
      a[i]={}                -- initialise the array of adjacency for the current line
      for j=1,#k             -- iterate over each row of m
      do
                             -- the following statements are used to wraps at borders
        v=m[i%#m+1]          -- wrap bottom to top
        l=j%#k+1             -- wrap right to left
        w=m[(i-2)%#m+1]      -- wrap top to bottom
        h=(j-2)%#k+1         -- wrap left to right

        a[i][j]= v[l]        -- living cells are 1 and deads are 0
                +k[l]        -- just add the values of adjacent cells
                +w[l]        -- to know the number of alive adjacent cells
                +v[h]
                +v[j]
                +w[h]
                +w[j]
                +k[h]
      end
    end

    s=''                     -- s will be the representation of the current generation
    for i=1,#m               -- iterate over each line
    do
      k=m[i]                 -- shorthand for the current line
      for j=1,#k             -- iterate over each row
      do
        x=a[i][j]            -- shorthand for the number of adjacent to the current cell
                             -- the next line change the state of the current cell
        k[j]=k[j]>0          -- if it is alive
                and((x<2     --   and it has less than 2 adjacent
                    or x>3)  --   or more than 3 adjacent
                  and 0      --     kill it
                  or 1)      --     else let it alive
                or           -- if it is dead
                  (x==3      --   and it has 3 adjacent
                  and 1      --     give life to it
                  or 0)      --     else let it dead
      end
      s=s..t(k)              -- save the representation of the current line
    end
    for i=1,#c               -- iterate over all the generation done until now
    do                       
      if(s==t(c[i]))         -- if the representation of the current generation
      then                   -- is equal to one we saved
        return#c>i           -- check if it is the latest generation
              and-1          -- if it isn't, it means we are in a loop -> return -1
              or i-1         -- if it is, we did 2 generations without changing
                             --  -> return the number of generation
      end
    end
  goto z                     -- if we reach that point, loop back to the label z
end

Przypadki testowe

Oto kilka przypadków testowych

function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]a={}for i=1,#m do k=m[i]p[#p+1]=t(k)a[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1
a[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=a[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end




print(f({{0,0,0},{0,1,1},{0,1,0}}))
print(f({{0,1,0,0},{0,1,0,0},{0,1,0,0},{0,0,0,0}}))
-- 53 generation, 15x15, takes 50-100 ms on a bad laptop
print(f({{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
       {0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
       {0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0}}))
-- Glider on a 15x14 board
-- 840 distinct generation
-- loop afterward -> return -1
-- takes ~4-5 seconds on the same bad laptop
print(f({{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
       {0,0,0,1,1,1,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}))
Katenkyo
źródło
5

Galaretka, 26 25 bajtów

ṙ-r1¤SZµ⁺_|=3
ÇÐĿ-LiṪÇ$$?

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Większe przypadki testowe (z odpowiedzi @ Katenkyo ): stabilne 15 × 15 | Szybowiec 15 × 14

Jak to działa

ṙ-r1¤SZµ⁺_|=3  Helper link. Argument: G (grid)
               This link computes the next state of G.

    ¤          Evaluate the three links to the left as a niladic chain.
 -               Yield -1.
   1             Yield 1.
  r              Range; yield [-1, 0, 1].
ṛ              Rotate the rows of G -1, 0 and 1 units up.
     S         Compute the sum of the three resulting grids.
               Essentially, this adds the rows directly above and below each given
               row to that row.
      Z        Zip; transpose rows and columns.
       µ       Convert the preceding chain into a link and begin a new chain.
        ⁺      Apply the preceding chain once more.
               This zips back and adds the surrounding columns to each column.
         _     Subtract G from the result.
               Each cell now contains the number of lit cells that surround it.
          |    That the bitwise OR of the result and G.
               Notably, 3|0 = 3|1 = 2|1 = 3.
           =3  Compare each resulting number with 3.


ÇÐĿ-LiṪÇ$$?    Main link. Argument: G (grid)

ÇÐL            Repeatedly apply the helper link until the results are no longer
               unique. Collect all unique results in a list.
         $     Evaluate the two links to the left as a monadic chain:
        $        Evaluate the two links to the left as a monadic chain:
      Ṫ            Pop the last element of the list of grids.
       Ç           Apply the helper link to get the next iteration.
     i           Get the index of the grid to the right (the first non-unique one)
                 in the popped list of grids. This yields 0 iff the popped list
                 doesn't contain that grid, i.e., the grid reached a stable state.
          ?    If the index is non-zero:
   -             Return -1.
    L            Else, return the length of the popped list of grids.
Dennis
źródło
5

Perl, 154 151 144 140 137 133 129 bajtów

Obejmuje +3 za -ap0

Uruchom z wejściem jako wierszem grup cyfr oddzielonych spacją

life.pl <<< "0000 0001 0111 0010"

Jest to potrzebne tylko w przypadku, gdy dane wejściowe są natychmiast stabilne. We wszystkich innych przypadkach możesz też wygodniej podać go jako osobne linie cyfr:

life.pl
0000
0001
0111
0010
^D

Podanie danych w ten sposób dałoby 1 zamiast 0 dla natychmiastowej stabilnej konfiguracji.

life.pl:

#!/usr/bin/perl -ap0
map{@f=map$F[$_%@F]x3,$i-1..++$i;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo

Prawie bije Mathematica na tym ...

Tylko w starszych wersjach perla (gdzie można użyć stałej jako zmiennej) to 126 bajtowe rozwiązanie działa:

#!/usr/bin/perl -p0a
map{@f=map$F[$_++%@F]x2,-1..1;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo

W przypadku, gdy istnieją co najmniej 2 wiersze, to 123 bajtowe rozwiązanie działa na wszystkich wersjach perla:

#!/usr/bin/perl -p0a
@F=@F[-$#F..!s%.%"0+($&+33)=~grep\$_,map{(//g,//g)[@--1..@+]}\@F[-1..1]"%eeg]for@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo
Ton Hospel
źródło
1

rubin, 207 bajtów

->a{r=[];(r<<a;a=(0...a.size).map{|i|(0...a[i].size).map{|j|n=0;(-1..1).map{|u|(-1..1).map{|v|n+=a[(i+u)%a.size][(j+v)%a[i].size]}};[n==3,n>2&&n<5][a[i][j]]?1:0}})while(!r.index(a));(a==r[-1])?r.index(a):-1}

Przechowuję historię każdej planszy, więc jeśli dostanę planszę, którą widziałem, zanim się zorientowałem, zdarzyła się jedna z dwóch rzeczy. po pierwsze może być tak, że znaleźliśmy stabilną pozycję, w którym to przypadku będzie najbardziej niechętny w naszej historii. drugą możliwością jest to, że mamy pętlę.

MegaTom
źródło
Matryca 15x15 oznacza, że ​​mamy 2 ^ 225 możliwych plansz, bardzo wątpię, czy możesz zapamiętać te matryce, używając pamięci całego komputera na świecie (nawet jeśli większość gier prawdopodobnie skończy się z mniej niż 1000 plansz). Powodzenia, zajmując się tym w Maszyny 64-bitowe.
GameDeveloper
1
@DarioOO Nawet szybowiec na płycie 15x14 będzie potrzebował „tylko” generacji 840, zanim powróci do swojego pierwszego stanu, więc możemy oczekiwać, że prawie wszystko będzie poniżej 1000 genów. Również 1000 genów na 15x15 przy użyciu 32-bitowych liczb całkowitych powoduje użycie pamięci 15*15*4*1000-> 900 KB, co jest wystarczające w przypadkach, gdy potrzebujemy 10k + genów :).
Katenkyo 18.04.16
1

Julia, 92 88 bajtów

f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)

Weryfikacja

julia> f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)
f (generic function with 1 method)

julia> f([0 0 0;0 1 1;0 1 0])
2

julia> f([0 0 1 1;0 1 1 1;0 1 0 0;0 1 1 1])
2

julia> f([0 1 0 0;0 1 0 0;0 1 0 0;0 0 0 0])
-1

julia> f([0 0 0 0;0 0 0 1;0 1 1 1;0 0 1 0])
4

julia> f([0 0 0 0;0 1 1 0;0 1 1 0;0 0 0 0])
0

julia> f([0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0])
53

julia> f([0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;0 0 0 1 1 1 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0])
-1
Dennis
źródło