Game of Life in (one line of) q

Recently on the KDB+ Personal Developers mailing list, there was a post of an YouTube video showing how Conway’s Game of Life can be implemented in one line of APL. That post generated some interest and gave rise to several one-liners in q:

life:{any(1b;x)&'3 4=\:sum sum f(f:rotate'\:[1 0 -1])x} / by Aaron Davies
life:{any(1;x)&3 4=\:2 sum/2(1 0 -1 rotate'\:)/x}       / by Attila Vrabecz
life:{(3=a)|x&4=a:2 sum/2 rotate'\:[1 0 -1]/x}          / by Attila Vrabecz
life:{3=a-x*4=a:2 sum/2(1 0 -1 rotate'\:)/x}            / by Attila Vrabecz
life:{0<x+0 1@4-2 sum/2(1 0 -1 rotate'\:)/x}            / by Swee Heng (me!)

They pretty much implement the algorithm shown in the YouTube video. The steps are as follow:

  1. Take the input grid X and generate 3 new grids: the 1st is X with each row rotated left by one position; the 2nd is X itself; and the 3rd is X with each row rotated right by one position. We illustrate the transformation of the grid positions using ASCII art
                     +-------+
                     | 12340 |
                     | 67895 |
                     | BCDEA |
      +-------+      +-------+
      | 01234 |      | 01234 |
      | 56789 | ---> | 56789 |
      | ABCDE |      | ABCDE |
      +-------+      +-------+
                     | 40123 |
                     | 95678 |
                     | EABCD |
                     +-------+
  2. For each of the 3 resulting grids, perform step 1 again but this time rotate the columns (instead of rows) up and down. In ASCII art:
                     +-------+      +-------+-------+-------+
                     | 12340 |      | 67895 | 12340 | BCDEA |
                     | 67895 | ---> | BCDEA | 67895 | 12340 |
                     | BCDEA |      | 12340 | BCDEA | 67895 |
      +-------+      +-------+      +-------+-------+-------+
      | 01234 |      | 01234 |      | 56789 | 01234 | ABCDE |
      | 56789 | ---> | 56789 | ---> | ABCDE | 56789 | 01234 |
      | ABCDE |      | ABCDE |      | 01234 | ABCDE | 56789 |
      +-------+      +-------+      +-------+-------+-------+
                     | 40123 |      | 95678 | 40123 | EABCD |
                     | 95678 | ---> | EABCD | 95678 | 40123 |
                     | EABCD |      | 40123 | EABCD | 95678 |
                     +-------+      +-------+-------+-------+
  3. Sum up all 9 grids. Each cells of the resulting grid contains the number of occupied cells in its immediate neighbourhood (including itself).

In Aaron’s code, Step 1 is implemented by “f:rotate’\:[1 0 -1]”, Step 2 is performed by the second call to “f” and Step 3 is done by the double-call to “sum”. Since “f” and “sum” are called twice iteratively, Attila rewrote them as “2 sum/2(1 0 -1 rotate’\:)/x”. He also reduced the test of survivorship (occupied cells with 2 or 3 neighbours) and birth (empty cells with 3 neighbours) to a single expression “3=a-x*4=a”. As for me, I found an equivalent expression (i.e. “0<x+0 1@4-“) for the test of survivorship and birth.

The above algorithm is not so efficient as it creates additional grids and adds them. Chris Burke provided an alternative algorithm using table lookup. While it is not a one-liner, it is much faster. Here it is verbatim:

t:0b vs ' til "i"$2 xexp 9
ctr:t[;27]
cnt:sum each t
trans:(cnt=3) or (ctr=1) and cnt=4
lifeinit:{
 r:count x;c:count first x;
 index::raze each raze 2 (1 0 -1 rotate'\:)/ (r,c) # til r*c;
 raze x}
life:{trans 2 sv x index}
liferun:{(life\) lifeinit x}

The insight here is that a cell and its 8 neighbours can be treated as a “neighbourhood array” of 9 bits. E.g. cell 7 in the ASCII art has the corresponding neighbourhood array (1, 2, 3, 6, 7, 8, B, C, D). Such 9-bits array corresponds (using “2 sv”) to a number from 0 to 511 inclusive. By pre-computing “trans” (the test of survivorship and birth) and “index” (the neighourhood array of each cell), the “life” step becomes a quick table lookup.

Advertisements

3 Responses to “Game of Life in (one line of) q”

  1. Andras Dotsch Says:

    Nice stuff! This is mine one below. The same size as yours, but maybe a bit more obvious:

    life:{3=a-x*4=a:2(sum -1 0 1 rotate\:,’/)/x}

    The trick is that I flip (,’/) twice.

  2. KDB+, Elm and web sockets | Formalized Mathematics Says:

    […] a bonus: a one-line implementation of Conway’s Game of Life in […]

  3. kdb programming challenge - Minesweeper - AquaQ Analytics Says:

    […] order to get around this, we can use the Game of Life technique shown in this blog. This technique is pretty fast of the to the neighboring cells. One example is as […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: