EXPLAIN EXTENDED

How to create fast database queries

Happy New Year: Conway’s Game of Life in SQL

with one comment

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.

divination

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.

Happy New Year!

Previous New Year posts:

Written by Quassnoi

December 31st, 2015 at 11:00 pm

One Response to 'Happy New Year: Conway’s Game of Life in SQL'

Subscribe to comments with RSS

  1. Hats off to you!

    S N G

    3 Mar 16 at 19:13

Leave a Reply