Wednesday, July 18, 2012

Conway's Game of Life in a MODEL clause

This post has no serious purpose. I was just fooling around with the MODEL clause when I got the idea that ITERATE could be used for modelling Conway's Game of Life. So that's what I did - just a little fun example of what MODEL can be used for. Sure it could be done in any number of other ways, I don't claim this to be a smart or efficient way, just fun ;-)

Conway's game of life models a population of cells in an twodimensional coordinate system with rules for how cells die, survive or reproduce from generation to generation:

  • Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

With a MODEL clause I can model these cells with x,y coordinates, ITERATE through the generations, and use RULES to calculate whether a cell die, survive or reproduce.

To view the output fairly nicely in SQL*PLUS I set these parameters:

SQL> set pagesize 60
SQL> set newpage 2
SQL> break on generation skip page
SQL> column generation new_value genvar noprint
SQL> ttitle left 'Generation: ' genvar skip 1
SQL> column cells format a60

Without further ado here's the SQL and a sample output:

SQL> with numbers as (
  2     select level n from dual
  3     connect by level <= 12
  4  ), start_cells as (
  5     select  5 x,  5 y from dual union all
  6     select  6 x,  5 y from dual union all
  7     select  5 x,  6 y from dual union all
  8     select  7 x,  7 y from dual union all
  9     select  8 x,  7 y from dual union all
 10     select  5 x,  8 y from dual union all
 11     select  6 x,  8 y from dual union all
 12     select  7 x,  8 y from dual
 13  )
 14  select generation
 15       , listagg(case cell when 1 then 'X' else ' ' end)
 16           within group (order by x) cells
 17  from (
 18     select generation, x, y, cell
 19     from (
 20        select x.n x
 21             , y.n y
 22             , nvl2(sc.x,1,0) cell
 23          from numbers x
 24         cross join numbers y
 25          left outer join start_cells sc
 26            on sc.x = x.n
 27           and sc.y = y.n
 28     )
 29     model
 30     dimension by (
 31        0 as generation
 32      , x
 33      , y
 34     )
 35     measures (
 36        cell
 37     )
 38     ignore nav
 39     rules upsert all iterate (10)
 40     (
 41        cell[iteration_number+1, any, any] =
 42           case sum(cell)
 43                [
 44                    generation = iteration_number,
 45                    x between cv()-1 and cv()+1,
 46                    y between cv()-1 and cv()+1
 47                ]
 48                - cell[iteration_number, cv(), cv()]
 49              when 2 then cell[iteration_number,cv(),cv()]
 50              when 3 then 1
 51              else 0
 52           end
 53     )
 54  )
 55  group by generation, y
 56  order by generation, y
 57  /


Generation:          0
CELLS
------------------------------------------------------------




    XX
    X
      XX
    XXX






Generation:          1
CELLS
------------------------------------------------------------




    XX
    X X
    X XX
     XXX
     X





Generation:          2
CELLS
------------------------------------------------------------




    XX
   XX XX
    X
    X  X
     X





Generation:          3
CELLS
------------------------------------------------------------




   XXXX
   X  X
    X XX
    XX






Generation:          4
CELLS
------------------------------------------------------------



    XX
   XXXX
   X
   XX XX
    XXX






Generation:          5
CELLS
------------------------------------------------------------



   X  X
   X  X
  X    X
   X  XX
   XX XX
     X





Generation:          6
CELLS
------------------------------------------------------------




  XX  XX
  XX   X
  XXXX  X
   XX  X
    XXX





Generation:          7
CELLS
------------------------------------------------------------




  XX  XX
 X   X XX
     XXXX
  X    X
   XXXX
     X




Generation:          8
CELLS
------------------------------------------------------------




  X   XXX
  X XX
     X
   X    X
   XXXX
     XX




Generation:          9
CELLS
------------------------------------------------------------



       X
   X XXX
   XXX X
   X X
   X  X
   X  XX
      X




Generation:         10
CELLS
------------------------------------------------------------



       X
   X X XX
  XX   X
  XX X
  XX XXX
     XXX
      XX



132 rows selected.

You can see how some cells die, some survive and some reproduce from generation to generation.

Let's take a look at bits of the SQL:

  2     select level n from dual
  3     connect by level <= 12

This creates a set of numbers from 1 to 12. I use it to define my grid size - in this case a 12x12 grid.

  5     select  5 x,  5 y from dual union all
  6     select  6 x,  5 y from dual union all
  7     select  5 x,  6 y from dual union all
  8     select  7 x,  7 y from dual union all
  9     select  8 x,  7 y from dual union all
 10     select  5 x,  8 y from dual union all
 11     select  6 x,  8 y from dual union all
 12     select  7 x,  8 y from dual

This is the starting population. The x,y coordinates of all live cells in generation zero.

 20        select x.n x
 21             , y.n y
 22             , nvl2(sc.x,1,0) cell
 23          from numbers x
 24         cross join numbers y
 25          left outer join start_cells sc
 26            on sc.x = x.n
 27           and sc.y = y.n

Here I create the 12x12 grid by cartesian join of numbers with itself. Then I give all live cells a cell value of 1 and all other cells a value of 0.

 30     dimension by (
 31        0 as generation
 32      , x
 33      , y
 34     )

This defines the indices of my "three dimensional array" which will be populated with the generation zero 12x12 grid from lines 20-27. "0 as generation" creates the dimension "generation" with a constant value of 0 for all the initial data.

 35     measures (
 36        cell
 37     )

There will be only one value (cell) for each position in the "three dimensional array".

 39     rules upsert all iterate (10)

This defines that I wish to iterate through the rules 10 times (meaning I will calculate Conway's Game of Life for 10 generations.) The "upsert all" is needed because I will create entries in the array that did not exist from the start.

 41        cell[iteration_number+1, any, any] =

This will set cell values of the next generation for any x,y value. iteration_number will be 0 in the first iteration, which therefore sets values for generation 0+1=1. Next iteration will have iteration_number=1 and set values for generation 1+1=2. Etc.
This assignment operator will therefore in each iteration create 12x12 new entries in our 3-D array. Each iteration calls the assignment 12x12 times to calculate the next generation. We assign into generation "iteration_number+1", so we want to calculate on values from generation = iteration_number.


 42           case sum(cell)
 43                [
 44                    generation = iteration_number,
 45                    x between cv()-1 and cv()+1,
 46                    y between cv()-1 and cv()+1
 47                ]
 48                - cell[iteration_number, cv(), cv()]

sum(cell)[...] gives me the sum of the values of cell for all indices defined within the square brackets. cv() is a shortcut for "current value" meaning that for each of the 12x12 calls to this calculation, cv() for x and cv() for y will return the actual x,y values for the specific call.
For example in the first iteration (iteration_number=0) the specific assignment call for x=5 and y=7 the cv() will generate sum(cell)[generation=0, x between 4 and 6, y between 6 and 8].
For the edge cases where cv() of either x or y is 12, this will become "between 11 and 13", but there are no entries for x=13 or y=13 in the array. The "ignore nav" in line 38 tells the calculation to treat these nonexistent data as zero rather than null.
So the sum(cell) is the sum of cell values of the 8 neighbors to the cell + the cell itself. Therefore I subtract the cell itself to get the sum of the neighbors only. That sum is the number of live neighbors of the cell.

 49              when 2 then cell[iteration_number,cv(),cv()]
 50              when 3 then 1
 51              else 0

And so I can apply Conway's rules. If the cell has two live neighbors nothing happens to the cell, it stays either dead or live so I carry over the value from the previous generation.
If the cell has three live neighbors it will always be live in the next generation (if it was live then it survived, if it was dead then it reproduced.)
All other cells (either too few or too many live neighbors) will be dead.

 14  select generation
 15       , listagg(case cell when 1 then 'X' else ' ' end)
 16           within group (order by x) cells
....
 55  group by generation, y
 56  order by generation, y

And finally I turn the generation,x,y data into one line for each y in each generation. "cells" will be a string with a space in each x position of dead cells and an X in each position of live cells. (listagg will work in version 11.2!)

SQL> break on generation skip page
SQL> column generation new_value genvar noprint
SQL> ttitle left 'Generation: ' genvar skip 1
SQL> column cells format a60

And these SQL*PLUS commands/parameters then format the output reasonably nicely with a "page" for each generation. The output needs a non-proportional font anyway, so if you are in TOAD or another GUI tool you probably need to "Execute as script" rather than getting your output in that nice proportional-font grid :-)

Speaking of TOAD... Here's another example just with a smaller grid and a different set of starting data:

SQL> with numbers as (
  2     select level n from dual
  3     connect by level <= 6
  4  ), start_cells as (
  5     select  4 x,  2 y from dual union all
  6     select  2 x,  3 y from dual union all
  7     select  5 x,  3 y from dual union all
  8     select  2 x,  4 y from dual union all
  9     select  5 x,  4 y from dual union all
 10     select  3 x,  5 y from dual
 11  )
 12  select generation
 13       , listagg(case cell when 1 then 'X' else ' ' end)
 14           within group (order by x) cells
 15  from (
 16     select generation, x, y, cell
 17     from (
 18        select x.n x
 19             , y.n y
 20             , nvl2(sc.x,1,0) cell
 21          from numbers x
 22         cross join numbers y
 23          left outer join start_cells sc
 24            on sc.x = x.n
 25           and sc.y = y.n
 26     )
 27     model
 28     dimension by (
 29        0 as generation
 30      , x
 31      , y
 32     )
 33     measures (
 34        cell
 35     )
 36     ignore nav
 37     rules upsert all iterate (4)
 38     (
 39        cell[iteration_number+1, any, any] =
 40           case sum(cell)
 41                [
 42                    generation = iteration_number,
 43                    x between cv()-1 and cv()+1,
 44                    y between cv()-1 and cv()+1
 45                ]
 46                - cell[iteration_number, cv(), cv()]
 47              when 2 then cell[iteration_number,cv(),cv()]
 48              when 3 then 1
 49              else 0
 50           end
 51     )
 52  )
 53  group by generation, y
 54  order by generation, y
 55  /


Generation:          0
CELLS
------------------------------------------------------------

   X
 X  X
 X  X
  X



Generation:          1
CELLS
------------------------------------------------------------


  XXX
 XXX




Generation:          2
CELLS
------------------------------------------------------------

   X
 X  X
 X  X
  X



Generation:          3
CELLS
------------------------------------------------------------


  XXX
 XXX




Generation:          4
CELLS
------------------------------------------------------------

   X
 X  X
 X  X
  X


30 rows selected.

These data will repeat like that for ever. There are other patterns that also repeat (read the Wikipedia article I link to above) and this particular one is called the TOAD ;-)

Anyway, this was just for fun, nothing else...

No comments:

Post a Comment