Conway's Game of Life in SQL, Part 2

I showed my implementation of Conway's Game of Life in SQL to a few people, a co-worker pondered if it could be done without the stored procedure.  I gave it some thought, and came up with an implementation that relies on views. I used views for the simple reason that it made things easier to see and understand.  If a query can be written using views, the it can be written as straight SQL, but the results are generally uglier, messier, and can often be unreadable.  Since I'm using MySQL, I realize how bad views can be when it comes to performance, but since this is a proof of concept, and a toy anyway, I'm not too worried.  I honestly doubt any real-life application would ever require me to implement the Game of Life in SQL!

I started as I had earlier, by defining the table as holding all the live cells for each generation.

create table cell (
  generation int,
  x int, 
  y int,
  primary key (generation, x, y));

Then, I created a view to represent all the candidate position on the grids where we might find live cells on the next generation.  We can only find cells where there are cells for the current generation, and in all 8 neighbour positions of those cells:

create view candidate (generation, x, y) as 
  select generation, x-1, y-1 from cell union
  select generation, x,   y-1 from cell union
  select generation, x+1, y-1 from cell union
  select generation, x-1, y   from cell union
  select generation, x,   y   from cell union
  select generation, x+1, y   from cell union
  select generation, x-1, y+1 from cell union
  select generation, x,   y+1 from cell union
  select generation, x+1, y+1 from cell;

Next, I counted the number of live cells in the 3x3 square around each candidate.  This isn't quite the same as counting the neighbours, since it includes the current cell in the count.  We will need to take that into account in a bit.

create view neighbour_count (generation, x, y, count) as 
  select generation, x, y, 
         (select count(*) 
          from cell 
         where cell.x in (candidate.x-1, candidate.x, candidate.x+1)
           and cell.y in (candidate.y-1, candidate.y, candidate.y+1)
           and not (cell.x = candidate.x and cell.y = candidate.y)
           and cell.generation = candidate.generation)
    from candidate;

From the previous post, the rules of the game can be reduced to: a cell is alive in the next generation if

1. it has 3 neighbours
2. it has 2 neighbours and was alive in the current generation

Let's write this as a truth table:

Live?	Neighbours	Alive in the next generation
yes	less than 2	no
yes	2	YES
yes	3	YES
yes	more than 3	no
no	less than 3	no
no	3	YES
no	more than 3	no

If we count the cell in the neighbour count, we change our truth table:

Live?	# cells in 3x3 square	Alive in the next generation
yes	less than 3	no
yes	3	YES
yes	4	YES
yes	more than 4	no
no	less than 3	no
no	3	YES
no	more than 3	no

A cell will be alive in the next generation if it's alive and the number of live cells in the square is 3 or 4, or if the cell is dead and there are 3 cells in the square.  Let's rewrite the rules... again.

A cell will be alive in the next generation if

1. The 3x3 square has exactly 3 cells
2. The 3x3 square has exactly 4 cells and the current cell is alive.

So, we'll include a cell in the next generation according to these rules.  We can tell if a cell is alive by doing a left outer join on the cell table:

insert into cell (
  select neighbour_count.generation+1, neighbour_count.x, neighbour_count.y 
  from neighbour_count 
         left outer join cell 
              on neighbour_count.generation = cell.generation
             and neighbour_count.x = cell.x
             and neighbour_count.y = cell.y
  where neighbour_count.generation = (select max(generation) from cell)
    and (neighbour_count.count = 3 
         or (neighbour_count.count = 4 and cell.x is not null)));

Repeat the insert statement for each following generation.

Conway's Game of Life in... SQL?

Yesterday, I attended the Code Retreat hosted at Notman House and organized by Mathieu Bérubé.  It was a most enjoyable experience.  On the first session, I paired with Christian Lavoie, and we tried to implement Conway's Game of Life using... mysql.  Some people thought this was crazy, and I can't disagree.  At the same time, we were able to complete the solution in under 45 minutes, not a small feat.

Part of the rules of the Code Retreat is that you delete your code after each session.  We did, but I thought the solution was so easy to implement, I thought I'd try to recreate it at home.  I made some changes to the implementation, but the core of the idea is the same as what we wrote.

The first thing to consider is that in the Game of Life, we cannot have a fixed-length 2D array that holds the cells.  Indeed, the best way is to store only the coordinates of the live cells.  Any cell that's not live isn't store anywhere, since that's the state of all the cells in the infinite grid, and it's just impossible to store an infinite grid.  We assume a finite number of live cells to start with (which means we'll always have a finite number of cells).

These cells will be located in a rectangular area that's bounded by the minimum x, minimum y, maximum x and maximum y coordinates of the cells.  This means that we can restrict our processing to the positions within a rectangle that's just a little bigger than the bounding rectangle: we need to add a border one-position wide around the whole rectangle.

Then, for each cell within that rectangle, we decide if it should be alive in the next generation.  We simply ignore cells that die, by not adding them to the next generation.  The 4 rules of the game can be rewritten as two simpler rules:

1. If the current cell is alive, it stays alive if it as exactly 2 or 3 neighbours who are also alive
2. If the current cell is dead, it becomes alive if it has exactly 3 neighbours.

Using a little logic processing, we can further rewrite this as the following 2 conditions to be alive in the next generation:

1. If a cells has 3 neighbours
2. If a cell is alive and has 2 neighbours

So, we only add the cell to the next generation (insert it in the table) if it fits either of those rules.

Counting neighbours is also fairly easy.  We find how many cells exist that have their x and y coordinates one less, equal, or one more than the current x.  We have to include the current x and y to include cells exactly to the left, exactly to right, exactly above or exactly below the current cell.  We must, however, exclude the current cell, so if we know it's set, we subtract 1 from the total count.

Here is code close to what we came up with, with some modifications that came to me after the fact.

drop table if exists cells;
create table cells (
  generation int,
  x int,
  y int,
  primary key (generation, x, y));

drop procedure if exists iterate_generation;
delimiter $$
create procedure iterate_generation ()
  begin
  declare current_gen int;
  declare current_x int;
  declare current_y int;
  declare min_x int;
  declare max_x int;
  declare min_y int;
  declare max_y int;
  declare live int;
  declare neighbour_count int;

  select max(generation) into current_gen from cells;
  select min(x)-1, min(y)-1, max(x)+1, max(y)+1
    into min_x, min_y, max_x, max_y from cells
   where generation = current_gen;


  set current_x := min_x;
  while current_x <= max_x do
    set current_y := min_y;
    while current_y <= max_y do
      select count(1) into live from cells
       where generation = current_gen
         and x = current_x
         and y = current_y;
      select count(1) - live into neighbour_count from cells
       where generation = current_gen
         and x in (current_x - 1, current_x, current_x + 1)
         and y in (current_y - 1, current_y, current_y + 1);


      if neighbour_count = 3 || live = 1 and neighbour_count = 2
      then
        insert into cells (generation, x, y)
                   values (current_gen+1, current_x, current_y);
      end if;
      set current_y := current_y + 1;
    end while;
    set current_x := current_x + 1;
  end while;
end
$$
delimiter ;

Crazy? well, yes. And yet, surprisingly easy. And absolutely a whole lot of fun.