The Game of Life is a   cellular automaton   devised by the British mathematician   John Horton Conway   in 1970.   It is the best-known example of a cellular automaton.

Conway's game of life is described   here:

A cell   C   is represented by a   1   when alive,   or   0   when dead,   in an   m-by-m   (or m×m)   square array of cells.

We calculate   N   - the sum of live cells in C's   eight-location neighbourhood,   then cell   C   is alive or dead in the next generation based on the following table:

   C   N                 new C
   1   0,1             ->  0  # Lonely
   1   4,5,6,7,8       ->  0  # Overcrowded
   1   2,3             ->  1  # Lives
   0   3               ->  1  # It takes three to give birth!
   0   0,1,2,4,5,6,7,8 ->  0  # Barren

Assume cells beyond the boundary are always dead.

The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players.   One interacts with the Game of Life by creating an initial configuration and observing how it evolves.



Task

Although you should test your implementation on more complex examples such as the   glider   in a larger universe,   show the action of the blinker   (three adjoining cells in a row all alive),   over three generations, in a 3 by 3 grid.



References

   Its creator John Conway, explains   the game of life.   Video from numberphile on youtube.
   John Conway   Inventing Game of Life   - Numberphile video.


Related task

   Langton's ant   - another well known cellular automaton.


global limit
 
procedure main(args)
    n := args[1] | 50        # default is a 50x50 grid
    limit := args[2] | &null #  optional limit to number of generations
    write("Enter the starting pattern, end with EOF")
    grid := getInitialGrid(n)
    play(grid)
end
 
# This procedure reads in the initial pattern, inserting it
#   into an nXn grid of cells.  The nXn grid also gets a
#   new border of empty cells, which just makes the test simpler
#   for determining what do with a cell on each generation.
# It would be better to let the user move the cursor and click
#   on cells to create/delete living cells, but this version
#   assumes a simple ASCII terminal.
procedure getInitialGrid(n)
    static notBlank, allStars
    initial {
        notBlank := ~' '            
        allStars := repl("*",*notBlank)
        }
 
    g := []                # store as an array of strings
 
    put(g,repl(" ",n))
    while r := read() do {                        # read in rows of grid
        r := left(r,n)                            #   force each to length n
        put(g," "||map(r,notBlank,allStars)||" ") #   and making any life a '*'
        }
    while *g ~= (n+2) do
        put(g,repl(" ",n))
 
    return g
end
 
# Simple-minded procedure to 'play' Life from a starting grid.
procedure play(grid)
    while not allDone(grid) do {
        display(grid)
        grid := onePlay(grid)
        }
end
 
# Display the grid
procedure display(g)
    write(repl("-",*g[1]))
    every write(!g)
    write(repl("-",*g[1]))
end
 
# Compute one generation of Life from the current one.
procedure onePlay(g)
    ng := []
    every put(ng, !g)        # new generation starts as copy of old
    every ng[r := 2 to *g-1][c := 2 to *g-1] := case sum(g,r,c) of {
                            3:       "*"     # cell lives (or is born)
                            2:       g[r][c] # cell unchanged
                            default: " "     # cell dead
                            }
    return ng
end
 
# Return the number of living cells surrounding the current cell.
procedure sum(g,r,c)
    cnt := 0
    every (i := -1 to 1, j := -1 to 1) do
        if ((i ~= 0) | (j ~= 0)) & (g[r+i][c+j] == "*") then cnt +:= 1
    return cnt
end
 
# Check to see if all the cells have died or we've exceeded the 
#   number of allowed generations.
procedure allDone(g)
   static count
   initial count := 0
   return ((count +:= 1) > \limit) | (trim(!g) == " ")
end