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: interview

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 copy
def pad(cells):
  for x in cells:
    x.append(0)
    x.insert(0, 0)
  cells.append([0] * len(cells[0]))
  cells.insert(0, [0] * len(cells[0]))
  return cells
def trim_world(cells):
  while all(i == 0 for i in cells[0]): cells.pop(0)
  while all(i == 0 for i in cells[-1]): cells.pop()
  while all(i[0] == 0 for i in cells): cells = [x[1:] for x in cells]
  while all(i[-1] == 0 for i in cells): cells = [x[:-1] for x in cells]
  return cells
def get_generation(cells, generations):
  cells = copy.deepcopy(cells)
  for g in range(generations):
    cells = pad(cells)
    new_world = copy.deepcopy(cells)
    for i in range(len(new_world)):
      for j in range(len(new_world[i])):
        count = 0
        for k in range(-1, 2):
          for l in range(-1, 2):
            try:
              if (k != 0 or l != 0) and (i + k) > -1 and (j + l) > -1 and cells[i + k][j + l]: count += 1
            except IndexError: '''meh'''
        new_world[i][j] = cells[i][j] if count == 2 else 1 if count == 3 else 0
    cells = trim_world(new_world)
  return cells



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
    
    # avoid checking the whole array
    alive = set((rindex, cindex) for rindex, row 
                 in enumerate(cells) for cindex, cell in enumerate(row) 
                 if cell == 1)
    
    for _ in xrange(generations):
        
        # if a cell has x neighbours, its coordinates will appear x times in list
        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)]
        
        # new generation
        alive = set(cell for cell in neighbours 
                    if (neighbours.count(cell) == 3) 
                       or (cell in alive and neighbours.count(cell) == 2))
    
    # rebuild the array around the living cells of the last generation
    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

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

class Life:
    
    def __init__(self, cells):
        self.cells = [e[::] for e in cells]
        self.neighbor = [(x,y) for x in range(-1,2) for y in range(-1,2) if x or y] 
        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 _lenX(self):
        return len(self.cells)
    
    @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 )
        
        
    def process(self, gen):
        for _ in range(gen):
            self._add_field()
            nextG = [e[::] for e in self.cells]
            for (x,y),c in list(self.core.items()):
                nextG[x][y] = {0:self._forDead, 1:self._forLife}.get(c)(x,y)
            self.cells = self._del_field(nextG)
        return self.cells
            
    def _add_field(self):
        for i,(s,e) in enumerate([(0,self._lenY+1)]*self._lenX):
            self.cells[i].insert(s, 0);self.cells[i].insert(e, 0)
        for _ in (s,e+1): self.cells.insert(_, [0]*(self._lenY)) 

    def _del_field(self, 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()