Click here to monitor SSC
  • Av rating:
  • Total votes: 7
  • Total comments: 16
Joe Celko

The SQL of The Game of Life

05 June 2014
Joe finds a reference to Conway

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, Conways Game of Life was too intriguing to be abandoned in the attic. Can it be implemented in SQL? Joe sets up a challenge.

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.

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).

When 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.

CREATE TABLE Grid

(i INTEGER NOT NULL,

  j INTEGER NOT NULL,

  PRIMARY KEY (i,j),

  merkle <data type> NOT NULL);

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:

CREATE TABLE Grid

(i INTEGER NOT NULL

    CHECK (i BETWEEN 1 AND 10),

j INTEGER NOT NULL

    CHECK (j BETWEEN 1 AND 10),,

PRIMARY KEY (i,j),

merkle CHAR(1) NOT NULL

    CHECK (merkle IN ('R', 'B')));

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.
Joe Celko

Author profile:

Joe Celko is one of the most widely read of all writers about SQL, and was the winner of the DBMS Magazine Reader's Choice Award four consecutive years. He is an independent consultant living in Austin, TX. He has taught SQL in the US, UK, the Nordic countries, South America and Africa.
He served 10 years on ANSI/ISO SQL Standards Committee and contributed to the SQL-89 and SQL-92 Standards.
He has written over 800 columns in the computer trade and academic press, mostly dealing with data and databases. He is the author of eight books on SQL for Morgan-Kaufmann, including the best selling SQL FOR SMARTIES.
Joe is a well-known figure on Newsgroups and Forums, and he is famous for his his dry wit. He is also interested in Science Fiction.

Search for other articles by Joe Celko

Rate this article:   Avg rating: from a total of 7 votes.


Poor

OK

Good

Great

Must read
Have Your Say
Do you have an opinion on this article? Then add your comment below:
You must be logged in to post to this forum

Click here to log in.


Subject: The Game of Life in SQL.
Posted by: Phil Factor (view profile)
Posted on: Friday, June 6, 2014 at 2:04 AM
Message:
/*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.j-1
    
LEFT OUTER JOIN grid S ON merkle.i=S.i
    
AND merkle.j=S.j-1
    
LEFT OUTER JOIN grid SE ON merkle.i=SE.i-1
    
AND merkle.j=SE.j-1
    
LEFT OUTER JOIN grid E ON merkle.i=E.i-1
    
AND merkle.j=E.j
    
LEFT OUTER JOIN grid NE ON merkle.i=NE.i-1
    
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=@ii-1
  
END  

Subject: The Real Game of Life
Posted by: Robert young (view profile)
Posted on: Friday, June 6, 2014 at 4:18 PM
Message: 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.


Subject: College Memories
Posted by: D (not signed in)
Posted on: Monday, June 9, 2014 at 8:34 AM
Message: 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!

Subject: please correct grammar
Posted by: ChipDale66 (not signed in)
Posted on: Monday, June 16, 2014 at 2:11 AM
Message: 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.<\quote> Ed: Somehow the word 'be' got deleted somewhere in the process. Now fixed

Subject: My solution to Assignment #2
Posted by: Jason Wolfkill (not signed in)
Posted on: Tuesday, June 17, 2014 at 2:21 PM
Message: 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!

Subject: SQL2008 + Visual
Posted by: puzsol (view profile)
Posted on: Thursday, July 17, 2014 at 8:17 AM
Message: 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

Subject: Geometric Solution
Posted by: Paul Brewer (view profile)
Posted on: Sunday, May 3, 2015 at 4:51 AM
Message: 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

Subject: Performance Testing
Posted by: Paul Brewer (view profile)
Posted on: Sunday, May 3, 2015 at 10:09 AM
Message: 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


Subject: Complete Solution
Posted by: Paul Brewer (view profile)
Posted on: Monday, May 4, 2015 at 4:41 AM
Message: 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

Subject: Complete Solution
Posted by: Paul Brewer (view profile)
Posted on: Monday, May 4, 2015 at 7:41 AM
Message: 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

Subject: Grid Referencing
Posted by: Paul Brewer (view profile)
Posted on: Monday, May 4, 2015 at 8:14 AM
Message: 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

Subject: Problem
Posted by: Paul Brewer (view profile)
Posted on: Tuesday, May 5, 2015 at 3:54 AM
Message: 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.

Subject: URL
Posted by: Paul Brewer (view profile)
Posted on: Tuesday, May 5, 2015 at 6:36 AM
Message: https://paulbrewer.wordpress.com/2015/05/03/sql-server-cellular-automation-using-geometry/

Subject: Apologies for all the spam ..
Posted by: Paul Brewer (view profile)
Posted on: Wednesday, May 6, 2015 at 11:46 AM
Message: 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!?





Subject: Set Based Solution
Posted by: Paul Brewer (view profile)
Posted on: Sunday, May 17, 2015 at 1:08 AM
Message: 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


Subject: Hekaton
Posted by: Paul Brewer (view profile)
Posted on: Tuesday, June 9, 2015 at 1:51 PM
Message: 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


 
Simple-Talk Database Delivery

DLM
Patterns & Practices Library

Visit our patterns and practices library to learn more about database lifecycle management.

Find out how to automate the process of building, testing and deploying your database changes to reduce risk and make rapid releases possible.

Get started

Phil Factor
Microsoft and Database Lifecycle Management (DLM): The DacPac

The Data-Tier Application Package (DacPac), together with the Data-Tier Application Framework (DacFx), provides an... Read more...

 View the blog

Top Rated

Working with SQL Server data in Power BI Desktop
 What's the best way of providing self-service business intelligence (BI) to data that is held in... Read more...

Microsoft and Database Lifecycle Management (DLM): The DacPac
 The Data-Tier Application Package (DacPac), together with the Data-Tier Application Framework (DacFx),... Read more...

A Start with Automating Database Configuration Management
 For a number of reasons, it pays to have the up-to-date source of all the databases and servers that... Read more...

Archiving Hierarchical, Deleted Transactions Using XML
 When you delete a business transaction from the database, there are times when you might want to keep a... Read more...

Rollback and Recovery Troubleshooting; Challenges and Strategies
 What happens if your database deployment goes awry? Do you restore from a backup or snapshot and lose... Read more...

Most Viewed

Beginning SQL Server 2005 Reporting Services Part 1
 Steve Joubert begins an in-depth tour of SQL Server 2005 Reporting Services with a step-by-step guide... Read more...

Ten Common Database Design Mistakes
 If database design is done right, then the development, deployment and subsequent performance in... Read more...

Temporary Tables in SQL Server
 Temporary tables are used by every DB developer, but they're not likely to be too adventurous with... Read more...

SQL Server Index Basics
 Given the fundamental importance of indexes in databases, it always comes as a surprise how often the... Read more...

Concatenating Row Values in Transact-SQL
 It is an interesting problem in Transact SQL, for which there are a number of solutions and... Read more...

Why Join

Over 400,000 Microsoft professionals subscribe to the Simple-Talk technical journal. Join today, it's fast, simple, free and secure.