Stable Game of Life

19

1

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.

poi830

Posted 2016-04-13T21:34:53.887

Reputation: 1 265

So what should be output if the pattern repeats forever? – Fund Monica's Lawsuit – 2016-04-13T21:38:12.583

I belive it says to output -1 in the question. – poi830 – 2016-04-13T21:38:34.153

2Possible 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. – El'endia Starman – 2016-04-13T21:39:24.857

3

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

– Fund Monica's Lawsuit – 2016-04-13T21:44:56.690

18I'm pretty sure this challenge is essentially asking "solve the halting problem". – Mego – 2016-04-13T21:45:38.010

In small matrices like these, a pattern cannot take very long to become stable, so around 250 generations would probably be enough. – poi830 – 2016-04-13T21:46:49.813

So there's a bound on the size? – Fund Monica's Lawsuit – 2016-04-13T21:47:48.470

Yeah, I added a 15x15 size limit to the question. – poi830 – 2016-04-13T21:48:27.953

Is there a specific input format, and can I assume that the input is valid? – Fund Monica's Lawsuit – 2016-04-13T21:50:46.143

The input is a matrix consisting of 0s and 1s, and yes, you can assume the input is valid. – poi830 – 2016-04-13T21:51:29.063

Are you saying "regard any matrix that hasn't stabilised by 250 generations as never stabilising", or do answers need to choose a number of generations that is provably sufficient to draw that conclusion? For example, 2^(15*15) is provably enough generations, as a given matrix always has the same successor and there are only this many possible matrices. I suspect there are much smaller upper bounds but I don't know how to prove one. – trichoplax – 2016-04-13T22:28:15.303

I'd recommend putting the rules before the examples, and including that each cell has 8 neighbours, for anyone unfamiliar with Conway's Game of Life. – trichoplax – 2016-04-13T23:48:57.257

6As 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 15144=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. – trichoplax – 2016-04-14T00:03:26.017

Can I just do 2^(x*y) iterations, or is there a timing constraint? – John Dvorak – 2016-04-14T14:59:31.880

@JanDvorak Doesn't looks like there's a timing constraint as the Mathematica answer is said to take ages for everything greater than 4x4

– Katenkyo – 2016-04-15T08:17:02.627

Is there a minimum size ? I'd like really to assume width and height >= 2 so the same value doesn't wrap around twice :-) – Ton Hospel – 2016-04-16T11:41:25.963

@poi830 Please clarify in the question the maximum number of generations required, or if a solution will only detect an infinite loop by reaching a previously held state. At the moment, it's unclear what you're asking. – mbomb007 – 2017-03-01T20:14:37.653

Answers

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&

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.

Martin Ender

Posted 2016-04-13T21:34:53.887

Reputation: 184 808

8

Lua, 531 509 488 487 464 424 405 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}}))

Katenkyo

Posted 2016-04-13T21:34:53.887

Reputation: 2 857

5

Perl, 154 151 144 140 137 133 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=map$F[$_++%@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

Ton Hospel

Posted 2016-04-13T21:34:53.887

Reputation: 14 114

5

Jelly, 26 25 bytes

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

Try it online! or verify all test cases.

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.

Dennis

Posted 2016-04-13T21:34:53.887

Reputation: 196 637

1

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.

MegaTom

Posted 2016-04-13T21:34:53.887

Reputation: 3 787

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. – CoffeDeveloper – 2016-04-15T10:19:22.900

1@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 :). – Katenkyo – 2016-04-18T08:07:28.810

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)

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

Dennis

Posted 2016-04-13T21:34:53.887

Reputation: 196 637