05 June 2014

The SQL of The Game of Life

Joe finds a reference to Conway's Game of Life whilst clearing out his desk, and is suddenly gripped with nostalgia. It wasn't just flares, mullets and disco, but simple computer games in interpreted basic. Somehow, Conway s Game of Life was too intriguing to be abandoned in the attic. Can it be implemented in SQL? Joe sets up a challenge.

Joe finds a reference to Conway

Nostalgia

Every few years, you need to go to the garage and pull out the old stuff. By “old stuff” I mean the physical things – garages attract many strange objects like broken toys, old magazines and unused tools. A few years ago, a friend of mine took his kids to help clean out grandma’s attic when his mother died.

His daughter grabbed the trunk with her aunt’s old clothes. Some things had aged like fine wine into “vintage clothing” since then 1970’s, some had become Halloween costumes. His son found a box of 45 RPM vinyl records.

  • “Hey, Dad, what are these things?”
  • “Records.”
  • “Of what?”
  • “Music. These are stone age CDs. They are probably worth a few bucks at the used bookstore.”
  • “How many songs on this thing?”
  • “One on each side.”
  • “No, really! How did you live like that?”

The hardware might be dead now, but the music is still good. It is the same way with software. I pulled out some of my old articles, clippings and books from the garage this month. In particular, I found some things on cellular automate and Conway’s Game of Life. John Horton Conway is a name you should know if you deal with recreational math and computer science.

Conway’s Game of Life

This was invented in 1970, but became a geek fad in the 1980’s. It was easy to program in BASIC or Pascal and it looked pretty on a small screen.

1999-imgDC.gif

For us databases guys, we know that this is where Dr. Codd started before he invented the Relational Model. If you want to read it, you can download it athttp://ebookee.org/E-F-Codd-Cellular-Automata_2164601.html

 Imagine a planar grid of cells in which strange creatures I called Merkles live. These are simple creatures that only know about the eight cells in their immediate neighborhood.

The grid starts at time zero with Merkles sprinkled in it. Every cycle, a Merkle looks at his neighborhood and follows these rules for the next cycle:

  1. If the neighborhood has zero or one neighbor, the poor Merkle dies of loneliness.
  2. If the neighborhood has four or more neighbors, the poor Merkle dies of overcrowding.
  3. If the neighborhood has two or three neighbors, the Merkle lives to see the next cycle.
  4. Any empty cell with exactly three live neighbors grows a Merkle.

If you want more details and to see some simple animations, look up Conway’s Game of Life (Wikipadia).

1999-imgE7.gifWhen you gave the Game of Life as a programming assignment, the bad programmers would use bit flags (0 for empty cells and 1 for a Merkle) because it is the most direct and obvious approach. But that decision leads to two grid arrays, one of the odd numbered cycles and oen for the even numbered cycles. A simple flag in the program keeps track of which of ht two arrays is current. A simple loop on the current grid looks at each cell’s neighborhood and marks the corresponding cells in the next generation gird.

But there is a better way, discovered by Ward Christensen. Create an array of tiny integers and use ten (hot one) for a Merkle and zero for an empty cell. In the first pass, scan they array for cells with a ten; when you find one, add one to each of its neighbors. Now make the second pass. When you find a three (newborn Merkle) or a 12 or 13 (survivor Merkle), set it to ten. Zero out any other values.

The real performance improvement in the Christensen algorithm came from only scanning the occupied cells. Most of the grid will be empty, even if the starting configuration was packed. Over population leads to a high initial death rate. That does not mean that the grid will necessarily stabilize at some point in time.

Generalizing the Lessons of Life

Changing the rules for the Merkles will give us slightly different worlds. There is more information this topic than you really want to know at http://mathworld.wolfram.com/topics/CellularAutomata.html. This site has a list of rules and demonstrations of the outputs,

One surprise is that there are configurations which can only be initial configurations (aka “Garden of Eden”). There are proofs that certain cellular automata have to have a “Garden of Eden” if they meet certain criteria, but the proof does not show them to you. The first “Garden of Eden” was not found until 1971, and at least three are now known. It is not, however, known if a pattern exists which has a father pattern, but no grandfather pattern.

Another family of cellular automata has two (or more) types of creatures in the grid and the rules involve how they interact. My favorite example

http://www.theatlantic.com/magazine/archive/2002/04/seeing-around-corners/2471/

In this imaginary world, the grid is populated with Red Merkles and Blue Merkles. Every cell is occupied and then we start the game. A Merkle is unhappy if its neighborhood has less than (n) neighbors of its own color. Two unhappy Merkles can switch places if one or both of them increase their happiness.

In a few cycles, the grid becomes segregated neighborhoods. , Economist Thomas C. Schelling created this simple model to study segregated neighborhoods in the US in the 1970’s. While racism might account for some of the U-shaped distribution of race in neighborhoods, the stronger factor is the sum of individual preferences.

You can see some QuickTime animations of Merkleville at these sites:

Well, Celko has been blathering. Let’s get to some conclusions and general principles that help us think about data.

  1. Individuals in a social environment interact, but only with their neighbors. How many people outside your Google circles, Facebook or email contact lists?
  2. The members of social systems work in parallel. Sudden changes are not magic or random, but they can be surprising.
  3. Complex patterns in data arise from simple underlying rules.
  4. Simple models can reveal those rules, or at least a simplified version of them.

Hey, I have insights on social networks and how things can go viral! I feel smarter. I hope that you do, too.

Your Assignments:

Obviously SQL does not have arrays, so you need to think a way to model a grid. The classic way in SQL has been this skeleton schema.

The two coordinate columns might also have a BETWEEN constraint to mimic the range declaration in procedural languages that have arrays. You might also add a constraint to the Merkle’s values.

First Assignment:

Build a 10 by 10 Schelling model in SQL. That means the Grid might be declared as:

You will need a procedure to load the initial grid and a procedure to swap unhappy Merkles. You can be creative here.

Second Assignment:

Write a stored procedure that will play Conway’s Game of Life. You will need to load the grid with a starting position, then one to do each cycle.

  • Hint: do you really need to have complete grid to do this or can you use a sparse model?
  • Hint: Spend some time on a “neighborhood query”
  • Hint: The MERGE statement can do inserts, updates and deletes in parallel which is how Life is supposed to work.

Keep up to date with Simple-Talk

For more articles like this delivered fortnightly, sign up to the Simple-Talk newsletter

This post has been viewed 13440 times – thanks for reading.

Tags: ,

  • Rate
    [Total: 8    Average: 3.8/5]
  • Share

Joe Celko

View all articles by Joe Celko

  • Phil Factor

    The Game of Life in SQL.

    /*How is this for a solution, Joe. I bumped the grid up to 20 as a 10*10 got into a stable form too quickly */
    –delete any existing grid table
    IF EXISTS (
    SELECT *
      
    FROM information_schema.Tables
      
    WHERE TABLE_TYPE =‘BASE TABLE’
      
    AND table_schema = ‘dbo’
      
    AND TABLE_NAME = ‘Grid’)
    DROP TABLE Grid
    GO
    –Create the grid table
    CREATE TABLE Grid
    (i INTEGER NOT NULL
        
    CHECK (i BETWEEN 1
        
    AND 20),
        
    j INTEGER NOT NULL
        
    CHECK (j BETWEEN 1
        
    AND 20),
        
    PRIMARY KEY (i,j),
        
    merkle integer NOT NULL
        
    CHECK (merkle IN (0, 1)));
    GO
    –delete any number view
    IF EXISTS (
    SELECT *
      
    FROM information_schema.Tables
      
    WHERE TABLE_TYPE =‘VIEW’
      
    AND table_schema = ‘dbo’
      
    AND TABLE_NAME = ‘OneToTwenty’)
    DROP VIEW OneToTwenty
    GO
    –create the number view
    CREATE VIEW OneToTwenty AS
    SELECT
    1 AS number UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
    UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8
    UNION ALL SELECT 9 UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12
    UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL SELECT 15 UNION ALL SELECT 16
    UNION ALL SELECT 17 UNION ALL SELECT 18 UNION ALL SELECT 19 UNION ALL SELECT 20
    GO

    IF EXISTS ( SELECT 1
      
    FROM information_schema.Routines
      
    WHERE ROUTINE_NAME = ‘UpdateGrid’
      
    AND ROUTINE_TYPE=‘PROCEDURE’
      
    AND ROUTINE_SCHEMA=‘dbo’)
        
    DROP PROCEDURE UpdateGrid
    GO
    CREATE PROCEDURE UpdateGrid
      
    AS
    UPDATE
    grid
    SET merkle = updated.merkle
    FROM Grid
      
    INNER JOIN
    (
    SELECT –Merkle,
        
    i,j,
      
    CASE WHEN merkle=1
        
    AND neighbours < 2 THEN 0
      
    –If the neighborhood has zero or one neighbor, the Merkle dies of loneliness.
        
    WHEN merkle=1
        
    AND neighbours BETWEEN 2
        
    AND 3 THEN 1
      
    –If the neighborhood has two or three neighbors, the Merkle lives to see the next cycle.
        
    WHEN merkle=0
        
    AND neighbours = 3 THEN 1
      
    –Any empty cell with exactly three live neighbors grows a Merkle.
      
    ELSE 0 END AS Merkle
      
    FROM
      
    (
      
    SELECT merkle.merkle, merkle.i, merkle.j,
          
    COALESCE(sw.merkle,0)+COALESCE(s.merkle,0)
           +
    COALESCE(se.merkle,0)+COALESCE(e.merkle,0)
           +
    COALESCE(ne.merkle,0)+COALESCE(n.merkle,0)
           +
    COALESCE(nw.merkle,0)+COALESCE(w.merkle,0) AS neighbours
      
    FROM grid merkle
        
    LEFT OUTER JOIN grid SW ON merkle.i=SW.i+1
        
    AND merkle.j=SW.j1
        
    LEFT OUTER JOIN grid S ON merkle.i=S.i
        
    AND merkle.j=S.j1
        
    LEFT OUTER JOIN grid SE ON merkle.i=SE.i1
        
    AND merkle.j=SE.j1
        
    LEFT OUTER JOIN grid E ON merkle.i=E.i1
        
    AND merkle.j=E.j
        
    LEFT OUTER JOIN grid NE ON merkle.i=NE.i1
        
    AND merkle.j=NE.j+1
        
    LEFT OUTER JOIN grid N ON merkle.i=N.i
        
    AND merkle.j=N.j+1
        
    LEFT OUTER JOIN grid NW ON merkle.i=NW.i+1
        
    AND merkle.j=NW.j+1
        
    LEFT OUTER JOIN grid W ON merkle.i=W.i+1
        
    AND merkle.j=W.j) f
    ) updated
      
    ON grid.i=updated.i
      
    AND grid.j=updated.j
    GO

    IF EXISTS (
    SELECT *
      
    FROM information_schema.Tables
      
    WHERE TABLE_TYPE =‘VIEW’
      
    AND table_schema = ‘dbo’
      
    AND TABLE_NAME = ‘TheBoard’)
      
    DROP VIEW TheBoard
    GO  
    CREATE VIEW TheBoard
    AS
    SELECT
    MAX (CASE WHEN i=1 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=2 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=3 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=4 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=5 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=6 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=7 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=8 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=9 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=10 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=11 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAAX (CASE WHEN i=12 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=13 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=14 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=15 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=16 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=17 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=18 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=19 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END)+‘ ‘+
    MAX (CASE WHEN i=20 THEN CASE WHEN Merkle=1 THEN ‘X’ ELSE ‘ ‘ END ELSE ‘ ‘ END) AS Life
    FROM grid GROUP BY j
    GO

    DECLARE @ii INT
    SELECT
    @ii=30 –the number of generations we want to do
    –fill in the grid
    DELETE FROM grid
    INSERT INTO grid (i,j,merkle)
        
    SELECT i.number, j.number, CHARINDEX(LEFT(NEWID(),1),‘0123456789ABCDEF’)% 2
        
    FROM OneToTwenty i
                
    CROSS JOIN OneToTwenty j
    SET NOCOUNT ON
    WHILE
    @ii>0
      
    BEGIN
       EXECUTE
    UpdateGrid –calculate what lives and dies
      
    SELECT life FROM TheBoard –and display it.
      
    SELECT @ii=@ii1
      
    END  

  • Robert young

    The Real Game of Life
    This is a Real Game of Life: http://en.wikipedia.org/wiki/John_B._Calhoun#Norway_rat_experiments

    I cursory web search doesn’t reveal that Conway used Calhoun’s experiment as inspiration. But Calhoun’s experiment might give those who preach "we ain’t makin’ enough babies" reason to reconsider.

  • D

    College Memories
    In college, I implemented it in assembly. What a nasty assignment that was. Then later I did a hexagonal Game of Life in Java.

    "Can it be implemented in SQL?"

    The madness will never end!

  • ChipDale66

    please correct grammar
    this paragraph makes no sense because of missing words in the first sentance – can only what?

    One surprise is that there are configurations which can only initial configurations (aka “Garden of Eden”). There are proofs that certain cellular automata have to have a “Garden of Eden” if they meet certain criteria, but the proof does not show them to you. The first “Garden of Eden” was not found until 1971, and at least three are now known. It is not, however, known if a pattern exists which has a father pattern, but no grandfather pattern.

    Ed: Somehow the word ‘be’ got deleted somewhere in the process. Now fixed

  • Jason Wolfkill

    My solution to Assignment #2
    I posted my solution to Assignment #2 (the Game of Life), which uses a single join, on my blog here: THE SQL OF THE GAME – CONWAY’S GAME OF LIFE

    Thanks for the challenge!

    Ed: A good post!

  • puzsol

    SQL2008 + Visual
    Ok… so I’m late to the party… but hey someone had to do it… run this, then look at the spatial results tab, and scroll through the columns of spatial data… viola! animation (sort of).

    I know the sql is not the most optimised, efficient, etc… but hey, this was for fun yes?

    if OBJECT_ID(‘MerkelLife’, ‘U’) is not null
    begin
    drop table MerkelLife
    end
    if OBJECT_ID(‘MerkelNeighbour’, ‘U’) is not null
    begin
    drop table MerkelNeighbour
    end
    if OBJECT_ID(‘MerkelCell’, ‘U’) is not null
    begin
    drop table MerkelCell
    end

    create table MerkelCell
    ( ID int not null constraint PK_MerkelCell primary key
    , Life geometry not null
    , Nonlife geometry not null
    )

    go
    create table MerkelNeighbour
    ( ID int not null constraint FK_MerkelCell_Center foreign key references MerkelCell(ID)
    , Neighbour int not null constraint FK_MerkelCell_Neighbour foreign key references MerkelCell(ID)
    )
    go

    create table MerkelLife
    ( Iteration int not null
    , ID int not null constraint FK_MerkelCell_Life foreign key references MerkelCell(ID)
    )
    go

    declare @x int, @y int, @poly nvarchar(max)

    set @x = 0;
    set @y = 0;

    loop:

    set @poly = ‘CIRCULARSTRING(‘
    + cast(@x + 0.45 as nvarchar) + ‘ ‘ + cast(@y as nvarchar) + ‘, ‘
    + cast(@x as nvarchar) + ‘ ‘ + cast(@y + 0.45 as nvarchar) + ‘, ‘
    + cast(@x – 0.45 as nvarchar) + ‘ ‘ + cast(@y as nvarchar) + ‘, ‘
    + cast(@x as nvarchar) + ‘ ‘ + cast(@y – 0.45 as nvarchar) + ‘, ‘
    + cast(@x + 0.45 as nvarchar) + ‘ ‘ + cast(@y as nvarchar) + ‘)’

    insert into MerkelCell (ID, Life, NonLife)
    select @x + 10 * @y
    , geometry::Parse(‘CURVEPOLYGON(‘ + @poly + ‘)’)
    , geometry::Parse(@poly)

    insert into MerkelLife
    select 1, @x + 10 * @y
    where RAND() >= 0.5

    set @x = @x + 1
    if (@x > 9)
    begin
    set @y = @y + 1
    set @x = 0
    end

    if (@y < 10)
    begin
    goto loop;
    end

    print ‘Our grid for the game of life’
    –select * from MerkelCell

    ;with dirs as
    ( select ID, case ID%10 when 9 then -9 else 1 end as r
    , case ID%10 when 0 then +9 else -1 end as l
    , case ID/10 when 9 then -90 else 10 end as u
    , case ID/10 when 0 then +90 else -10 end as d
    from MerkelCell)
    insert into MerkelNeighbour
    select ID, ID+r from dirs
    union
    select ID, ID+r+u from dirs
    union
    select ID, ID+u from dirs
    union
    select ID, ID+l+u from dirs
    union
    select ID, ID+l from dirs
    union
    select ID, ID+l+d from dirs
    union
    select ID, ID+d from dirs
    union
    select ID, ID+d+r from dirs

    print ‘Our neighbours in the game of life’
    –select * from MerkelNeighbour

    declare @i int
    set @i = 1

    — Show the starting grid
    /*
    select c.ID, case when l.ID is null then c.Nonlife else c.Life end as Cell
    from MerkelCell c
    inner join MerkelLife l on l.ID = c.ID and l.Iteration = @i
    */

    while @i <= 25
    begin
    insert into MerkelLife (ID, Iteration)
    select n.ID, @i + 1
    from
    (
    select n.ID, count(*) as neighbours
    from MerkelLife l
    inner join MerkelNeighbour n on n.Neighbour = l.ID
    where l.Iteration = @i
    group by n.ID
    ) as n
    left join MerkelLife l on l.ID = n.ID and l.Iteration = @i
    where (n.neighbours = 3) or (n.neighbours = 2 and l.ID is not null)

    set @i = @i + 1
    /*
    — Show the next grid
    select c.ID, case when l.ID is null then c.Nonlife else c.Life end as Cell
    from MerkelCell c
    inner join MerkelLife l on l.ID = c.ID and l.Iteration = @i
    */
    end

    select c.ID
    , case when l.g1 is null then c.Nonlife else c.Life end as gen1
    , case when l.g2 is null then c.Nonlife else c.Life end as gen2
    , case when l.g3 is null then c.Nonlife else c.Life end as gen3
    , case when l.g4 is null then c.Nonlife else c.Life end as gen4
    , case when l.g5 is null then c.Nonlife else c.Life end as gen5
    , case when l.g6 is null then c.Nonlife else c.Life end as gen6
    , case when l.g7 is null then c.Nonlife else c.Life end as gen7
    , case when l.g8 is null then c.Nonlife else c.Life end as gen8
    , case when l.g9 is null then c.Nonlife else c.Life end as gen9
    , case when l.g10 is null then c.Nonlife else c.Life end as gen10
    , case when l.g11 is null then c.Nonlife else c.Life end as gen11
    , case when l.g12 is null then c.Nonlife else c.Life end as gen12
    , case when l.g13 is null then c.Nonlife else c.Life end as gen13
    , case when l.g14 is null then c.Nonlife else c.Life end as gen14
    , case when l.g15 is null then c.Nonlife else c.Life end as gen15
    , case when l.g16 is null then c.Nonlife else c.Life end as gen16
    , case when l.g17 is null then c.Nonlife else c.Life end as gen17
    , case when l.g18 is null then c.Nonlife else c.Life end as gen18
    , case when l.g19 is null then c.Nonlife else c.Life end as gen19
    , case when l.g20 is null then c.Nonlife else c.Life end as gen20
    , case when l.g21 is null then c.Nonlife else c.Life end as gen21
    , case when l.g22 is null then c.Nonlife else c.Life end as gen22
    , case when l.g23 is null then c.Nonlife else c.Life end as gen23
    , case when l.g24 is null then c.Nonlife else c.Life end as gen24
    , case when l.g25 is null then c.Nonlife else c.Life end as gen25
    from MerkelCell c
    left join
    (
    select *
    from (
    select ID, ‘g’+ cast(Iteration as nvarchar) as col, ID as x
    from MerkelLife
    ) as s
    PIVOT
    (
    max(x)
    FOR col IN (g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11, g12, g13, g14, g15, g16, g17, g18, g19, g20, g21, g22, g23, g24, g25)
    )AS p
    ) l on l.ID = c.ID

  • Paul Brewer

    Geometric Solution
    Hi,
    Here’s another solution based on geometry, using the intersect method though. Polygon’s (1.2 times the cell size) are calculated from Merkle cell x, y axis coordinates and are used to count adjacent (overlapping) neighbour cells.

    https://paulbrewer.wordpress.com/2015/05/03/sql-server-cellular-automation-using-geometry/

    The setup script includes a pre-populated table with 4 ‘Oscillating’ patterns, a stored procedure is provided that iterates through x cycles apply Conway’s rule to the previous iteration each time to construct a new pattern. Results are presented via the spatial tab in SQL Server Management studio.

    Each iteration of the ‘Pattern Generator’ takes about 20 seconds on my home computer, at the very least my solution is good for benchmarking and comparing SQL Server instances.

    Regards
    Paul

  • Paul Brewer

    Performance Testing
    I’ve made some improvements to the performance of my solution (adding an 8 adjacent cells join which was faster than spatial methods for cell elimination) . If processing just a simple ‘Blinker’ oscillating pattern, each iteration completes in under a second. The lab setup script creates 4 quite large starting patterns hence 5 second iteration times.

    At every interval ((interval * 6) + 1) , the new pattern(s) match the first pattern because of their oscillation cycles (2 Cycle and 3). I think mine would scale quite well too with larger patterns, It a million miles away from the world record though. This is a quote from Wickipedia –

    The 6,366,548,773,467,669,985,195,496,000th (6 octillionth) generation of a Turing machine, made in the game of Life, computed in less than 30 seconds on an Intel Core Duo 2 GHz CPU using Golly in Hashlife mode

  • Paul Brewer

    Complete Solution
    Just reread the challenge criteria and realized I’ve jumped ahead a few stages by offering a complete and tested solution. It wasn’t that difficult, 10 hours programming.

    There are some good parts to my solution (dynamic grid construction with geometric referencing of cells) and some bad bit’s (8 self joins in the cell elimination rules) but is a complete and tested solution.

    It’s very ‘Version 1’, I think you need to solve something before you performance tune it. ‘Slow and Correct’ is better than ‘Fast but Flawed’ in any solution first draft.

    Regards
    Paul

  • Paul Brewer

    Complete Solution
    Just reread the challenge criteria and realized I’ve jumped ahead a few stages by offering a complete and tested solution. It wasn’t that difficult, 10 hours programming.

    There are some good parts to my solution (dynamic grid construction with geometric referencing of cells) and some bad bit’s (8 self joins in the cell elimination rules) but is a complete and tested solution.

    It’s very ‘Version 1’, I think you need to solve something before you performance tune it. ‘Slow and Correct’ is better than ‘Fast but Flawed’ in any solution first draft.

    Regards
    Paul

  • Paul Brewer

    Grid Referencing
    Hi,
    I’d like to point out that the dynamic geometric referencing query in my solution means it will be able to generate and visualize ‘Glider’ patterns that move across grids. A temporary grid is constructed each iteration that bounds all live Merkels, It’s the ‘Sparse’ model, Merkles exist simple as x and y axis coordinates between pattern generations/iterations.
    Regards
    Paul

  • Paul Brewer

    Problem
    One problem with my solution is scaling where a pattern produces a ‘Glider’. The orginal pattern stays in place, the glider moves and the conceptual grid grows with each iteraction. I’ll change the Grid in Version 2 so it becomes a frame, 1 cell thick for each pattern.

  • Paul Brewer
  • Paul Brewer

    Apologies for all the spam ..
    My solution can now handle ‘Gosper Glider Guns’, it scales and is pretty much complete.

    The trick was to use geometry for the ‘Merkle Stays Alive’ rule, geometric intersects with 2 or 3 adjacent Merkles. For the dead cell ‘Merkle Comes to Life’ rule, a nicely indexed set based query works better.

    There are prepopulated patterns in the setup script to test and prove all this. 10 iterations with 4 oscillating patterns and a Gosper Glider Gun pattern take 35 seconds on my machine which isn’t too bad really. SQL Server is never going to compete with programmatic arrays but we can store results as we go which might offer other opportunities for exploring the chaos!?

  • Paul Brewer

    Set Based Solution
    Here’s a simple, completely set based solution that performs and scales well. It generates about 10 new patterns a second, from an initial starting set of 6 complex patterns (4 oscillators and 2 glider guns). I’ve run it into the 10,000’s iteration range without problems.

    https://paulbrewer.wordpress.com/ca_setup_io/

    Regards
    Paul

  • Paul Brewer

    Hekaton
    Hi,
    I’ve developed a 3rd solution, in Hekaton this time.

    https://paulbrewer.wordpress.com/2015/05/03/sql-server-cellular-automation-using-geometry/

    Each of the 3 solutions stress different areas of SQL Server.
    – Geometry stresses CPU
    – Set based queries stress the IO subsystem
    – Hekaton stresses memory
    All 3 have been bundled into a stress testing application which SQL Server Central is publishing on Monday.

    I apologies for spamming this thread, it was quite an inspirational, exciting and interesting challenge.

    Regards
    Paul