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. :-)
12 February, 2009 at 2:09 pm
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
13 February, 2009 at 9:52 am
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