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