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

- it has 3 neighbours
- 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

A cell will be alive in the next generation if

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

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.

It is really amazing post, it really shows so many different things of database technology which people just ignore.

ReplyDelete