Given a 2D array and a number of generations, compute n timesteps of [Conway's Game of Life](http://en.wikipedia.org/wiki/Conway%27s_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](https://en.wikipedia.org/wiki/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.:

```python
print(htmlize(cells))
````

~~~if:c
In **C**, the initial dimensions of the GoL universe is passed into your function *by reference* via the pointers `rowptr` and `colptr`.  When expanding/contracting the GoL universe, please keep track of the dimensions of the modified grid through these two variables.
~~~

Difficulty: MEDIUM_HARD
Tags: Data structures

Game theory

Ad-hoc
Skill types: Data structures

Starter code:
def get_generation(cells, gen):
	

Solutions:
def get(cells, i, j):
	return cells[i][j] if i > -1 and j > -1 and (i < len(cells)) and (j < len(cells[0])) else 0

def num_neighbors(cells, i, j):
	return get(cells, i, j + 1) + get(cells, i, j - 1) + get(cells, i + 1, j) + get(cells, i - 1, j) + get(cells, i - 1, j - 1) + get(cells, i - 1, j + 1) + get(cells, i + 1, j - 1) + get(cells, i + 1, j + 1)

def next_cell(cell, i, j):
	n = num_neighbors(cell, i, j)
	return int(0 if n < 2 or n > 3 else 1 if cell[i][j] else n == 3)

def expand(cells):
	row = [0] * (len(cells[0]) + 2)
	return [row] + [[0] + r + [0] for r in cells] + [row]

def trim(cells):
	while not any(cells[0]):
		del cells[0]
	while not any(cells[-1]):
		del cells[-1]
	while not any([row[0] for row in cells]):
		list(map(lambda x: x.pop(0), cells))
	while not any([row[-1] for row in cells]):
		list(map(lambda x: x.pop(), cells))

def next_gen(cells):
	cells = expand(cells)
	cells = [[next_cell(cells, i, j) for j in range(len(cells[i]))] for i in range(len(cells))]
	trim(cells)
	return cells

def get_generation(cells, generations):
	for i in range(generations):
		cells = next_gen(cells)
	if not cells:
		return [[]]
	return cells


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)]


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


import copy

def add_space(cells):
	row = [[0] * (len(cells[0]) + 2)]
	return row + [[0] + x + [0] for x in cells] + copy.deepcopy(row)

def cut_space(cells):
	for i in range(-1, 1):
		while cells[i].count(1) == 0:
			cells.pop(i)
		while [cells[n][i] for n in range(len(cells))].count(1) == 0:
			for n in range(len(cells)):
				cells[n].pop(i)
	return cells

def morph_cell(neighbours, cell):
	if cell == 1:
		if neighbours.count(1) < 2 or neighbours.count(1) > 3:
			return 0
	if cell == 0 and neighbours.count(1) == 3:
		return 1
	else:
		return cell

def get_neighbours(cells, coords):
	neighbours = []
	for n in range(max(0, coords[0] - 1), min(len(cells), coords[0] + 2)):
		for m in range(max(0, coords[1] - 1), min(len(cells[n]), coords[1] + 2)):
			neighbours.append(cells[n][m])
	if cells[coords[0]][coords[1]] == 1:
		neighbours = sorted(neighbours)[:-1]
	else:
		neighbours = sorted(neighbours)[1:]
	return morph_cell(neighbours, cells[coords[0]][coords[1]])

def new_step(cells, new_cells):
	for i in range(len(cells)):
		for j in range(len(cells[i])):
			new_cells[i][j] = get_neighbours(cells, (i, j))
	return new_cells

def get_generation(cells, generations):
	while generations != 0:
		cells = add_space(cells)
		new_cells = copy.deepcopy(cells)
		new_cells = cut_space(new_step(cells, new_cells))
		cells = new_cells
		print(cells)
		generations -= 1
	return cells


def get_generation(cells, generations):
	if generations == 0:
		return cells
	alive = set(((rindex, cindex) for (rindex, row) in enumerate(cells) for (cindex, cell) in enumerate(row) if cell == 1))
	for _ in xrange(generations):
		neighbours = [(cell[0] + y, cell[1] + x) for cell in alive for y in xrange(-1, 2) for x in xrange(-1, 2) if (y, x) != (0, 0)]
		alive = set((cell for cell in neighbours if neighbours.count(cell) == 3 or (cell in alive and neighbours.count(cell) == 2)))
	(ys, xs) = zip(*alive)
	cells = [[1 if (rindex, cindex) in alive else 0 for cindex in range(min(xs), max(xs) + 1)] for rindex in range(min(ys), max(ys) + 1)]
	return cells


def get_generation(cells, gen):
	ng = Life(cells)
	return Life.process(ng, gen)

class Life:
	neighbor = [(x, y) for x in range(-1, 2) for y in range(-1, 2) if x or y]

	def __init__(self, cells):
		self.cells = [e[:] for e in cells]
		self._forLife = lambda x, y: int(self._express(x, y) in (2, 3))
		self._forDead = lambda x, y: int(self._express(x, y) == 3)

	@property
	def _lenY(self):
		return len(self.cells[0])

	@property
	def core(self):
		return {(x, y): c for (x, e) in enumerate(self.cells) for (y, c) in enumerate(e)}

	def _express(self, xc, yc):
		core = self.core
		return sum((self.cells[x + xc][y + yc] for (x, y) in self.neighbor if core.get((x + xc, y + yc)) != None))

	@classmethod
	def process(cls, self, gen):
		for _ in range(gen):
			cls._add_field(self)
			nextG = [e[:] for e in self.cells]
			for ((x, y), c) in self.core.items():
				nextG[x][y] = {0: self._forDead, 1: self._forLife}.get(c)(x, y)
			self.cells = cls._del_field(nextG)
		return self.cells

	@classmethod
	def _add_field(cls, self):
		for _ in range(4):
			self.cells = [list(e) for e in zip(*self.cells[::-1])]
			if any(self.cells[0]):
				self.cells.insert(0, [0] * self._lenY)

	@staticmethod
	def _del_field(field, cut=4):
		for _ in range(4):
			field = [list(e) for e in zip(*field[::-1])]
			while not any(field[0]):
				field.pop(0)
		return field


from typing import List, Tuple

class Game(List[List[bool]]):

	def __init__(self, cells: List[List[int or bool]]) -> None:
		if not cells[0]:
			self.height = self.width = 2
			self[0:2] = [[False, False], [False, False]]
			return
		self.height: int = len(cells)
		self.width: int = len(cells[0])
		for i in range(len(cells)):
			row = []
			for val in cells[i]:
				row.append(bool(val))
			self.append(row)
		self.__trim()

	def __trim(self) -> None:
		for _ in range(self.height):
			row = self[0]
			if True in row:
				break
			del self[0]
			self.height -= 1
		for _ in reversed(list(range(self.height))):
			row = self[-1]
			if True in row:
				break
			del self[-1]
			self.height -= 1
		empty = True
		while empty:
			for row in self:
				if row[0]:
					empty = False
					break
			else:
				for row in self:
					del row[0]
				self.width -= 1
		empty = True
		while empty:
			for row in self:
				if row[-1]:
					empty = False
					break
			else:
				for row in self:
					del row[-1]
				self.width -= 1

	def __pad(self) -> None:
		self.width += 2
		self.height += 2
		for i in self:
			i.insert(0, False)
			i.append(False)
		self.insert(0, [False] * self.width)
		self.append([False] * self.width)

	def __neighbors(self, i: int, j: int):
		north = i == 0
		west = j == 0
		south = i == self.height - 1
		east = j == self.width - 1
		return int((self[i - 1][j - 1] if not north and (not west) else 0) + (self[i - 1][j] if not north else 0) + (self[i - 1][j + 1] if not north and (not east) else 0) + (self[i][j - 1] if not west else 0) + (self[i][j + 1] if not east else 0) + (self[i + 1][j - 1] if not south and (not west) else 0) + (self[i + 1][j] if not south else 0) + (self[i + 1][j + 1] if not south and (not east) else 0))

	def iterate(self):
		self.__pad()
		queue: List[Tuple[int, int]] = []
		for i in range(self.height):
			for j in range(self.width):
				status = self[i][j]
				neighbors = self.__neighbors(i, j)
				if status and (neighbors < 2 or neighbors > 3) or (not status and neighbors == 3):
					queue.append((i, j))
		for (i, j) in queue:
			self[i][j] = not self[i][j]
		self.__trim()

	def export(self) -> List[List[int]]:
		if not self.height or not self.width:
			return [[]]
		out: List[List[int]] = []
		for i in self:
			row = []
			for j in i:
				row.append(int(j))
			out.append(row)
		return out

def get_generation(cells: List[List[str]], generations):
	board = Game(cells)
	for _ in range(generations):
		board.iterate()
	return board.export()


import numpy as np

def next_gen(grid):
	neighbours = np.array([np.roll(grid, (i, j), axis=(0, 1)) for i in [-1, 0, 1] for j in [-1, 0, 1]]).sum(axis=0) - grid
	return (neighbours == 3) | grid & (neighbours == 2)

def unpad(grid):
	if grid[0,].sum() == 0:
		return unpad(grid[1:])
	if grid[-1,].sum() == 0:
		return unpad(grid[:-1])
	if grid[:, 0].sum() == 0:
		return unpad(grid[:, 1:])
	if grid[:, -1].sum() == 0:
		return unpad(grid[:, :-1])
	return grid

def get_generation(cells, generations):
	cells = np.array(cells)
	for _ in range(generations):
		cells = next_gen(np.pad(cells, 1, mode='constant'))
	return unpad(cells).tolist()