Happy New Year: Conway’s Game of Life in SQL
It's Yuletide again and today I'd like to tell about an old tradition in Russia. Its origins can be traced back to pre-Christian, pagan rites of the ancient Slavic tribes.
Each year on the Christmas eve, when it is freezing cold outside and the Grandfather Frost comes out to inspect his vast domain, young girls gather in an old, poorly lit bathhouse and try to look into the future.
There are many ways to do a Christmas divination: some prefer candle wax, some go with cats or mirrors, some use a good old deck of cards. But the old women can tell you of another way to look into the future. It requires skill and patience, but it is said an intrepid soul brave enough to look the eternity in the eye can unveil the mystery of the future and see the good and the bad that the next year will bring.
To do this, you need a large enough checkered board and a bag of dried beans, black and white. Carefully arranging the black beans into letters three squares wide and five squares tall, you write your question on the board. When ready, you exclaim the magic words: "RENDRAG! YAWNOC! NNAMEUN NOV!" and begin the magic rite.
Those of you who can spell backwards can scroll down now.
Those who are not familiar with Conway's Game of Life and don't believe in Christmas magic, can google for it (do it, if you never have, it's fun).
And I will go on and explain the rules to the rest of my readers who do believe in magic pagan rites.
First, you check how many black beans surround each tile on the board. If it is surrounded by exactly two black beans, it stays the same next turn, for the two is the number of the true love; if it is surrounded by exactly three, it gets the bean next turn, for the three is the number of new life; any other number means the tile is empty the next turn, for empty is the world devoid of life and love.
You use the white beans to mark the tiles which are to get or to lose the bean on the next turn, for white means change.
If you are close to the edge of the board and don't have adjacent tiles from either side, wrap around to another side, that is top to bottom, left to right or vice versa. This symbolizes the old belief that our world was bagel-shaped.
Singing an ancient song, you do the divination turn by turn, moving the beans around. With time, certain patterns emerge on the board. Some resemble a crane, some resemble a beehive, other just seems chaotic. When you do as many turns as there are days in the new year, you look at the patterns and interpret them.
Now, let's try to do this in SQL. We'll be using PostgreSQL 9.4 as it supports some very nice features.
Font
First things first, we have to make that 3x5 pixel font work. I've sketched the basic symbols, just enough for the divination to work, that is punctuation and capital letters from A to Z. I used a text editor to draw the glyphs, leaving a one-pixel space between them. However, it's not going to look good in a query. Fortunately, 3 times 5 is 15, so we can encode appearance of each of those symbols with a number from 0 to 2^15 - 1 = 32767. Let's do this:
WITH font (image) AS ( SELECT ' * * * * * ** * ** * * * * * * ** * * *** ** *** * * ** * * ** * ** *** *** * * * * * * * * * * *** * ** * ** ** *** * * * * * * * * * * *** * * * *** ** * * * * * * * * * * * ** * * * * * * * * * * * * * * * *** * * * * * * * * * * * * * * * * * * * * * * * *** * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * *** *** * * * * * * *** ** ** * * ** * * * *** *** ** * * * ** ** * *** * * ** * * * * * * * ** * * ** * * * * * * * * * * * *** ** * * * * * * * * * * * * * * * * * * * * * * * * * * *** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *** * * * * * * * ** * *** * * * * * *** *** ** * ** * * * ** * * ** * * ** * ** *** * ** * * * * * * *** * * * * * * ** * * ** * *** * * * * * * *** ' ) SELECT ARRAY( SELECT BIT_OR((SUBSTRING(line, num * 4 + dot + 1, 1) = '*')::INT::BIT(15) << ((n - 2) * 3 + dot)::INT)::INT FROM font CROSS JOIN LATERAL REGEXP_SPLIT_TO_TABLE(image::TEXT, E'\\n') WITH ORDINALITY l (line, n) CROSS JOIN GENERATE_SERIES(0, 58) num CROSS JOIN GENERATE_SERIES(0, 2) dot WHERE line > '' GROUP BY num ORDER BY num ) codes
codes |
---|
[0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351] |
The font is going to look mangled in the snippet above, so just click "view source" if you want to see the font in all its beauty.
The output of this query is an array which encodes 58 symbols, from space to Z.
Board
Let's simulate our divination board and start with writing the number "2016" on it. To do this, we should construct a series of five strings, each one containing the font pixels for every letter in the string, then join those strings together with a new line character. We will employ PostgreSQL's bit arithmetic capabilities to populate the dots:
WITH RECURSIVE i AS ( SELECT ARRAY[ 0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351 ] font, '2016'::TEXT message ), b (config) AS ( SELECT ARRAY_TO_STRING( ARRAY( SELECT row FROM i CROSS JOIN GENERATE_SERIES(0, 4) line CROSS JOIN LATERAL ( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE WHEN dot < 3 AND (font[ASCII(SUBSTRING(message, c + 1, 1)) - 31]::BIT(15) & (1::BIT(15) << (3 * line + dot)::INT))::INT::BOOLEAN THEN '*' ELSE ' ' END FROM GENERATE_SERIES(0, LENGTH(message) - 1) c CROSS JOIN GENERATE_SERIES(0, 3) dot ORDER BY c, dot ), '' ) ) q (row) ORDER BY line ), E'\n' ) ) SELECT * FROM b
config |
---|
* * * ** * * * * ** * * * * * ** * * * * * * *** * *** * |
Rules
Implementing the rules is pretty straightforward. We need to examine each square on the board and calculate the number of occupied squares surrounding this one. This requires a recursive query: on each "turn", the current board is passed in a field of a single-line query, then joined with the GENERATE_SERIES()
to expand it into a series of dots, and for each dot a LATERAL
query is applied, calculating the number of neighbors. The lateral query in its turn is also a cross-join of two GENERATE_SERIES(-1, 1)
which gives us 9 records in total. We need to make sure that we don't count the (0, 0) in: when calculating the number of neighbors, we are not interested in the square itself, just the surrounding tiles.
We also need a way to serialize the board into a single field (for the recursion) and access individual dots in this field. This could be done with HSTORE
or JSON
or a two-dimensional array, but the fastest way to do this seems to be using a bitmap: just a single BIT(600)
field with appropriate bits set. It's very easy to random access any single bit in this field using bit arithmetic, and PostgreSQL offers native aggregate functions on bitmaps to serialize it back for the recursion.
Bit field
To store the board in a bit field, we need to know the maximum size of the board in advance, and we also need to set the total size of the board beforehand (since our board is a torus, the patterns can wrap it around from either side, so the board size kinda matters). We'll just go with a 20 x 30 board, that would be enough.
To convert the string above into a bitmap, we need to split this string into individual lines and characters, get the number of each line and character and see if it's an asterisk or a space. Spaces would be filtered out. The rest would be just a series of X and Y. To place a bit on its place, which is Y * WIDTH + X, we need to take the bitmap consisting just of the rightmost bit (...00001, which is of course just the number one) and shift that bit to the left as far as we need. When we get a series of bits, each on its place, we need to OR them all together, so that the end result gets a 1 on each place where at least one 1 has already been. That's how we do it:
WITH RECURSIVE i AS ( SELECT ARRAY[ 0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351 ] font, '2016'::TEXT message ), b (config) AS ( SELECT ARRAY_TO_STRING( ARRAY( SELECT row FROM i CROSS JOIN GENERATE_SERIES(0, 4) line CROSS JOIN LATERAL ( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE WHEN dot < 3 AND (font[ASCII(SUBSTRING(message, c + 1, 1)) - 31]::BIT(15) & (1::BIT(15) << (3 * line + dot)::INT))::INT::BOOLEAN THEN '*' ELSE ' ' END FROM GENERATE_SERIES(0, LENGTH(message) - 1) c CROSS JOIN GENERATE_SERIES(0, 3) dot ORDER BY c, dot ), '' ) ) q (row) ORDER BY line ), E'\n' ) ), p AS ( SELECT x, y FROM b JOIN LATERAL REGEXP_SPLIT_TO_TABLE(config::TEXT, E'\\n') WITH ORDINALITY l (line, y) ON line > '' JOIN LATERAL REGEXP_SPLIT_TO_TABLE(line, '') WITH ORDINALITY s (sym, x) ON sym !~ E'\\s' ), s (field, height, width) AS ( SELECT field, height, width FROM ( SELECT 20 height, 30 width ) n CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT) field FROM p ) q ) SELECT * FROM s
field | height | width |
---|---|---|
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100111001001110000000000000001010010010100100000000000000000110010010101000000000000000000010011010101010000000000000001100010001000100000000000000000000000000000000 | 20 | 30 |
Note that we are using WITH ORDINALITY
along with REGEXP_SPLIT_TO_TABLE
. This clause makes the function not just expand the string into a recordset of chunks, but return the ordinal number of each chunk along with it. This is much more elegant and efficient than using GENERATE_SERIES
along with SUBSTRING
or arrays to get the individual pieces of a string and their numbers.
Least significant bits come last in the string representation of a bitmap, so you might want to scroll the result window above to the right, to see it's not just zeroes.
Let's convert our bitmap back to string representation to check if we got everything right. To do this we generate a series of records, one for each dot, using GENERATE_SERIES
, then return a space or an asterisk for each bit unset or set. Finally, we concatenate them first into arrays then to strings in the right order:
WITH RECURSIVE i AS ( SELECT ARRAY[ 0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351 ] font, '2016'::TEXT message ), b (config) AS ( SELECT ARRAY_TO_STRING( ARRAY( SELECT row FROM i CROSS JOIN GENERATE_SERIES(0, 4) line CROSS JOIN LATERAL ( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE WHEN dot < 3 AND (font[ASCII(SUBSTRING(message, c + 1, 1)) - 31]::BIT(15) & (1::BIT(15) << (3 * line + dot)::INT))::INT::BOOLEAN THEN '*' ELSE ' ' END FROM GENERATE_SERIES(0, LENGTH(message) - 1) c CROSS JOIN GENERATE_SERIES(0, 3) dot ORDER BY c, dot ), '' ) ) q (row) ORDER BY line ), E'\n' ) ), p AS ( SELECT x, y FROM b JOIN LATERAL REGEXP_SPLIT_TO_TABLE(config::TEXT, E'\\n') WITH ORDINALITY l (line, y) ON line > '' JOIN LATERAL REGEXP_SPLIT_TO_TABLE(line, '') WITH ORDINALITY s (sym, x) ON sym !~ E'\\s' ), s (field, height, width) AS ( SELECT field, height, width FROM ( SELECT 20 height, 30 width ) n CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT) field FROM p ) q ) SELECT ARRAY_TO_STRING( ARRAY( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE field & (1::BIT(600) << (y * width + x)::INT) WHEN 0::BIT(600) THEN ' ' ELSE '*' END FROM GENERATE_SERIES(0, width - 1) x ORDER BY x ), '' ) || '|' FROM GENERATE_SERIES(0, height - 1) y ), E'\n' ) image, field FROM s
image | field |
---|---|
| * * * ** | * * * * ** * | * * * * ** | * * * * * * | *** * *** * | | | | | | | | | | | | | | | |
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100111001001110000000000000001010010010100100000000000000000110010010101000000000000000000010011010101010000000000000001100010001000100000000000000000000000000000000 |
OK, seems we nailed it. Let's do the recursion.
Recursion
As I said above, we expand the bit field into a series of individual records, one for each bit, and call a lateral query for it, counting its neighbors. The only tricky thing here is handing that wrapping around. So if we have a bit on X, Y, with either X or Y being a zero, we need to wrap around to WIDTH - 1 or HEIGHT - 1 when looking for neighbors. Same way, if we have X and Y at HEIGHT - 1 or WIDTH - 1, the neighbors are at 0. This sounds like module arithmetic, which is what we are going to use here.
WITH RECURSIVE i AS ( SELECT ARRAY[ 0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351 ] font, '2016'::TEXT message ), b (config) AS ( SELECT ARRAY_TO_STRING( ARRAY( SELECT row FROM i CROSS JOIN GENERATE_SERIES(0, 4) line CROSS JOIN LATERAL ( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE WHEN dot < 3 AND (font[ASCII(SUBSTRING(message, c + 1, 1)) - 31]::BIT(15) & (1::BIT(15) << (3 * line + dot)::INT))::INT::BOOLEAN THEN '*' ELSE ' ' END FROM GENERATE_SERIES(0, LENGTH(message) - 1) c CROSS JOIN GENERATE_SERIES(0, 3) dot ORDER BY c, dot ), '' ) ) q (row) ORDER BY line ), E'\n' ) ), p AS ( SELECT x, y FROM b JOIN LATERAL REGEXP_SPLIT_TO_TABLE(config::TEXT, E'\\n') WITH ORDINALITY l (line, y) ON line > '' JOIN LATERAL REGEXP_SPLIT_TO_TABLE(line, '') WITH ORDINALITY s (sym, x) ON sym !~ E'\\s' ), s (field, step, height, width, cnt) AS ( SELECT field, step, height, width, 0::BIGINT cnt FROM ( SELECT 1 step, 20 height, 30 width ) n CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT) field FROM p ) q UNION ALL SELECT q.field, step + 1, height, width, q.cnt FROM s CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT), COUNT(*) cnt FROM GENERATE_SERIES(0, height - 1) y CROSS JOIN GENERATE_SERIES(0, width - 1) x CROSS JOIN LATERAL ( SELECT SUM(((field & (1::BIT(600) << (((y + height + yo) % height) * width + ((x + width + xo) % width))::INT)) <> 0::BIT(600))::INT) neighbors FROM GENERATE_SERIES(-1, 1) xo CROSS JOIN GENERATE_SERIES(-1, 1) yo WHERE (xo, yo) IS DISTINCT FROM (0, 0) ) q WHERE CASE WHEN neighbors = 2 AND (field & (1::BIT(600) << (y * width + x))) <> 0::BIT(600) THEN TRUE WHEN neighbors = 3 THEN TRUE END ) q (field, cnt) WHERE step = 1 ) SELECT step, ARRAY_TO_STRING( ARRAY( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE field & (1::BIT(600) << (y * width + x)::INT) WHEN 0::BIT(600) THEN ' ' ELSE '*' END FROM GENERATE_SERIES(0, width - 1) x ORDER BY x ), '' ) || '|' FROM GENERATE_SERIES(0, height - 1) y ), E'\n' ) image FROM s
step | image |
---|---|
1 | | * * * ** | * * * * ** * | * * * * ** | * * * * * * | *** * *** * | | | | | | | | | | | | | | | |
2 | | * * ** * | * * ***** * * | * * * **** | * * ** ** * | *** * *** * | * * | | | | | | | | | | | | | | |
We have it going! It's just one step, so that we can manually inspect it and see if it looks legit, but it seems it does. Let's look what the step 366 brings us:
WITH RECURSIVE i AS ( SELECT ARRAY[ 0, 8338, 45, 24445, 15518, 17057, 31630, 18, 8778, 10530, 2728, 1488, 5120, 448, 8192, 672, 11114, 29850, 29994, 14499, 18925, 14543, 10958, 9383, 10922, 14762, 1040, 5136, 1104, 3640, 1296, 8355, 25578, 23530, 15083, 10858, 15211, 29391, 4815, 27242, 23533, 9362, 11044, 23277, 29257, 23421, 23407, 11114, 4843, 27498, 23275, 14478, 9367, 31597, 11117, 24429, 23213, 9389, 29351 ] font, '2016'::TEXT message ), b (config) AS ( SELECT ARRAY_TO_STRING( ARRAY( SELECT row FROM i CROSS JOIN GENERATE_SERIES(0, 4) line CROSS JOIN LATERAL ( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE WHEN dot < 3 AND (font[ASCII(SUBSTRING(message, c + 1, 1)) - 31]::BIT(15) & (1::BIT(15) << (3 * line + dot)::INT))::INT::BOOLEAN THEN '*' ELSE ' ' END FROM GENERATE_SERIES(0, LENGTH(message) - 1) c CROSS JOIN GENERATE_SERIES(0, 3) dot ORDER BY c, dot ), '' ) ) q (row) ORDER BY line ), E'\n' ) ), p AS ( SELECT x, y FROM b JOIN LATERAL REGEXP_SPLIT_TO_TABLE(config::TEXT, E'\\n') WITH ORDINALITY l (line, y) ON line > '' JOIN LATERAL REGEXP_SPLIT_TO_TABLE(line, '') WITH ORDINALITY s (sym, x) ON sym !~ E'\\s' ), s (field, step, height, width, cnt) AS ( SELECT field, step, height, width, 0::BIGINT cnt FROM ( SELECT 1 step, 20 height, 30 width ) n CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT) field FROM p ) q UNION ALL SELECT q.field, step + 1, height, width, q.cnt FROM s CROSS JOIN LATERAL ( SELECT BIT_OR(1::BIT(600) << (y * width + x)::INT), COUNT(*) cnt FROM GENERATE_SERIES(0, height - 1) y CROSS JOIN GENERATE_SERIES(0, width - 1) x CROSS JOIN LATERAL ( SELECT SUM(((field & (1::BIT(600) << (((y + height + yo) % height) * width + ((x + width + xo) % width))::INT)) <> 0::BIT(600))::INT) neighbors FROM GENERATE_SERIES(-1, 1) xo CROSS JOIN GENERATE_SERIES(-1, 1) yo WHERE (xo, yo) IS DISTINCT FROM (0, 0) ) q WHERE CASE WHEN neighbors = 2 AND (field & (1::BIT(600) << (y * width + x))) <> 0::BIT(600) THEN TRUE WHEN neighbors = 3 THEN TRUE END ) q (field, cnt) WHERE step < 366 ) SELECT step, ARRAY_TO_STRING( ARRAY( SELECT ARRAY_TO_STRING( ARRAY( SELECT CASE field & (1::BIT(600) << (y * width + x)::INT) WHEN 0::BIT(600) THEN ' ' ELSE '*' END FROM GENERATE_SERIES(0, width - 1) x ORDER BY x ), '' ) || '|' FROM GENERATE_SERIES(0, height - 1) y ), E'\n' ) image FROM s WHERE step IN (1, 366)
step | image |
---|---|
1 | | * * * ** | * * * * ** * | * * * * ** | * * * * * * | *** * *** * | | | | | | | | | | | | | | | |
366 | | | | | ** | * * | * * | * | | | | | ** | * * | * | | | | | | |
Seems we got ourselves a Loaf and a Boat! Wonder what could that mean?
Let's try some other patterns. I won't repeat the SQL, just replace the text message above and adjust the height, the width and the BIT type size in queries i
and s
:
step | image |
---|---|
1 | | * * * * *** | * * * * * * | * * * * * ** | * * * * * * | *** * * *** | | | | | | | | | | | | | | | |
366 | * * | * ** | * * | ** * * | ** * | | ** ** | * * * * | ** ** | | * | * * | * * | * | * | * * | * * | * | ** | * * | |
"LOVE" would give us a Block (hmmm…), a Honey Farm (not too bad!), and a standalone Beehive next to a Pond. One might say those patterns are pretty… promising!
What shall we expect in our professional life then?
step | image |
---|---|
1 | | ** * * | * * * * | * * * * | * * * * | ** ** *** | | | | | | | | | | | | | | | |
366 | | | ** | ** | | | | | | | | | | | ** | ** | | | | | |
Two Blocks for "SQL"? Oh come on!
And finally,
step | image |
---|---|
1 | | * * * ** ** * * *** *** * * * * *** * ** * | * * * * * * * * * * * * * * * * * * * * * * * | *** *** ** ** * * * ** * * * ** *** ** * | * * * * * * * * * * *** * * * * * * | * * * * * * * * * *** * * * *** * * * * * | | | | | | | | | | | | | | | | | | | | | | | | | |
366 | * * | * | | ** | * * | * * | ** * | ** | ** | * * ** * | * * *** | * * * | * * ** * | ** * *** * | ** * * * * ** | * * ** * *| ** * * * *| * * * | * **** * | ** ** * | *** * **| **| * | ** ** | ** * ** | * ** * * | * ** ** * ** ** | * * * * ** | * ** * ** * | * * * | |
The "HAPPY NEW YEAR!" pattern does not stabilize!
This could only mean one thing: future is not known to us and it's up to us to make it what we want it to be.
Previous New Year posts:
Hats off to you!
S N G
3 Mar 16 at 19:13