John Conways’s “Game of Life”

The Game of Life is a well-known cellular automaton in which each generation of a population 'evolves' from the previous one according to a set of predefined rules.

Here's a one-line APL function takes a boolean matrix as argument and returns a boolean matrix with the new generation.

  ∇ nextGeneration←Life currentGeneration
[1] ⍝⍝ Take a matrix of Booleans and returns one
[2]  nextGeneration←↑↑1 currentGeneration∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
  ∇

How the APL code works

If you're completely new to APL, this explanation is probably not the place to start! However, you should be able to get some idea of what's happening even if the details are not yet clear. Just bear in mind that APL evaluates expressions from right to left unless you use parentheses.

To compute a new generation in the Game of Life we first need to find out how many neighbours each live cell has. To keep things simple let's consider the following 5x5 grid:

      currentGeneration←5 5⍴0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0
      currentGeneration
0 0 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0

If we rotate each row of the grid one place left by using APL's Rotate function ⌽, each element is replaced by its right-hand neighbour. In other words, the new grid will have a 1 for all cells whose right-hand neighbour was 1:

      1⌽currentGeneration
0 0 0 0 0
0 1 1 0 0
0 0 1 1 0
0 0 1 0 0
0 0 0 0 0

Similarly we can rotate right to find the left-hand neighbour by using ¯1⌽currentGeneration. By using APL's Outer Product operator ∘. together with the Rotate function we can get a set of three grids containing the left-hand neighbour, the original grid, and the right-hand neighbour:

      ¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
 0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
 0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
 0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

Now we can use a similar trick but rotate up and down by using APL's First Axis Rotate function ⊖. Used with an Outer Product this gives us a series of 9 grids:

     ¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
 0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
 0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
 0 0 0 1 0   0 0 1 0 0   0 1 0 0 0

 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
 0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
 0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
 0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

 0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
 0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
 0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

The grid in the centre is our original grid, and the others give the neighbours above, below, left, right and diagonally.

Now we can find out how many neighbours each cell in the original grid has by summing the corresponding elements in each of the 9 grids. For a live cell this will give us 1 more than the number of neighbours - e.g. a '4' in the result means a cell had three neighbours. For a dead cell the result is just the number of neighbours:

      +/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 1 2 2 1
 1 3 4 3 1
 1 4 5 4 1
 1 3 3 2 0
 0 1 1 1 0

For a cell to exist in the next generation, one of two rules must be met:

• Any live cell with two neighbours lives, unchanged, to the next generation
• Any cell, live or dead, with exactly three neighbours is live in the next generation

This means that all cells which might be live in the next generation will have a sum of 3 (from the first rule) or 3 or 4 (from the second rule).

So we're interested in cells with a sum of 3 or 4, which we can find as follows:

     3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0   0 0 0 0 0
 0 1 0 1 0   0 0 1 0 0
 0 0 0 0 0   0 1 0 1 0
 0 1 1 0 0   0 0 0 0 0
 0 0 0 0 0   0 0 0 0 0

The next step is best understood by first considering the two rules separately

(a) A cell will live in the next generation if it's live in the current generation AND has two neighbours. Here we're using APL's And function, ^

    (⊂currentGeneration)^3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0
 0 0 0 1 0
 0 0 0 0 0
 0 0 1 0 0
 0 0 0 0 0

(b) A cell will be live in the next generation if it has three neigbours:

      4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0
 0 0 1 0 0
 0 1 0 1 0
 0 0 0 0 0
 0 0 0 0 0

We can write this slightly redundantly by AND-ing with 1 (meaning AND cell is alive or dead) for reasons which will become apparent shortly:

      1^4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0
 0 0 1 0 0
 0 1 0 1 0
 0 0 0 0 0
 0 0 0 0 0

So the next step is to say that a cell is live if either rule (a) OR rule (b) is met. We need to use APL's Or function, ∨. We could write this rather long-windedly as:

     (1^4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration)∨(⊂currentGeneration)^3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 0 0 0 0 0
 0 0 1 1 0
 0 1 0 1 0
 0 0 1 0 0
 0 0 0 0 0

But we can take advantage of APL's Inner Product operator to do the AND operations of each rule and then OR the result - the ∨.^ in the following:

     1 currentGeneration∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
  0 0 0 0 0
  0 1 1 1 0
  0 1 0 0 0
  0 1 1 0 0
  0 0 0 0 0

The final expression ends with a bit of housekeeping using ↑↑ to turn the result back into a simple array (it's currently nested).

External links

• Conways_Game_of_Life

• Conway’s Game of Life in one line of APL

• Time(r) for the Game of Life

CategoryShowcases