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.


--
-- demo\rosetta\Conways_Game_of_Life.exw
-- =====================================
--
with javascript_semantics
include pGUI.e

constant title = "Conway's Game of Life"
Ihandle dlg, canvas
Ihandln hTimer = NULL
cdCanvas cddbuffer

sequence c = {},    -- cells
         cn,        -- new cells
         cl         -- last cells

procedure draw(integer what)
    integer x = floor(length(c)/2)+1,
            y = floor(length(c[1])/2)
    switch what do
        case ' ': c = sq_mul(c,0)                                   -- Clear
        case '+': c[x][y-1..y+1] = repeat(1,3)                      -- Blinker
        case 'G': {                    c[x+1,y+4],
                   c[x+2,y+2],         c[x+2,y+4],
                           c[x+3,y+3], c[x+3,y+4]} = repeat(1,5)    -- Glider
        case 'T': {c[x-1,y+1],c[x,y+1],c[x+1,y+1],
                   c[x  ,y+3],c[x,y+4],c[x  ,y+5]} = repeat(1,6)    -- Thunderbird
        case 'X': for i=0 to min(x,y)-1 do
                    {c[x-i,y+i],c[x+i,y+i],
                     c[x-i,y-i],c[x+i,y-i]} = repeat(1,4)           -- Cross
                  end for
    end switch
end procedure

atom t1 = time()+1
integer fps = 0

function redraw_cb(Ihandle /*ih*/)
    integer {width, height} = IupGetIntInt(canvas, "DRAWSIZE"),
            -- limit to 10K cells (performance target of 10fps)
            -- n here is the cell size in pixels (min of 1x1)
            n = ceil(sqrt(width*height/10000)),
            w = floor(width/n)+2, -- (see cx below)
            h = floor(height/n)+2,
            alive = 0
    -- keep w, h odd for symmetry (plus I suspect the 
    --  "Cross" code above may now crash without this)
    w -= even(w)
    h -= even(h)
    if length(c)!=w
    or length(c[1])!=h then
        c = repeat(repeat(0,h),w)
        cn = deep_copy(c)
        cl = deep_copy(c)
        draw('X')
        if hTimer!=NULL then
            IupStoreAttribute(hTimer, "RUN", "YES")
        end if
    end if
    cdCanvasActivate(cddbuffer)
    --
    -- There is a "dead border" of 1 cell all around the edge of c (etc) which
    -- we never display or update. If we have got this right/an exact fit, then 
    -- w*n should be exactly 2n too wide, whereas in the worst case there is an
    -- (2n-1) pixel border, which we split between left and right, ditto cy.
    --
    integer cx = n+floor((width-w*n)/2)
    for x=2 to w-1 do
        integer cy = n+floor((height-h*n)/2)
        for y=2 to h-1 do
            integer cxy = c[x,y],
                    clxy = cl[x,y],
                    cnxy = -cxy
            for i=x-1 to x+1 do
                for j=y-1 to y+1 do
                    cnxy += c[i,j]
                end for
            end for
            integer live = iff(cxy?cnxy>=2 and cnxy<=3:cnxy==3),
            colour = iff(live?iff(cxy?iff(clxy?CD_PURPLE    -- adult
                                              :CD_GREEN)    -- newborn
                                     :iff(clxy?CD_RED       -- old
                                              :CD_YELLOW))  -- shortlived
                             :CD_BLACK)
            cn[x,y] = live
            alive += live
            cdCanvasSetForeground(cddbuffer,colour)
            cdCanvasBox(cddbuffer, cx, cx+n-1, cy, cy+n-1)
            cy += n
        end for
        cx += n
    end for
    cdCanvasFlush(cddbuffer)
    if not alive then
        IupStoreAttribute(hTimer, "RUN", "NO")
        IupStoreAttribute(dlg, "TITLE", "died")
    elsif c=cn then
        IupStoreAttribute(hTimer, "RUN", "NO")
        IupStoreAttribute(dlg, "TITLE", "stable")
    else
        cl = c
        c = deep_copy(cn)
        fps += 1
        if time()>=t1 then
            IupSetStrAttribute(dlg,"TITLE","%s (%d FPS)",{title,fps})
            t1 = time()+1
            fps = 0
        end if
    end if
    return IUP_DEFAULT
end function

function map_cb(Ihandle ih)
    cdCanvas cdcanvas = cdCreateCanvas(CD_IUP, ih)
    cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas)
    cdCanvasSetBackground(cddbuffer, CD_WHITE)
    cdCanvasSetForeground(cddbuffer, CD_RED)
    return IUP_DEFAULT
end function

function key_cb(Ihandle /*ih*/, atom c)
    if c=K_ESC then return IUP_CLOSE end if -- (standard practice for me)
    if c=K_F5 then return IUP_DEFAULT end if -- (let browser reload work)
    if    find(c," ")   then draw(' ')  -- Clear
    elsif find(c,"+bB") then draw('+')  -- Blinker
    elsif find(c,"gG")  then draw('G')  -- Glider
    elsif find(c,"tT")  then draw('T')  -- Thunderbird
    elsif find(c,"xX")  then draw('X')  -- Cross
    end if
    IupStoreAttribute(hTimer, "RUN", "YES")
    return IUP_CONTINUE
end function

function timer_cb(Ihandle /*ih*/)
    IupUpdate(canvas)
    return IUP_IGNORE
end function

procedure main()
    IupOpen()
    canvas = IupCanvas("RASTERSIZE=390x390")
    IupSetCallbacks(canvas, {"MAP_CB", Icallback("map_cb"),
                             "ACTION", Icallback("redraw_cb")})
    dlg = IupDialog(canvas,`TITLE="%s", MINSIZE=350x55`, {title})
      -- (above MINSIZE prevents the title from getting squished)
    IupSetCallback(dlg, "KEY_CB", Icallback("key_cb"))
    IupShow(dlg)
    IupSetAttribute(canvas,"RASTERSIZE",NULL)
--  hTimer = IupTimer(Icallback("timer_cb"),40) -- 25fps (maybe)
    hTimer = IupTimer(Icallback("timer_cb"),100) -- 10fps
    if platform()!=JS then
        IupMainLoop()
        IupClose()
    end if
end procedure

main()
