Hey there! I am back this week with another Python challenge. This was actually a question I got on an interview exam. Program Conway’s Game of Life in Python trying to avoid Python loops as much as possible.
The Problem
The Game of Life is a cellular automaton created by John Horton Conway in 1970. In this game, we have a regular rectangular grid where each square is a cell that can either be born, remain alive, die or remain dead depending on the states of the cells in its neighbourhood.
The rules to implement are the following:
- Any live cell with less than two neighbours dies. Simulating underpopulation.
- Any live with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies. Simulating overpopulation.
- Any dead cell with exactly three live neighbours becomes alive. Simulating reproduction.
So now, the idea is to create a piece of code, a function, that takes a matrix of the game of life with 1s and 0s and returns the matrix evolved to the next step. So, for instance, we could have the following
# Performing 5 steps of Game of Life with input matrix:
# [[0 0 0 0 0 0]
# [0 1 1 1 0 0]
# [0 0 0 1 0 0]
# [0 1 1 1 0 0]
# [0 0 0 0 0 0]]
# After step 1
# [[0 0 1 0 0 0]
# [0 0 1 1 0 0]
# [0 0 0 0 1 0]
# [0 0 1 1 0 0]
# [0 0 1 0 0 0]]
# After step 2
# [[0 0 1 1 0 0]
# [0 0 1 1 0 0]
# [0 0 0 0 1 0]
# [0 0 1 1 0 0]
# [0 0 1 1 0 0]]
Remember the bonus points: Avoid loops as much as you can!
As a bonus, you can also add some visualization to the example and make something like this!
My Solution
For the elements on the inside of the square, it is pretty easy to access the 3×3 submatrix that we will need. If the element has indexes [i,j], then the slice of the submatrix to get is [i-1:i+2,j-1,j+2]. But what happens in the case of edge cells?
There is an easy solution to that. We can pad the initial matrix, let’s say of size m x n, to have a size m+2 x n+2 with extra 0s on the border. Then, we will be able to access all the elements in the same way, and the outer padded border will not affect our calculations because they are all 0s!
This can be implemented at the beginning of our function with the following
def GoLStep(GoLArr):
# We start by creating the extended matrix with outer zero rows and columns
n, m = np.shape(GoLArr)
GoLArr = np.vstack((np.zeros(m, dtype=int), GoLArr, np.zeros(m, dtype=int)))
GoLArr = np.hstack(((np.zeros((n+2,1), dtype=int)), GoLArr, (np.zeros((n+2,1), dtype=int))))
Now, we have to get the number neighbours of each cell. Since we know how to access the matrix alread, it should be pretty easy. For each element, we calculate the following
np.sum(GoLArr[row-1:row+2, column-1:column+2]) - GoLArr[row,column]
Ok, but we have to do this for all the elements and save it. How to do that avoiding a loop? Luckily, there is a very convenient function in numpy called vectorize.
This function takes a function as an input and returns another function. I know, very meta. The good thing about this newly returned function is that it is vectorized for the variables that you select. Therefore, you can pass a numpy array and it will run the function on each of its elements. Exactly what we want… but not quite.
We actually want to iterate over the indexes of the original Game of Life Array (GoLArr), not through the elements of the GoLArr itself. So, we create an indices array, which will be the vectorized variable.
This is the result of putting it all together
def cellNeigh(element, GoLArr, m):
# This changes from 1, 2, 3, 4, ... indexing to (i,j) indexing
row, column = element // m, element % m
return np.sum(GoLArr[row:row+3, column:column+3]) - GoLArr[row+1,column+1]
def GoLStep(GoLArr):
# We start by creating the extended matrix with outer zero rows and columns
n, m = np.shape(GoLArr)
GoLArr = np.vstack((np.zeros(m, dtype=int), GoLArr, np.zeros(m, dtype=int)))
GoLArr = np.hstack(((np.zeros((n+2,1), dtype=int)), GoLArr, (np.zeros((n+2,1), dtype=int))))
indices = np.arange(n*m).reshape(n,m)
# We call the cellNeigh function FOR EACH element in the indices array. We use
# this elements to obtain the submatrices of the GoLArr. Finally, we obtain
# the number of neighbors for each cell and store it in a (n,m) matrix
neigh = np.vectorize(cellNeigh, excluded=(1,2))(indices, GoLArr, m)
Here, we have obtained the neigh matrix that stores the number of neighbours that each cell has. We are ready to add the last final line that returns the GoLArr on the next step.
return np.where((neigh == 3) | (GoLArr[1:n+1, 1:m+1] == 1) & (neigh == 2), 1, 0)
Yes, this takes all rules exposed before into a single np.where statement and returns the correct GoLArr on the following step!
Here you can see everything together.
def cellNeigh(element, GoLArr, m):
# This changes from 1, 2, 3, 4, ... indexing to (i,j) indexing
row, column = element // m, element % m
return np.sum(GoLArr[row:row+3, column:column+3]) - GoLArr[row+1,column+1]
def GoLStep(GoLArr):
# We start by creating the extended matrix with outer zero rows and columns
n, m = np.shape(GoLArr)
GoLArr = np.vstack((np.zeros(m, dtype=int), GoLArr, np.zeros(m, dtype=int)))
GoLArr = np.hstack(((np.zeros((n+2,1), dtype=int)), GoLArr, (np.zeros((n+2,1), dtype=int))))
indices = np.arange(n*m).reshape(n,m)
# We call the cellNeigh function FOR EACH element in the indices array. We use
# this elements to obtain the submatrices of the GoLArr. Finally, we obtain
# the number of neighbors for each cell and store it in a (n,m) matrix
neigh = np.vectorize(cellNeigh, excluded=(1,2))(indices, GoLArr, m)
return np.where((neigh == 3) | (GoLArr[1:n+1, 1:m+1] == 1) & (neigh == 2), 1, 0)
def main():
arr = np.array(
[[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0]]
)
print('Performing 5 steps of Game of Life with input matrix:')
print(arr)
for i in range(5):
arr = GoLStep(arr)
print(f'\nAfter step {i+1}')
print(arr)
if __name__ == '__main__':
main()
If you liked this blog and you would like to look at other blogs, I have interesting stuff in SQL and Python!
