Challenge:

Given a matrix (or 2d array) of 0s and 1s, output the number of steps it takes for Conway's game of life to reach a stable state, or -1 if it never reaches one. A stable state is a state in which no cells are turned on or off each step. The game must run in the given matrix, with the top and bottom connected, and the sides connected. (i.e. given a 4x3 matrix it should run on a 4x3 torus) The input matrix will not be larger than 15x15.

Note: If the matrix starts in a stable state, the output should be 0.

Samples:

Input:

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


Output:

2

Process: (this does not need to be displayed)

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


Input:

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


Output:

2

Process:

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


Input:

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


Output:

-1

Process:

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


repeating forever

Input:

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


Output:

4

Process:

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


Input:

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


Output:

0

Process:

The beginning state is stable.

Rules of the Game of Life

If a cell that is off (0) is next to exactly three on (1) cells, it is turned on. Otherwise, it is left off. If a cell that is on is next to 2 or 3 on squares, it says on. Otherwise, it is turned off.

• So what should be output if the pattern repeats forever?
– Nic
Apr 13, 2016 at 21:38
• Possible input formats? Any bounds on matrix sizes? If not, what if we have a 100x100 matrix? Also, you should probably put a summary of the Game of Life rules in the question so it's self-contained. Apr 13, 2016 at 21:39
• Oh, I see. I misread one of the examples. Another question, though -- at what point should we assume it doesn't become stable? Because I'm sure there are plenty of patterns which become stable after hundreds or thousands of iterations. There's even a category for it: Methuselah
– Nic
Apr 13, 2016 at 21:44
• I'm pretty sure this challenge is essentially asking "solve the halting problem".
– user45941
Apr 13, 2016 at 21:45
• As a counterexample to show 250 generations is not always enough: For a 15 by 14 matrix, a single glider in an otherwise empty arena will take 15*14*4=840 generations to return to its original state. If the end of that long path is blocked by a 2 by 2 block, the glider will annihilate leaving a stable configuration. This will be a few rows short of the end of the path to avoid destroying the glider right at the start, but still well over 600 generations before stability. Apr 14, 2016 at 0:03

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&


I wouldn't recommend trying more than 4x4 inputs, because it's going to take forever (and a lot of memory).

Explanation

This simply simulates the Game of Life for 2N steps where N is the number of cells in the input. This guarantees that if the system settles into a stable state, we've reached it. Afterwards, we find the first pair of consecutive identical states in the simulated history.

Let's go through the code:

2^Length[Join@@#]


This computes 2N, since Join@@ is used to flatten a 2D list.

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


This simulates the Game of Life for 2N generations. The 3x3 matrix specifies the neighbourhood of a totalistic 2D automaton and 224 is the rule number of standard Game of Life. I've written about how to compute this number over here on Mathematica.SE.

Partition[...,2,1]


This gets all consecutive (overlapping) pairs of generations.

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


This finds the first pair of identical generations, defaulting to 0 if none is found and limiting the search to depth 1. If such a pair is found, the result is returned in a list though. So we use:

#&@@...


To extract the first element from that list (the default value of 0, being atomic, is unaffected by this).

...-1


Finally we subtract one because the challenge expects 0-based indices and -1 for failure.

Lua, 531509488487464424405 404 Bytes

Who wants a massive submission? \o/

Edit: Improved it, but don't know how to golf it anymore, so... explanations are coming comments added :)

Saved ~60 bytes with the help of @KennyLau

small golfing cutting one more byte by renaming a into Y to prevent the inlined hexadecimal conversion

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


Test cases

Here's some test cases

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


Perl, 154151144140137133 129 bytes

Includes +3 for -ap0

Run with the input as a line of groups of digits separated by space

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


This is only really needed in case the input is immediately stable. In all other cases you can also more conveniently give it as seperate lines of digits:

life.pl
0000
0001
0111
0010
^D


Giving input this way would however give 1 instead of 0 for an immediately stable configuration.

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  Almost beating Mathematica on this one... Only on older perl versions (where you could use a constant as a variable) does this 126 byte solution work: #!/usr/bin/perl -p0a map{@f=mapF[_++%@F]x2,-1..1;s%.%"0+(&+33)=~grep$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo


In case there are certain to be at least 2 rows this 123 byte solution works on all perl versions:

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


Jelly, 26 25 bytes

ṙ-r1¤SZµ⁺_|=3
ÇÐĿ-LiṪÇ$$?  Larger test cases (from @Katenkyo's answer): 15×15 stable | 15×14 glider How it works ṙ-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.


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


I keep a history of each board, so if I get a board I have seen before I know one of two thing happened. first it could be that we have found a stable position, in which case it will be the most resent in our history. the other possibility is that we have a loop.

• 15x15 matrix means we have 2^225 possible boards, I highly doubt you can even memorize those matrices using the memory of all computer in the worlds (even if most games will probably end with less than 1000 boards).. Good luck addressing that in 64 bit machines. Apr 15, 2016 at 10:19
• @DarioOO Even a glider on a 15x14 board will need "only" 840 generation before looping back to its first state, so we can expect nearly everything to be under 1000 gens. Also, 1000 gens on a 15x15 using 32 bits integers result in a memory usage of 15*15*4*1000 -> 900 KB, good enough for cases where we'll need 10k+ gens :). Apr 18, 2016 at 8:07

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)


Verification

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