Game of Life in (one line of) k

In my previous post I mentioned several q implementation of Conway’s Game of Life. There are also some k implementations at nsl.com (see this page). The shortest one I know of comes from Arthur Whitney:

life:{3=a-x*4=a:2{+(0+':x)+1_x,0}/x}

The key insight here is that for each cell in the grid we can compute the number of occupied cells in its neighbourhood by (i.) summing its column-wise neighbours; and then (ii.) summing the row-wise neighbours of the first sum. To visualize the components of the sum in ASCII art:

  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |       |   |   |   |   |       |   |   |   |   |
  | 0 | 1 | 2 | 3 |       | 0 | 1 | 2 | 3 |       | 01|012|123|23 |
  |   |   |   |   |       | 4 | 5 | 6 | 7 |       | 45|456|567|67 |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |  col  | 0 | 1 | 2 | 3 |  row  | 01|012|123|23 |
  | 4 | 5 | 6 | 7 |  sum  | 4 | 5 | 6 | 7 |  sum  | 45|456|567|67 |
  |   |   |   |   | ----> | 8 | 9 | A | B | ----> | 89|89A|9AB|AB |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+
  |   |   |   |   |       | 4 | 5 | 6 | 7 |       | 45|456|567|67 |
  | 8 | 9 | A | B |       | 8 | 9 | A | B |       | 89|89A|9AB|AB |
  |   |   |   |   |       |   |   |   |   |       |   |   |   |   |
  +---+---+---+---+       +---+---+---+---+       +---+---+---+---+

The code {+(0+’:x)+1_x,0} simply arranges the rows and computes the column-wise sums.

      x                (0+':x)            1_x,0
  +-------+       +---------------+     +-------+
  | 01234 |       | 01234         |     | 56789 |
  | 56789 | ----> | 56789 + 01234 |  +  | ABCDE |
  | ABCDE |       | ABCDE + 56789 |     | FGHIJ |
  | FGHIJ |       | FGHIJ + ABCDE |     |       |
  +-------+       +---------------+     +-------+

The flip (+) operation changes columns to rows so that the same {+(0+’:x)+1_x,0} code can be used to compute the row-wise sums. The 2nd flip restores the orientation of the grid.

The above Game of Life is not exactly the same as what I posted earlier since the boundary cells do not wrap around. To get a wrap-around version, we can use this one-liner:

life:{3=a-x*4=a:2{+x-2{|1_0+':x,1#x}/x}/x}

I will leave it to the reader to figure out how this works. :-)

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.