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:
- If the current cell is alive, it stays alive if it as exactly 2 or 3 neighbours who are also alive
- If the current cell is dead, it becomes alive if it has exactly 3 neighbours.
- If a cells has 3 neighbours
- If a cell is alive and has 2 neighbours
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.