Conway’s Game of Life – Unlimited Edition – In Python

What is this?

Conways’s Game Of Life is a Cellular Automation Method created by John Conway. This game was created with Biology in mind but has been applied in various fields such as Graphics, terrain generation,etc..

geeksforgeeks.org

How the game works

Because the Game of Life is built on a grid of nine squares, every cell has eight neighboring cells,as shown in the given figure. A given cell (i, j) in the simulation is accessed on a grid [i][j], where i and j are the row and column indices, respectively. The value of a given cell at a given instant of time depends on the state of its neighbors at the previous time step. Conway’s Game of Life has four rules.

1. If a cell is ON and has fewer than two neighbors that are ON, it turns OFF
2. If a cell is ON and has either two or three neighbors that are ON, it remains ON.
3. If a cell is ON and has more than three neighbors that are ON, it turns OFF.
4. If a cell is OFF and has exactly three neighbors that are ON, it turns ON.

The challenge

Given a 2D array and a number of generations, compute n timesteps of Conway’s Game of Life.

The rules of the game are:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.

Each cell’s neighborhood is the 8 cells immediately around it (i.e. Moore Neighborhood). The universe is infinite in both the x and y dimensions and all cells are initially dead – except for those specified in the arguments. The return value should be a 2d array cropped around all of the living cells. (If there are no living cells, then return [[]].)

For illustration purposes, 0 and 1 will be represented as ░░ and ▓▓ blocks respectively (PHP, C: plain black and white squares). You can take advantage of the htmlize function to get a text representation of the universe, e.g.:

print(htmlize(cells))

Test cases

# -*- coding: utf-8 -*-
def htmlize(array):
    s = []
    for row in array:
        for cell in row:
            s.append('▓▓' if cell else '░░')
        s.append('<:LF:>')
    return ''.join(s)

start = [[1,0,0],
         [0,1,1],
         [1,1,0]]
end   = [[0,1,0],
         [0,0,1],
         [1,1,1]]
         
test.describe('Glider<:LF:>' + htmlize(start))
test.it('Glider 1')

resp = get_generation(start, 1)
test.expect(resp == end, 'Got<:LF:>' + htmlize(resp) + '<:LF:>instead of<:LF:>' + htmlize(end))

The solution in Python

Option 1:

def get_neighbours(x, y):
    return {(x + i, y + j) for i in range(-1, 2) for j in range(-1, 2)}

def get_generation(cells, generations):
    if not cells: return cells
    xm, ym, xM, yM = 0, 0, len(cells[0]) - 1, len(cells) - 1
    cells = {(x, y) for y, l in enumerate(cells) for x, c in enumerate(l) if c}
    for _ in range(generations):
        cells = {(x, y) for x in range(xm - 1, xM + 2) for y in range(ym - 1, yM + 2)
                    if 2 < len(cells & get_neighbours(x, y)) < 4 + ((x, y) in cells)}
        xm, ym = min(x for x, y in cells), min(y for x, y in cells)
        xM, yM = max(x for x, y in cells), max(y for x, y in cells)
    return [[int((x, y) in cells) for x in range(xm, xM + 1)] for y in range(ym, yM + 1)]

Option 2 (using numpy):

import numpy as np
from scipy.ndimage import generic_filter

def get_cell(cells):
    m, n = cells[4], sum(cells[:4]+cells[5:])
    return n==3 or (n==2 and m)

def crop_window(cells):
    r, c = tuple(cells.any(i).nonzero()[0] for i in (1,0))
    return cells[r[0]:r[-1]+1, c[0]:c[-1]+1].tolist() if r.size else [[]]
    
def get_generation(cells, gens):
    for i in range(gens):
        cells = np.pad(cells, 1, 'constant')
        cells = generic_filter(cells, get_cell, size=(3,3), mode='constant')
        cells = crop_window(cells)
    return cells

Option 3:

def get_generation(cells, generations):
    C = {(i,j): cells[i][j] for i,r in enumerate(cells) for j,_ in enumerate(r)}
    neig = lambda i,j: sum(C.get((i+x,j+y),0) for x in (0,1,-1) for y in (0,1,-1) if x or y)
    bound = lambda minmax, axis: minmax([t[axis] for t in C if C[t]] or [0])
    interval = lambda axis, pad: range(bound(min,axis)-pad, bound(max,axis)+pad+1)
    for k in range(generations):
        C = {(i,j):C.get((i,j),0) for i in interval(0,1) for j in interval(1,1)}
        C = {t:(C[t] and neig(*t) in (2,3)) or (not C[t] and neig(*t)==3) for t in C}
    return [[C[(i,j)] for j in interval(1,0)] for i in interval(0,0)]

Option 4:

def get_generation(cells, gg):
    for g in range(gg):
        if not cells[0]:
            return [[]]
        for i in "  ":
            ee = lambda: [[0 for x in range(len(cells[0]))] for q in '  ']
            cells = map(list, zip(*(ee() + cells + ee())))
        cells = [[((0, 0, cells[x][y], 1) + (0,)*4)[sum(sum((cells[a][y-1:y+2]
            for a in range(x-1, x+2)), [])) - cells[x][y]]
            for y in range(len(cells[0]))[1:-1]]
            for x in range(len(cells))[1:-1]]
        for i in "  ":
            while not sum(cells[0]):
                cells = cells[1:]
            while not sum(cells[-1]):
                cells = cells[:-1]
            cells = map(list, zip(*cells))
    return cells