Stabiles Spiel des Lebens

19

Herausforderung:

Geben Sie bei einer Matrix (oder einem 2D-Array) aus 0 und 1 die Anzahl der Schritte aus, die Conways Lebensspiel benötigt, um einen stabilen Zustand zu erreichen, oder -1, wenn es nie einen erreicht. Ein stabiler Zustand ist ein Zustand, in dem bei jedem Schritt keine Zellen ein- oder ausgeschaltet werden. Das Spiel muss in der angegebenen Matrix ausgeführt werden, wobei Ober- und Unterseite sowie die Seiten miteinander verbunden sind. (Bei einer 4x3-Matrix sollte diese auf einem 4x3-Torus ausgeführt werden.) Die Eingabematrix darf nicht größer als 15x15 sein.

Hinweis: Wenn die Matrix in einem stabilen Zustand startet, sollte der Ausgang 0 sein.

Proben:

Eingang:

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

Ausgabe:

2

Prozess: (muss nicht angezeigt werden)

[[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]]

Eingang:

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

Ausgabe:

2

Verarbeiten:

[[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]]

Eingang:

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

Ausgabe:

-1

Verarbeiten:

[[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]]

für immer wiederholen

Eingang:

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

Ausgabe:

4

Verarbeiten:

[[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]]

Eingang:

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

Ausgabe:

0

Verarbeiten:

Der Anfangszustand ist stabil.

Spielregeln des Lebens

Wenn eine Zelle, die ausgeschaltet ist (0), neben genau drei eingeschalteten (1) Zellen liegt, ist sie eingeschaltet. Ansonsten bleibt es aus. Wenn eine Zelle, die eingeschaltet ist, neben 2 oder 3 auf Quadraten steht, heißt das, dass sie eingeschaltet ist. Ansonsten ist es ausgeschaltet.

poi830
quelle
Was soll also ausgegeben werden, wenn sich das Muster für immer wiederholt?
Fund Monica Klage
2
Mögliche Eingabeformate? Grenzen für Matrixgrößen? Wenn nicht, was ist, wenn wir eine 100x100-Matrix haben? Außerdem sollten Sie wahrscheinlich eine Zusammenfassung der Game of Life-Regeln in die Frage einfügen, damit sie in sich geschlossen sind.
El'endia Starman
3
Oh, ich verstehe. Ich habe eines der Beispiele falsch verstanden. Eine andere Frage - an welchem ​​Punkt sollten wir annehmen, dass es nicht stabil wird? Weil ich sicher bin, dass es viele Muster gibt, die nach Hunderten oder Tausenden von Iterationen stabil werden. Es gibt sogar eine Kategorie dafür: Methusalah
Fund Monicas Klage
18
Ich bin mir ziemlich sicher, dass es bei dieser Herausforderung im Wesentlichen darum geht, "das Halteproblem zu lösen".
Mego
6
Ein Gegenbeispiel, das 250 Generationen zeigt, reicht nicht immer aus: Für eine 15 x 14-Matrix benötigt ein einzelner Segelflugzeug in einer ansonsten leeren Arena 15 * 14 * 4 = 840 Generationen, um in seinen ursprünglichen Zustand zurückzukehren. Wenn das Ende dieses langen Weges durch einen 2 mal 2-Block blockiert wird, wird der Segelflugzeug vernichtet und eine stabile Konfiguration hinterlassen. Dies wird ein paar Reihen vor dem Ende des Weges sein, um zu vermeiden, dass der Schirm gleich zu Beginn zerstört wird, aber immer noch weit über 600 Generationen vor der Stabilität.
Trichoplax

Antworten:

10

Mathematica, 130 129 Bytes

#&@@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&

Ich würde nicht empfehlen, mehr als 4x4-Eingänge zu verwenden, da dies ewig dauern wird (und viel Speicherplatz benötigt).

Erläuterung

Dies simuliert einfach das Spiel des Lebens für 2 N Schritte, wobei N die Anzahl der Zellen in der Eingabe ist. Dies garantiert, dass wir einen stabilen Zustand des Systems erreicht haben. Danach finden wir das erste Paar aufeinanderfolgender identischer Zustände in der simulierten Historie.

Lass uns den Code durchgehen:

2^Length[Join@@#]

Dies berechnet 2 N , daJoin@@ zum Reduzieren einer 2D-Liste verwendet wird.

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

Dies simuliert das Spiel des Lebens für 2 N Generationen. Die 3x3-Matrix gibt die Nachbarschaft eines totalistischen 2D-Automaten an und 224ist die Regelnummer des Standard-Lebensspiels. Ich habe hier auf Mathematica.SE darüber geschrieben, wie man diese Zahl berechnet .

Partition[...,2,1]

Dies ergibt alle aufeinanderfolgenden (überlappenden) Generationenpaare.

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

Dadurch wird das erste Paar identischer Generationen 0gefunden. Wird keine gefunden, wird standardmäßig die Suche auf die Tiefe beschränkt 1. Wenn ein solches Paar wird gefunden, wird das Ergebnis allerdings in einer Liste zurückgegeben. Also benutzen wir:

#&@@...

So extrahieren Sie das erste Element aus dieser Liste (der Standardwert von 0ist atomar und bleibt davon unberührt).

...-1

Schließlich subtrahieren wir eins, weil die Herausforderung auf 0-basierten Indizes und -1auf Misserfolg beruht.

Martin Ender
quelle
8

Lua, 531 509 488 487 464 424 405 404 Bytes

Wer möchte eine massive Einreichung? \O/

Bearbeiten: Verbesserte es, aber weiß nicht mehr, wie man Golf spielt, also ... werden Erklärungen kommen Kommentare hinzugefügt :)

~ 60 Bytes mit Hilfe von @ KennyLau gespeichert

kleine Golf - Schneiden ein weiteres Byte durch die Umbenennung ain Ydie inlined hexadezimale Umwandlung zu verhindern

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

Ungolfed

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

Testfälle

Hier sind einige Testfälle

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
quelle
5

Jelly, 26 25 Bytes

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

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Größere Testfälle (aus der Antwort von @ Katenkyo ): 15 × 15 stabil |15 × 14 Segelflugzeug

Wie es funktioniert

ṙ-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
quelle
5

Perl, 154 151 144 140 137 133 129 Bytes

Beinhaltet +3 für -ap0

Führen Sie die Eingabe als eine durch Leerzeichen getrennte Reihe von Zifferngruppen aus

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

Dies wird nur dann wirklich benötigt, wenn die Eingabe sofort stabil ist. In allen anderen Fällen können Sie es auch bequemer als separate Ziffernzeilen angeben:

life.pl
0000
0001
0111
0010
^D

Wenn Sie auf diese Weise eine Eingabe machen, erhalten Sie jedoch 1 anstelle von 0 für eine sofort stabile Konfiguration.

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

Mathematica in diesem Fall fast geschlagen ...

Nur in älteren Perl-Versionen (wo Sie eine Konstante als Variable verwenden könnten) funktioniert diese 126-Byte-Lösung:

#!/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

Wenn mindestens 2 Zeilen vorhanden sind, funktioniert diese 123-Byte-Lösung für alle Perl-Versionen:

#!/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
Tonne Hospel
quelle
1

Rubin, 207 Bytes

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

Ich führe von jedem Board eine Chronik. Wenn ich also ein Board bekomme, das ich gesehen habe, bevor ich weiß, dass eines von zwei Dingen passiert ist, Erstens könnte es sein, dass wir eine stabile Position gefunden haben. In diesem Fall ist dies die bitterste in unserer Geschichte. Die andere Möglichkeit ist, dass wir eine Schleife haben.

MegaTom
quelle
15x15 Matrix bedeutet, dass wir 2 ^ 225 mögliche Boards haben. Ich bezweifle, dass Sie sich diese Matrizen sogar aus dem Speicher aller Computer der Welt merken können (auch wenn die meisten Spiele wahrscheinlich mit weniger als 1000 Boards enden werden) 64-Bit-Maschinen.
GameDeveloper
1
@DarioOO Sogar ein Segelflugzeug auf einem 15x14-Board benötigt "nur" eine 840-Generation, bevor es in den ersten Zustand zurückkehrt. Wir können also davon ausgehen, dass fast alles unter 1000 Gens liegt. Außerdem ergeben 1000 Gens bei einer Größe von 15 x 15 mit 32-Bit-Ganzzahlen eine Speichernutzung von 15*15*4*1000-> 900 KB. Dies ist gut genug für Fälle, in denen 10k + Gens benötigt werden :).
Katenkyo
1

Julia, 92 88 Bytes

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)

Nachprüfung

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
quelle