SQL-based Game of Life from Code Retreat 2015

Last weekend I took part in my second Code Retreat event. The code is supposed to be deleted after the end, but like a good first world anarchist I saved one of them.

So here it is - SQL-based game of life.

Schema and test fixtures

It's all SQLite.

First we need a table to hold our simulations. It will be one table indexed by simulation name, generation number, x, and y listing all live cells.

Grid has no bounds, and can potentially be as big as your database allows.

CREATE TABLE life(
  simulation string,
  generation int,
  x int,
  y int
);

To run simulation we feed it initial conditions. Here's some test data. Of course you'll use real data instead:

INSERT INTO life VALUES
  ("line", 0, 0, 0),
  ("line", 0, 1, 0),
  ("line", 0, 2, 0);
INSERT INTO life VALUES
  ("glider", 0, 1, 0),
  ("glider", 0, 2, 1),
  ("glider", 0, 0, 2),
  ("glider", 0, 1, 2),
  ("glider", 0, 2, 2);

And now we need to code the game.

Counting cell's neighbours

It's tempting to do a double join over x and then y, but it's actually much better to simply create helper table and join that once:

INSERT INTO neighbour_coordinates VALUES (-1,-1), (-1,0), (-1,+1), (0,-1), (0,+1), (+1,-1), (+1,0), (+1, +1);

CREATE VIEW live_neighbours AS
  SELECT simulation, generation, x+dx as xx, y+dy as yy, count(*) as cnt
  FROM life
  JOIN neighbour_coordinates 
  GROUP BY simulation, generation, xx, yy;

Isn't SQL great? We already have neighbour counts for every cell in the simulation with one or more neighbours.

LEFT OUTER JOIN of DOOM

Now it's simple step - for cells which are alive we calculate them as alive if they have 2 or 3 neighbours in previously calculated view - for cells which are dead if they have exactly 3 neighbours. That's a simple JOIN on x and y... Oh wait, we're not joining data, we're joining existence or nonexistence of cell in life table, so we need a special kind of JOIN:

CREATE VIEW current_status AS
  SELECT
    live_neighbours.simulation,
    live_neighbours.generation,
    live_neighbours.xx as x,
    live_neighbours.yy as y,
    live_neighbours.cnt,
    (life.simulation NOT NULL) as alive
  FROM live_neighbours
  LEFT OUTER JOIN life ON
    life.x = live_neighbours.xx AND
    life.y = live_neighbours.yy AND
    life.simulation = live_neighbours.simulation AND
    life.generation = live_neighbours.generation;

SQL is friendly and readable, am I right?

What's alive next generation?

Well, that's fairly straightforward:

CREATE VIEW alive_next_generation AS
  SELECT simulation, generation+1 as generation, x, y
  FROM current_status
  WHERE (alive AND (cnt = 2 OR cnt = 3)) OR
        ((NOT alive) AND (cnt = 3));

Where are my stored procedures?

Unfortunately here we ran into a horrible tragedy, as SQLite doesn't support stored procedures, so we needed a tiny Ruby wrapper. Obvious Bobby Tables exploit included as a bonus:

simulation = ARGV[0]
generation = ARGV[1].to_i
sql = "INSERT INTO life SELECT * FROM alive_next_generation WHERE simulation = '%s' AND generation = %d;" % [simulation, generation]
IO.popen("sqlite3 life.db", "w") do |fh|
  fh.puts sql
end

Querying database

As Ruby code for updating database was ready, Copy&Paste Design Pattern was used to make it also work as data querying, if for some reason you don't want to do so from SQLite console:

simulation = ARGV[0]
generation = ARGV[1].to_i
sql = "SELECT x, y FROM life WHERE simulation = '%s' AND generation = %d;" % [simulation, generation]
IO.popen("sqlite3 life.db", "w") do |fh|
  fh.puts sql
end

Test driver

Of course everything was driven in a very  TDD way, more or less. Here's test driver Rakefile:

def update(simulation, generations)
  generations.each do |generation|
    system "./update_simulation #{simulation} #{generation}"
  end
end

def query(simulation, generation)
  `./query_simulation #{simulation} #{generation}`.lines.sort
end

task "init" do
  system "trash life.db"
  system "sqlite3 life.db <schema.sql
  system "sqlite3 life.db <fixtures.sql
end

task "test" => ["init"] do
  update("line", 1..2)
  raise "Stayed the same" if query("line", 0) == query("line", 1)
  raise "Not back to original status" if query("line", 0) != query("line", 2)

  update("glider", 1..4)

  glider0 = `echo "select x+1 as x, y+1 as y from life where simulation = 'glider' and generation = 0;" | sqlite3 life.db`.lines.sort
  glider4 = `echo "select x, y from life where simulation = 'glider' and generation = 4;" | sqlite3 life.db`.lines.sort
  raise "Did not glide" unless glider0 == glider4
end

What's next?

Next step would obviously be ASCII-Artifying output instead of just dumping a list of X/Y coordinates as a table - and possibly similar ASCII-Art reader. Unfortunately 45 minute limit on the round prevented that from happening.

I'd like to thank my coding partner for cooperation in writing this. For understandable reasons I'm not going to do any doxxing.