## 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.

- If a cell is ON and has fewer than two neighbors that are ON, it turns OFF
- If a cell is ON and has either two or three neighbors that are ON, it remains ON.
- If a cell is ON and has more than three neighbors that are ON, it turns OFF.
- 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:

- Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any live cell with two or three live neighbours lives on to the next generation.
- 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