Tantangan:

Diberi matriks (atau array 2d) 0s dan 1s, output jumlah langkah yang diperlukan untuk permainan Conway untuk mencapai kondisi stabil, atau -1 jika tidak pernah mencapai satu. Keadaan stabil adalah keadaan di mana tidak ada sel yang dinyalakan atau dimatikan setiap langkah. Gim harus berjalan dalam matriks yang diberikan, dengan bagian atas dan bawah terhubung, dan sisi-sisinya terhubung. (Yaitu diberi matriks 4x3 itu harus dijalankan pada torus 4x3) Matriks input tidak akan lebih besar dari 15x15.

Catatan: Jika matriks dimulai dalam keadaan stabil, output harus 0.

Sampel:

Memasukkan:

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

Keluaran:

2

Proses: (ini tidak perlu ditampilkan)

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

Memasukkan:

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

Keluaran:

2

Proses:

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

Memasukkan:

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

Keluaran:

-1

Proses:

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

terulang selamanya

Memasukkan:

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

Keluaran:

4

Proses:

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

Memasukkan:

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

Keluaran:

0

Proses:

Keadaan awal stabil.

Aturan Game of Life

Jika sel yang mati (0) tepat di sebelah tepat tiga pada (1) sel, itu dihidupkan. Kalau tidak, itu akan ditinggalkan. Jika sel yang aktif di sebelah 2 atau 3 pada kotak, ia mengatakan. Kalau tidak, dimatikan.

Mathematica, 130 129 byte

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

Saya tidak akan merekomendasikan mencoba lebih dari input 4x4, karena itu akan memakan waktu lama (dan banyak memori).

Penjelasan

Ini hanya mensimulasikan Game of Life untuk 2 ^N langkah di mana N adalah jumlah sel dalam input. Ini menjamin bahwa jika sistem menetap ke kondisi stabil, kami telah mencapainya. Setelah itu, kami menemukan pasangan pertama dari status identik berturut-turut dalam sejarah simulasi.

Mari kita lihat kodenya:

2^Length[Join@@#]

Ini menghitung 2 ^N , karena Join@@digunakan untuk meratakan daftar 2D.

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

Ini mensimulasikan Game of Life untuk generasi 2 ^N. Matriks 3x3 menentukan lingkungan dari otomat 2D totalistik dan 224merupakan nomor aturan dari Game of Life standar. Saya telah menulis tentang bagaimana menghitung angka ini di sini di Mathematica.SE .

Partition[...,2,1]

Ini menghasilkan semua pasangan generasi secara berurutan (tumpang tindih).

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

Ini menemukan pasangan generasi pertama yang identik, default ke 0jika tidak ada yang ditemukan dan membatasi pencarian ke kedalaman 1. Jika pasangan seperti ini ditemukan, hasilnya dikembalikan dalam daftar meskipun. Jadi kami menggunakan:

#&@@...

Untuk mengekstrak elemen pertama dari daftar itu (nilai default 0, menjadi atom, tidak terpengaruh oleh ini).

...-1

Akhirnya kami mengurangi satu karena tantangan mengharapkan 0indeks berbasis dan -1untuk kegagalan.

Lua, 531 509 488 487 464 424 405 404 Bytes

Siapa yang mau pengajuan besar-besaran? \Hai/

Sunting: Memperbaikinya, tetapi tidak tahu cara bermain golf lagi, jadi ... penjelasannya akan ditambahkan komentar :)

Disimpan ~ 60 byte dengan bantuan @ KennyLau

golf kecil memotong satu byte lagi dengan mengubah nama amenjadi Yuntuk mencegah konversi heksadesimal yang digariskan

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

Tidak disatukan

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

Uji kasus

Ini beberapa test case

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

Jelly, 26 25 byte

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

Cobalah online! atau verifikasi semua kasus uji .

Kasing uji yang lebih besar (dari jawaban @ Katenkyo ): 15 × 15 stable | 15 × 14 peluncur

Bagaimana itu bekerja

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

Perl, 154 151 144 140 137 133 129 byte

Termasuk +3 untuk -ap0

Jalankan dengan input sebagai garis kelompok digit yang dipisahkan oleh spasi

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

Ini hanya benar-benar diperlukan jika input langsung stabil. Dalam semua kasus lain, Anda juga dapat dengan mudah memberikannya sebagai garis digit terpisah:

life.pl
0000
0001
0111
0010
^D

Namun, memberikan input dengan cara ini akan memberikan 1 bukannya 0 untuk konfigurasi yang stabil segera.

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

Hampir mengalahkan Mathematica yang satu ini ...

Hanya pada versi perl yang lebih lama (di mana Anda dapat menggunakan konstanta sebagai variabel) apakah solusi 126 byte ini berfungsi:

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

Seandainya ada setidaknya 2 baris solusi 123 byte ini bekerja pada semua versi perl:

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

ruby, 207 byte

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

Saya menyimpan sejarah setiap papan, jadi jika saya mendapatkan papan yang pernah saya lihat sebelumnya, saya tahu satu dari dua hal terjadi. pertama bisa jadi kita telah menemukan posisi yang stabil, dalam hal ini akan menjadi yang paling membenci dalam sejarah kita. kemungkinan lainnya adalah kita memiliki satu loop.

Julia, 92 88 byte

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)

Verifikasi

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