PostgreSQL Advent Calendar 2012 12/14 です。
ライフゲームとは「生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲーム」のことです。
碁盤目状に配置されたセルが、隣接するセルとの関係により、誕生・生存・死滅していく様子をシミュレーションします。
ルールは下記参考
ライフゲーム - Wikipedia
このライフゲームをSQLを使って実装してみます。
データ構造
セルの集合を下記のように表現します。
・１つのセルにつき、１行のレコード
・セルは３つの属性（列）を持つ
integer x：碁盤の左端から右に何個目か
integer y：碁盤の上端から下に何個目か
integer alive：生存状態（生きているセルなら1、死んでいるセルなら0）
データはこれだけです。
初期化
碁盤のサイズ、生存しているセルの割合、を決めてランダムに生成
CREATE TABLE cells AS SELECT x::integer, y::integer ,CASE WHEN random() < 0.3 THEN 1 -- 3割のセルが生存 ELSE 0 END::integer AS alive FROM generate_series(1,5) t1(x) -- 横のサイズが5 ,generate_series(1,5) t2(y) -- 縦のサイズが5 ; /* SELECT * FROM cells; x | y | alive ---+---+------- 1 | 1 | 1 1 | 2 | 0 1 | 3 | 0 1 | 4 | 0 1 | 5 | 0 2 | 1 | 0 2 | 2 | 0 2 | 3 | 1 2 | 4 | 1 2 | 5 | 0 3 | 1 | 1 3 | 2 | 1 3 | 3 | 1 3 | 4 | 1 3 | 5 | 0 4 | 1 | 0 4 | 2 | 0 4 | 3 | 0 4 | 4 | 0 4 | 5 | 0 5 | 1 | 0 5 | 2 | 0 5 | 3 | 0 5 | 4 | 1 5 | 5 | 0 (25 rows) */
描画
初期化したセルから碁盤を描画してみます。
aliveの値をテキストに集約して0,1の文字列で表現しています。
SELECT string_agg(alive_y, E'¥n' ORDER BY y) AS board
FROM(
SELECT
y
,string_agg(alive::text, '' ORDER BY x) AS alive_y
FROM cells
GROUP BY y
)t
;
/*
board
-----------------------------------
10100¥n00100¥n01100¥n01101¥n00000
(1 row)
10100
00100
01100
01101
00000
*/
次世代の生成
まずはSQLを
SELECT
x, y
,(
SELECT
CASE WHEN c1.alive = 0 AND c2.alives = 3 THEN 1 -- 誕生
WHEN c1.alive = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
ELSE 0 -- 死滅
END
FROM(
SELECT sum(c2.alive) as alives
FROM cells c2
WHERE
NOT(c1.x = c2.x AND c1.y = c2.y) -- 自分自身を除く
AND
c1.x BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲
AND
c1.y BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
)c2
)::integer AS alive
FROM cells c1
;
/*
x | y | alive
---+---+-------
1 | 1 | 0
1 | 2 | 0
1 | 3 | 0
1 | 4 | 0
1 | 5 | 0
2 | 1 | 1
2 | 2 | 0
2 | 3 | 0
2 | 4 | 1
2 | 5 | 0
3 | 1 | 0
3 | 2 | 1
3 | 3 | 0
3 | 4 | 1
3 | 5 | 0
4 | 1 | 0
4 | 2 | 1
4 | 3 | 0
4 | 4 | 1
4 | 5 | 0
5 | 1 | 0
5 | 2 | 0
5 | 3 | 0
5 | 4 | 0
5 | 5 | 0
(25 rows)
01000
00110
00000
01110
00000
*/
ちょっと解説
次世代のaliveを生成しているサブクエリを具体的なケースに置き換えてみます。
x=2, y=3のセルは次世代で生存しているでしょうか？
サブクエリをc1.x=2, c1.y=3, c1.alive=1で置換したものが下記になります。
SELECT
CASE WHEN 1 = 0 AND c2.alives = 3 THEN 1 -- 誕生
WHEN 1 = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
ELSE 0 -- 死滅
END
FROM(
-- ここのサブクエリで周囲の生存セル数を計算
SELECT sum(c2.alive) as alives
FROM cells c2
WHERE
NOT(2 = c2.x AND 3 = c2.y) -- 自分自身を除く
AND
2 BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲
AND
3 BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
)c2
具体的なケースができたら、後は全てのセルに対して同様に処理してやればOKです。状態を保存する場合はUPDATEするなり、CREATE TABLEするなりしてやりましょう。
まとめ
ライフゲーム？それ、SQLでもできるよ。
Advent Calendar
明日はsakamotomsさんです。
おまけ1
任意の碁盤の状態からcellsを初期化したい場合
CREATE OR REPLACE FUNCTION board_to_cells(board text)
RETURNS TABLE(x integer, y integer, alive integer)
AS $$
SELECT
row_number() OVER(PARTITION BY y)::integer as x
,y::integer
,alive::integer
FROM(
SELECT
row_number() OVER() AS y
,regexp_split_to_table(alive_y, '') AS alive
FROM(
SELECT
regexp_split_to_table($1, '\n') AS alive_y
)t
)t
$$
LANGUAGE SQL;
/*
SELECT * FROM board_to_cells(E'010\n100\n100');
*/
おまけ2
パフォーマンス実験
手元の環境にて、初期状態が100×100, 生存率3割で試したところ、次世代の計算にかかる時間が20秒強ほど。 もっと高速な実装を考えてみるのも面白いかも。
