Discussion thread for Game of Life.
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.
Hey @misho88, that’s a pretty elegant solution! Never thought of it as a convolution, but your code has a few bugs
- 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] ].
- You forgot to account for the periodic boundary condition by passing
- 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.
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.
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…