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}}))
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.69018I'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.627Is 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