Game of Life

Problem discussion
#1

Discussion thread for Game of Life.

#2

Counting neighbors is basically a convolution problem, which makes this kind of trivial:

from scipy.signal import convolve2d
def game_of_life(board, steps):
    ones = [ [1,1,1],[1,1,1],[1,1,1] ]
    for _ in range(steps):
        board = convolve2d(board, ones, 'same')
        board = ((3 <= board) & (board <= 4))
    return board.astype(int)

I figured this might be interesting for people given the somewhat high difficulty and time-commitment estimates.

1 Like
#3

Hey @misho88, that’s a pretty elegant solution! Never thought of it as a convolution, but your code has a few bugs :slight_smile:

  1. The kernel should count the number of neighbors but your kernel counts the current cell as a neighbor too. It should be ones = [ [1,1,1],[1,0,1],[1,1,1] ].
  2. You forgot to account for the periodic boundary condition by passing boundary='wrap' to convolve2d.
  3. Your code assumes all cells with 3 or 4 neighbors will survive, but it’s a bit more complicated: alive cells with 2-3 neighbors survive, and dead cells with 3 neighbors come to life.

Fixing those your code becomes

import numpy as np
from scipy.signal import convolve2d

def game_of_life(board, steps):
    board = np.array(board)  # Convert to numpy array so we can nicely use convolve2d
    
    # Convolutional kernel that counts neighbors.
    kernel = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
    
    for _ in range(steps):
        neighbors = convolve2d(board, kernel, mode='same', boundary='wrap')
        board = (((board == 1) & ((neighbors == 2) | (neighbors == 3))) | ((board == 0) & (neighbors == 3)))
    
    return board.astype(int).tolist()  # Convert numpy array back to Python list.

which is more efficient than a naive solution, especially in Python. It can probably be made even faster if you use FFTs to perform the convolution!

PS: The difficulty and time-commitment estimates are kind of based on the naive solution which is why they’re a little high.

#4

Hi @alir,

Thanks for this! Those are fair points. I should have read the description more carefully (my general strategy with these has been to skim the descriptions and fix my solutions when the validator tells me I’m wrong, which is probably not the best approach given that you straight up say not to expect everything to be perfect this early on on the main page).

It can probably be made even faster if you use FFTs to perform the convolution!

I’m not sure this is true. It should certainly hold for large stencils, but with a 3x3 one, the convolution takes 9NM operations for an N-by-M grid (that is, it’s basically linear in performance). Just the forward FFT of the grid would be O(NM log NM). I think the former is also more cache-efficient as long as the stencil stays small since the progression through memory is more sequential. Might be worth a try at some point, though, as an exercise. I can’t immediately work out how the different kinds of convolutions map to FFT operations and it’s kinda bugging me now.

#5

Oh haha yeah I like to submit quick and dirty solutions then fix them later too. I just wanted to see how much faster your code was when I realized it didn’t pass the tests so I tried to fix it.

You were probably correct about ones = [ [1,1,1],[1,1,1],[1,1,1] ] because then you just shift the number of neighbors to check for up by 1, so your bounds of (3 <= board) & (board <= 4) were correct for your stencil (but might still have to consider alive and dead cells separately).

And yeah you’re right about the FFT only helping on large stencils (like a stencil the size of the grid). I guess you’d need to roughly have log NM < S where S is the size of the stencil before seeing any benefits. Maybe 3x3 (S = 9) is too small but seems like FFT would be faster even for moderately sized stencils, but maybe things like caching and FFT plan creation suck up a lot of time by comparison…

#6

The convolution idea is very neat. I went a step further in node.js using seperable convolutions:

1D convolution of [1,1,1] in columns and in rows, to an intermediate board b2 (just lots of adding as only unit multipliers, with boundary checks for the edges).
Made assignment back to the original board on the 2nd inner loop (to avoid looping it all again) with a logical check of whether the cell should live or die, taking into account the +1 that gets added to the sum if it is already alive.

// convolute rows
for (let i = 0; i < rows; i++) {
    let i_1 = i == 0 ? rows-1 : i-1; // cell above, with wrapping
    let i1 = i == rows-1 ? 0 : i+1; // cell below, wrapping
    for (let j = 0; j < cols; j++) {
        b2[i][j] = board[i_1][j] + board[i][j] + board[i1][j];
    }
}

// convolute cols
for (let j = 0; j < cols; j++) {
    let j_1 = j == 0 ? cols-1 : j-1; //cell left, with wrapping
    let j1 = j == cols-1 ? 0 : j+1; // cell right, with wrapping
    for (let i = 0; i < rows; i++) {
        let count = b2[i][j_1] + b2[i][j] + b2[i][j1]; // includes +1 if already live
        // does the cell live or die?!!!
        board[i][j] = (count==3) || (count==4&&board[i][j]==1) ? 1 : 0;
    }
}