SQL-based Game of Life refactored

A couple weeks ago I posted SQL-based Game of Life. It was rather ridiculous, with 3-levels of VIEWs, one of them including LEFT OUTER JOIN.

I revisited the problem for some refactoring and it turns out solution is far simpler.

Rules of game of life

Standard rules are:

• cell's neighbours are all cells next to the cell
• cell is not its own neighbour
• cell becomes live if it was alive and has 2 or 3 live neighbours
• cell becomes dead if it was dead and has 3 live neighbours

But I thought, what if we tweaked them a bit so every cell is considered its own neighbour as well? Mathematically tweaking definition:

• cell's neighbours are all cells next to the cell
• cell is its own neighbour
• cell becomes alive if it was alive and has 3 or 4 live neighbours
• cell becomes dead if it was dead and has 3 live neighbours

That might or might not lead to simpler query. But those numbers are weirdly close, what if instead we did this:

• cell's neighbours are all cells next to the cell
• cell is 0.5 of its own neighbour
• cell becomes alive if it was alive and has 2.5 or 3.5 live neighbours
• cell becomes dead if it was dead and has 3 live neighbours

Wait, doesn't that simply mean...

• cell's neighbours are all cells next to the cell
• cell is 0.5 of its own neighbour
• cell becomes alive if it has between 2.5 and 3.5 live neighbours

So it turns out we don't need to check alive/dead at all, leading to really simple code to which I'll get soon. Especially if we multiply weight by 2 to avoid floats - so cell counts as 1-weight neighbour and all cells around it count as 2-weight neighbours - and then we look for any total weight between 5 and 7.

Does that work with other rules?

For a while I thought it's a hack for standard Game of Life, and it wouldn't generalize to other types, but it totally would. If for example live cells stay live at 1, 6, or 7 neighbours, and dead ones at 2, 4, or 8, then we check for total in [3,13,15,4,6,16]. Or you could weight them at 10/1 instead of 1/2, then rules would be in [11,16,17,2,4,8].

I didn't use this generalization is the code, as code is a tiny bit simpler for standard case, but it's really tiny difference.

The code

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

CREATE TABLE neighbour_coordinates(
  dx int,
  dy int,
  weight int
);

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

CREATE VIEW alive_next_generation AS
  SELECT
    simulation,
    generation+1 AS generation,
    x+dx as x,
    y+dy as y
  FROM life
  JOIN neighbour_coordinates
  GROUP BY simulation, generation, life.x+dx, life.y+dy
  HAVING SUM(weight) BETWEEN 5 and 7;

Driver being exactly as before. That's ridiculously simple compared with initial solution.

MongoDB rant

And then I thought - how about doing this in MongoDB? And oh my god, that aggregation pipeline...

MongoDB JSON-document model is the sweetest thing ever in the world of databases, and it's interface is OK for simple queries, but it seriously just needs a real query language. So far every time I had to do anything nontrivial in MongoDB I did it in Ruby on application side, and I'm not unusual here.

SQL world is on the other end of the scale, with literally the worst document model ever invented, but fairly adequate query language. I wouldn't call SQL "good", but compared to monstrosities required by mongo for even fairly straightforward stuff...

Did anybody ever manage to get best of both worlds with some document model based on JSON or similar, and adequate query language?

I know some RDBMSs have JSON boltons but they're half-supported bullshit, and SQL is just adequate in comparison to what Mongo requires, not by any objective standard, so I'd rather not get there.

Some NoSQLs like MongoDB for some reason feel they don't need any kind of real querying language, just some $-trees, but that doesn't get anywhere close to adequate even for rather simple uses and it just moves querying to application side hacks.

I guess solr/lucene is sort of doing both sides decently, but it's a fairly special kind of NoSQL, and for many reason difficult to use as primary database. (don't even ask what kind of hackery I've done with it over years).

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.