-
Notifications
You must be signed in to change notification settings - Fork 0
/
sql:game-of-life.xhtml
165 lines (156 loc) · 5.27 KB
/
sql:game-of-life.xhtml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
<?xml version="1.0" encoding="utf-8" ?>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>SQL: Game of Life</title>
<meta name="author" content="Magnus Achim Deininger" />
<meta name="description" content="π-Day Special: an even more esoteric version of yesterday's Game of Life." />
<meta name="date" content="2013-03-14T22:19:00Z" />
<meta name="mtime" content="2013-03-14T22:19:00Z" />
<meta name="category" content="Articles" />
<meta name="category" content="SQL" />
<meta name="unix:name" content="sql:game-of-life" />
</head>
<body>
<h1>EVERYTHING is a Database Problem</h1>
<p>Right, so it's π-Day (the lame one, anyway), we just had πzza and are watching Harry πtter and the Philosopher's Stone. Everything gets better with large quantities of π so the obvious thing to do is, of course, to follow up on <a href="/xslt:game-of-life">yesterday's XSLT Game of Life implementation</a>.</p>
<p>As mentioned yesterday, the XSLT version is extremely slow. It could probably be sped up a bit. Maybe by including dead cells explicitly and working with standard XPath functions instead of looking up attributes. Maybe some other way.</p>
<p>But the far geekier thing to do is, of course, to write another version in a real language: SQL. <em>Cue mad laughter.</em></p>
<h1>Implementation</h1>
<p>I've actually gone through several implementations to come up with <a href="src/life.sql">a fairly fast version</a>:</p>
<pre><code><![CDATA[create table life
(
id integer not null,
x integer not null,
y integer not null,
state integer null,
primary key (id, x, y)
);
create table neighbourspec
(
id integer not null,
x integer not null,
y integer not null,
primary key (id, x, y)
);
insert into neighbourspec
(id, x, y)
values
(1, -1, -1),
(1, -1, 0),
(1, -1, 1),
(1, 0, -1),
(1, 0, 1),
(1, 1, -1),
(1, 1, 0),
(1, 1, 1);
create view vexpands as
select
life.id,
null as nid,
life.x,
life.y,
life.state
from life
union select
life.id,
neighbourspec.id as nid,
life.x + neighbourspec.x as x,
life.y + neighbourspec.y as y,
0 as state
from life, neighbourspec;
create view vexpand as
select
life.id,
life.x,
life.y,
max(life.state) as state
from vexpands as life
group by life.id, life.x, life.y;
create view vscore as
select
x1.id,
x1.x,
x1.y,
x1.state > 0 as alive,
sum(x2.state) as score
from vexpand as x1, vexpand as x2, neighbourspec
where x1.id = x2.id
and x2.x = x1.x + neighbourspec.x
and x2.y = x1.y + neighbourspec.y
group by x1.id, x1.x, x1.y, x1.state;
create view vlifenext as
select
vscore.id,
x,
y,
score = 3 or (score = 2 and alive) as state
from vscore;
]]></code></pre>
<p>The biggest surprise here was that things got significantly faster once I introduced the dummy data table <em>neighbourspec</em>. The basic workings of this bit of SQL should be obvious: insert board definition into the <em>life</em> table and then the <em>vlifenext</em> view contains the next generation.</p>
<p>To update the table, use a simple <em>insert or replace into</em> - deleting anything but living cells kinda speeds things up as well. Note that the <em>state</em> in that last view there might need a cast, depending on your SQL implementation. In SQLite the following materialised view works rather swell to automate updates to the <em>life</em> table:</p>
<pre><code><![CDATA[create view vprogress as
select 1 as id;
create trigger insertProgress instead of insert on vprogress
for each row
begin
delete from life where not state > 0;
insert or replace into life
(id, x, y, state)
select
id, x, y, state
from vlifenext;
end;
]]></code></pre>
<p>To use that view, just insert anything and it'll advance the <em>life</em> table one generation. Now, to display the board, we can reuse the XSLT to generate SVGs from last time. To export the XML we need for that, we use this view:</p>
<pre><code><![CDATA[create view vxmlfragment as
select
id,
'<bit x="' || x || '" y="' || y || '"/>' as fragment
from life
where state = 1;
]]></code></pre>
<p>... and this makefile snippet:</p>
<pre><code><![CDATA[game-of-life.xml: life.sqlite3
echo '<?xml version="1.0"?><game-of-life xmlns="http://ef.gy/2013/0p">' > $@
echo "select fragment from vxmlfragment where id = 1;" | $(SQLITE3) $< >> $@
echo '</game-of-life>' >> $@
]]></code></pre>
<p>That assumed that the database is going to be an sqlite3 database, the <em>SQLITE3</em> variable points to the sqlite3 CLI programme and you'd want the output to be called <em>game-of-life.xml</em>.</p>
<h1>Sample Data</h1>
<p>The database itself is still somewhat boring, so here's my favourite infinitely growing pattern:</p>
<pre><code><![CDATA[insert into life
(id, x, y, state)
values
(1, 0, 0, 1),
(1, 1, 0, 1),
(1, 2, 0, 1),
(1, 3, 0, 1),
(1, 4, 0, 1),
(1, 5, 0, 1),
(1, 6, 0, 1),
(1, 7, 0, 1),
(1, 9, 0, 1),
(1, 10, 0, 1),
(1, 11, 0, 1),
(1, 12, 0, 1),
(1, 13, 0, 1),
(1, 17, 0, 1),
(1, 18, 0, 1),
(1, 19, 0, 1),
(1, 26, 0, 1),
(1, 27, 0, 1),
(1, 28, 0, 1),
(1, 29, 0, 1),
(1, 30, 0, 1),
(1, 31, 0, 1),
(1, 32, 0, 1),
(1, 34, 0, 1),
(1, 35, 0, 1),
(1, 36, 0, 1),
(1, 37, 0, 1),
(1, 38, 0, 1)
;
]]></code></pre>
<p>Right, enjoy. Also, Snape is bleeding badass. But you knew that already.</p>
</body>
</html>