Is it a still-life?

Question

The Problem:

You receive a (section of) a Conway's Game of Life grid. Your task is to output whether it represents a still-life (subsequent generations are identical to the current grid), a oscillator of period up to 4 (every nth generation is identical to the current grid), or something else.

The remainder of the infinite grid consists of dead cells.

Rules of the Game of Life

If a dead cell is next to exactly three living cells, it becomes alive. Otherwise, it remains dead. If a living cell is next to 2 or 3 living cells, it stays alive. Otherwise, it dies.

Input/Output formats

Input and output can be by any reasonable method - list of locations of living cells, array of bools, one or more strings, etc. You cannot assume that dead cells are stripped from the edge of the input grid. Outputs must be any three consistent values ([still-life: 0, oscillator: 1, other: 2], for instance).

For oscillators of period 5 or greater, output of "Oscillator" or "Other" are both acceptable.

Examples

(1 is living, 0 is dead)

INPUT          OUTPUT
0 0 0 0
0 1 1 0        Still-Life
0 1 1 0
0 0 0 0


INPUT          OUTPUT
1 1
1 0            Other


INPUT          OUTPUT
0 0 0 1 1 0
0 0 0 1 0 1    Still-Life
0 0 0 0 1 0


INPUT          OUTPUT
0 1 0
0 0 1          Other
0 1 0


INPUT          OUTPUT
0 1
0 1            Oscillator (period 2)
0 1


INPUT          OUTPUT
1 1 0 0
1 1 0 0        Oscillator (period 2)
0 0 1 1
0 0 1 1


INPUT                  OUTPUT
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0        Oscillator (period 3)
1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0
1 0 0 0 1 1 1 1
0 0 1 0 0 0 0 0


INPUT                 OUTPUT
1 1 0 0 0 1 1
0 1 0 1 0 1 0
0 1 1 0 1 1 0         Oscillator (period 4)
0 1 0 1 0 1 0
1 1 0 0 0 1 1


INPUT          OUTPUT
1 1 1
1 0 0          Other (This is a glider - the same shape will repeat, but it will be shifted)
0 1 0

This is code-golf- the shortest answer in each language wins.

Answer 1

APL (Dyalog Extended), ^{61 56 48 40 37 36 35 33} 32 bytes

6∧+/w∘≢¨⊢∘⌂life\5/⊆w←0,∘⌽∘⍉⍣16⊢⎕

Try it online!

Outputs 0 for still-life, 6 for oscillators, and 12 for other.

Expects a binary matrix.

-5 bytes from ovs using a train for the left-most dfn.

-8 bytes from user by omitting traj and using ⍣ instead.

-8 more bytes from user.

-3 bytes simplifying user's idea.

-1 more byte from user(how did they do it?!).

-2 more bytes, converting to a full program.

-1 more more byte from user.

Explanation

 6∧+/w∘≡¨⊢∘⌂life\5/⊆w←0,∘⌽∘⍉⍣16⊢⎕
                            ⍣16⊢⎕ apply the following to the input 16 times:
                      0,∘⌽∘⍉      rotate 90 degrees and prepend a column of zeroes
                    w←            store padded input in w    
                 5/⊆              copy it 5 times
         ⊢∘⌂life\                 scan using life function
     w∘≡¨                         check which ones match w       
   +/                             sum to get number of truthies
 6∧                               lcm(6,truthies)

Answer 2

MATL, 42 38 31 29 bytes

2 bytes saved thanks to @Neil!

4thYaXJ4:"3Y6QZ+5:7mtJX=w]xvu

Input is a binary matrix. Output is

• Still life: 1
• Oscillator: 0 newline1
• Other: 0.

Try it online! Or verify all test cases.

Explanation

4th      % Push 4, duplicate, concatenate horizontally. Gives [4 4]
Ya       % Implicit input. Padarray. Adds a 2D frame of width 4. This is the
         % initial grid state. The padding ensures that results will be correct
         % for 4 iterations even if only this finite region is considered
XJ       % Copy that into clipboard J
4:"      % Push 4, range, for each (this loop runs for 4 iterations)
  3Y6    %   Push [1 1 1; 1 0 1; 1 1 1] (Moore neighbourhood)
  Q      %   Add 1, element-wise. Gives [2 2 2; 2 1 2; 2 2 2]
  Z+     %   2D convolution, maintaining size. Newly active cells correspond to
         %   values 5 = 1+2*2 (active cell with 2 active neighbours), 6 = 0+2*3
         %   (inactive cell with 3 active neighours) or 7 = 1+2*3 (active cell
         %   with 3 active neighours)
  5:7    %   Push range from 5 to 7, that is, [5 6 7]
  m      %   Ismember. This gives the new grid state
  tJX=   %   Duplicate. Push copy of initial state. Are both arrays equal? Gives
         %   true (1) or false (0) (*)
  w      %   Swap. This moves the latest grid state to top, for the next iteration
]        % End
x        % Delete last grid state. The stack contains the results of (*) for each
         % iteration
v        % Concatenate stack contents vertically. Gives a column vector containing
         % true (1) or false (0). The only possibilities are: [1; 1; 1; 1]
         % (still life), [0; 1; 0; 1] (period 2), [0; 0; 1; 0] (period 3),
         % [0; 0; 0; 1] (period 4) and [0; 0; 0; 0] (other)
u        % Unique: removes duplicates, maintaining order. Gives 1, [0; 1] or 0
         % Implicit display

Answer 3

JavaScript (ES6), 191 bytes

Expects a binary matrix. Returns false for still-life, true for oscillator or 0 for other.

m=>(M=m=(h=a=>[v,v,v,v,...a,v,v,v,v])(v=m.map(h,v=0),v=v.map(_=>0)),g=k=>(m=m.map((r,y)=>r.map((v,x)=>m.reduce(n=>d?n>>(m[~-(y+--d/3)]||[])[x+d%3-1]:n,v*16+8,d=9)&1)))+''!=M?k&&g(k-1):k<4)(4)

Try it online!

Commented

The helper function h expands an array a[] with 4 leading and 4 trailing values v:

h = a => [v, v, v, v, ...a, v, v, v, v]

We use it to expand the original matrix horizontally and vertically. A copy of the updated matrix is saved in M:

M = m = h(v = m.map(h, v = 0), v = v.map(_ => 0))

We then invoke the main recursive function g with k = 4:

g = k =>                         // k = counter
  ( m =                          // update m[]:
    m.map((r, y) =>              //   for each row r[] at position y in m[]:
      r.map((v, x) =>            //     for each value v at position x in r[]:
        m.reduce(n =>            //       for each entry in m[]:
          d ?                    //         if d is not equal to 0:
            n >> (               //           right-shift n if the cell at:
              m[~-(y + --d / 3)] //             Y = floor(y + --d / 3) - 1
              || []              //
            )[x + d % 3 - 1]     //             X = x + (d mod 3) - 1
                                 //           is set
          :                      //         else:
            n,                   //           leave n unchanged
          v * 16 + 8,            //         starting with n = v * 16 + 8
                                 //         (0b1000 if v = 0, or 0b11000 if v = 1)
          d = 9                  //         and d = 9
        )                        //       end of reduce()
        & 1                      //       isolate the least significant bit
      )                          //     end of inner map()
    )                            //   end of outer map()
  ) + '' != M ?                  // coerce m[] to a string; if it's not equal to M[]:
    k && g(k - 1)                //   unless k = 0, do a recursive call with k - 1
  :                              // else:
    k < 4                        //   test whether there was at least 2 iterations

Answer 4

APL (Dyalog Extended), 31 27 26 bytes

(6∧⌂life⍣(1…4)⍳⊂)(⌽0,⍉)⍣16

Try it online!

APL has emerged victorious again. My work here is finally done; now I can rest.

This borrows heavily from Razetime's answer, but I thought it was sufficiently different as to merit its own answer. Also, I wanted to get some rep from this :) @ngn also helped on this new train version.

Returns 0 for still-life, 6 for oscillators, and 12 for other. Requires zero-indexing.

⎕ is niladic and reads from the input.

(⌽0,⍉)⍣16 pads 4 layers of zeroes on all sides of the input. ⍣, the power operator, applies (⌽0,⍉) 16 times. 0, adds one row of zeroes, and ⌽⍉ rotates 90 degrees.

life⍣(1…4)⍳⊂ is a fork. On the right side, ⊂ boxes the padded grid. On the left side, ⌂life⍣(1…4) makes a range from 1 to 4 (1…4) and for every x in that range, it applies the ⌂life function to the padded matrix x times. Basically, it gives us a vector of the padded matrix over 4 generations. Then, ⍳ finds the index of the padded matrix inside the vector of generations. If it's a still-life, this will be 0, the first element; if it's an oscillator, it will be 1, 2, or 3, and if it's something else, it will be 4 (outside the vector).

6∧ just bring the different oscillator indices together finding the lcm with 6. Still-life (0) remains 0, oscillator (1,2,3) become 6, and other (4) becomes 12.

Answer 5

Jelly, 32 31 bytes

Ż€UZ
Ç⁴¡µÇ4¡+3\Z$⁺_|=3µ4СḊiµ’Ṡ

Try it online!

Outputs 0 for still life, 1 for oscillator, and -1 for other.

Ż€UZ                          Monadic helper link: pad row with zeroes and rotate
Ż€                            Prepend a 0 to each row,
  U                           reverse each row,
   Z                          transpose.

Ç⁴¡µÇ4¡+3\Z$⁺_|=3µ4СḊiµ’Ṡ    Main link:
Ç⁴¡                           Repeat helper 16 times (pad the input four times).
   µ             µ4С         Repeat four times, collecting each result
                     Ḋ        (not including the 0th iteration):
    Ç4¡                       pad the grid once,
       +3\                    sum every neighborhood of three elements,
          Z                   transpose,
           $⁺                 sum and transpose again,
             _                subtract the previous grid values,
              |               bitwise OR with the previous grid values,
               =3             is each equal to 3?
                      i       Find the index in the results (or 0 if not found)
Ç4¡µ                          of the quadruple-padded input,
                       µ      then
                        ’     decrement
                         Ṡ    and take the sign.

µ’ could be _1, and Ż€UZµ4¡ was originally Ż€UZƊ4¡, but if I'm already using two one µs then I may as well use two one more!

Ç4¡+3\Z$⁺ computes the sum of each Moore neighborhood including the centers, which in the case of a cell which should be alive in the next generation is 3 or 4, but not 4 if the cell is dead, so while _| leaves sums for dead cells unchanged, it decrements the sums for alive cells, such that cells which should survive have values 2 or 3, then sets the ones bit so that 2 becomes 3, 3 remains 3, and no other value becomes 3.

Answer 6

Wolfram Language (Mathematica), 65 bytes

⌊CellularAutomaton["GameOfLife",p=#~ArrayPad~4,4]~Count~p/2⌋&

Try it online!

Returns 2 for still-life, 1 for oscillators, and 0 for other.

Answer 7

05AB1E, 43 bytes

8Fø¾δ.ø}©4FÐ2Fø¾δ.ø}2F€ü3ø}OO·α567såD®Qˆ}¯Ù

Inspired by @LuisMendo's MATL answer, just with less convenient builtins.. matrix challenges aren't really 05AB1E's strong suit.

Outputs [1] for still-life; [0,1] for oscillator; and [0] for other.

Try it online or verify all test cases.

Explanation:

# Pad the input with four layers of 0s:
8F            # Loop 8 times:
  ø           #  Zip/transpose, swapping rows/columns
              #  (which uses the implicit input in the first iteration)
    δ         #  Loop over each row:
   ¾ .ø       #   And surround it with a leading and trailing 0
}©            # After the loop: store the padded input in variable `®` (without popping)

# Now we'll do a Game of Life cycle, four iterations in total:
4F            # Loop 4 times:
  D           #  Duplicate the current matrix
   2Fø¾δ.ø}   #  Pad it with a single layer of 0s similar as above
   2F         #  Loop 2 times:
     €        #   Map over each row:
      ü3      #    Create overlapping triplets of the current row
     ø        #   Zip/transpose; swapping rows/columns
   }          #  After this loop, we'll have a list of 3x3 blocks
    OO        #  Sum all values in a single 3x3 block together
      ·       #  Then double each sum
       α      #  Take the absolute difference (at the same positions) with the current
              #  matrix we've duplicated earlier
        567så #  Check for each value in this matrix if it's in the integer 567
              #  (1 if truthy; 0 if falsey)
  D           #  Duplicate the resulting matrix
   ®Q         #  Check if it's equal to matrix `®` (1 if truthy; 0 if falsey)
     ˆ        #  Pop and add this check to the global array
}             # After the loop:

# Create the result based on these four iterations:
¯             # Push the global array
 Ù            # Uniquify it
              # (after which the result is output implicitly)

Answer 8

Python 3, ^{413 \$\cdots\$ 375} 354 bytes

Saved 13 bytes thanks to Danis!!!

def f(w,t=0,u=[0],R=range):
 l=len(w[0])+12;d=len(w);m=[u*l for i in u*6]+[u*6+w[i]+u*6for i in R(d)]+[u*l for i in u*6];n=[u*l for j in m];q=R(-1,2)
 while t<6and any(w[r]!=n[r+6][6:-6]for r in R(d)):
  for r in R(1,11+d):
   for c in R(1,l-1):n[r][c]=sum(m[r+i][c+j]for i in q for j in q)in(3+m[r][c],3)
  m=[[*r]for r in n];t+=1
 return t>5and 2or t>1

Try it online!

Verbose but it works! :)))

Inputs the grid as a list of lists of \$1\$s and \$0\$s.
Returns False if it's a still-life, True if its an oscillator, or \$2\$ if it's an other.

Answer 9

Charcoal, 90 bytes

≔⁰θ≔⟦⟧ηＷＳ«Ｆ⌕Ａι1⊞η⟦θκ⟧≦⊕θ»≔ηθＦ⁴«≔⟦⟧ζＦ³Ｆ³Ｆ⊕⌈↔⊖⟦κλ⟧Ｆθ⊞ζ⊖Ｅν⁺ξ⎇πλκ≔Φζ∧⁼λ⌕ζκ›²↔⁻⁶№ζκθ⊞υθ»Ｉ⌈⟦¹⌕υη

Try it online! Link is to verbose version of code. Input is a newline-terminated list of strings and output is -1 for other, 0 for stable and 1 for oscillator. Explanation:

≔⁰θ≔⟦⟧ηＷＳ«Ｆ⌕Ａι1⊞η⟦θκ⟧≦⊕θ»≔ηθ

Input the grid, push the coordinates of all the 1s to a list, and keep a copy of that list.

Ｆ⁴«

Iterate the game of life 4 times.

≔⟦⟧ζＦ³Ｆ³Ｆ⊕⌈↔⊖⟦κλ⟧Ｆθ⊞ζ⊖Ｅν⁺ξ⎇πλκ

Make a new list consisting of all the cells in the original list plus two repetitions for each neighbouring cell.

≔Φζ∧⁼λ⌕ζκ›²↔⁻⁶№ζκθ

Extract all cells that appear between 5 and 7 times. 5 represents a live cell with 2 neighbours, while 6 and 7 represent cells with 3 neighbours.

⊞υθ

Save a copy of the new iteration.

»Ｉ⌈⟦¹⌕υη

Print the index of the original position in the list of iterations, limited to 1.