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. :-)

Advertisements

2 Responses to “Game of Life in (one line of) k”

  1. Julian Yip Says:

    This is fun. For the wrap-around version, I think there might be a typo. Here is the fixed version:

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

    Cheers,

    Julian

    • thesweeheng Says:

      Fun indeed! And many thanks for identifying my typo (missing ‘a:’ between ‘=’ and ‘2’).

      Originally it was life:{0<x+0 1@4-2{+x-2{|1_0+’:x,1#x}/x}/x} but I wanted to make it consistent with the earlier code by replacing ‘0<x+0 1@4-‘ with ‘3=a-x*4=a:’. In the process of cut-and-pasting, I omitted the ‘a:’ :-P


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: