from typing import Tuple, List, Iterator, TextIO, Dict, Callable
from typing_extensions import Protocol


Coords = Tuple[int, int]

Field = List[List['Cell']]

Context = Field


def directions() -> Iterator[Coords]:
	for i in range(-1, 2):
		for j in range(-1, 2):
			if (i, j) != (0, 0):
				yield i, j


def show_cells(cells: Field) -> str:
	return "\n".join(map(lambda row: "".join(
		map(lambda c: str(c), row)), cells))


# reject inheritance, embrace composition
class Cell(Protocol):
	def update(self, ctx: Field) -> 'Cell':
		...


def count_alive(ctx: Field) -> int:
	n = 0
	for y in range(len(ctx)):
		for x in range(len(ctx[y])):
			if (y, x) != (1, 1) and not isinstance(ctx[y][x], DeadCell):
				n += 1
	return n


class DeadCell:
	def update(self, ctx: Field) -> Cell:
		if count_alive(ctx) == 3:
			return AliveCell()
		else:
			return self

	def __str__(self) -> str:
		return "-"


class AliveCell:
	def update(self, ctx: Field) -> Cell:
		if count_alive(ctx) in [2, 3]:
			return self
		else:
			return DeadCell()

	def __str__(self) -> str:
		return "o"


Registry = Dict[str, Callable[[], Cell]]
# help MyPy figure out what we want
rl: List[Callable[[], Cell]] = [DeadCell, AliveCell]
registry: Registry = {t.__name__: t for t in rl}
del rl


def in_bounds(p: Coords, b: Coords) -> bool:
	return 0 <= p[0] and p[0] < b[0] and 0 <= p[1] and p[1] < b[1]


def make_world(size: int) -> Field:
	return [[DeadCell() for x in range(size)] for y in range(size)]


class World:
	size: int
	cells: List[List[Cell]]

	def __init__(self, size: int) -> None:
		self.size = size
		self.cells = make_world(size)

	def update(self) -> None:
		# this line had me stumped for hours :)
		# i switched from dict to list, but forgot to change cells.copy() to a 2-deep copy
		# the Rust people were right, mutable aliasing is the root of all evil
		# i miss Haskell
		new_cells = [row.copy() for row in self.cells]
		for y in range(self.size):
			for x in range(self.size):
				ctx = make_world(3)
				ctx[1][1] = self.cells[y][x]
				for dy, dx in directions():
					p = (y + dy, x + dx)
					if in_bounds(p, (self.size, self.size)):
						ctx[1 + dy][1 + dx] = self.cells[p[0]][p[1]]
				new_cells[y][x] = self.cells[y][x].update(ctx)
		self.cells = new_cells

	def __str__(self) -> str:
		return show_cells(self.cells)

	def dump(self, f: TextIO) -> None:
		# format version
		print(0, file=f)
		print(self.size, file=f)
		for row in self.cells:
			print(",".join([type(cell).__name__ for cell in row]), file=f)

	@staticmethod
	def load(f: TextIO, registry: Registry = registry) -> 'World':
		v = int(f.readline())
		if v != 0:
			raise Exception("wrong format version")
		size = int(f.readline())
		w = World(size)
		for y, line in enumerate(f):
			for x, cell in enumerate(line.strip().split(",")):
				w.cells[y][x] = registry[cell]()
		return w


#if __name__ == '__main__':
world = World(30)
# create a glider
for y, x in [(0, 1), (2, 0), (2, 1), (2, 2), (1, 2)]:
	world.cells[y][x] = AliveCell()
for _ in range(100):
	print(world)
	world.update()