# coding=utf-8


import collections
from operator import add

from typing import List, Set


class Point(collections.namedtuple("Point", "x y")):
    __slots__ = ()

    def __add__(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        return self.__class__._make(map(lambda x: add(*x), zip(self, other))) #abstract as fuck!


Frame = Set[Point]


def neighbors(point: Point) -> List[Point]:
    yield from (Point(x, y) + point
                for y in range(-1, 2)
                for x in range(-1, 2)
                if (x, y) != (0, 0))


def next_frame(frame: Frame) -> Frame:
    # count neighbors for each cell
    neighbor_count = collections.defaultdict(int)
    for cell in frame:
        for neighbor in neighbors(cell):
            neighbor_count[neighbor] += 1

    # Create output
    output = set()
    for cell in neighbor_count.keys() | frame:
        if cell in frame:  # live cell ...
            if 2 <= neighbor_count[cell] <= 3:
                output.add(cell)  # ... lives
        else:  # dead cell ...
            if neighbor_count[cell] == 3:
                output.add(cell)  # ... lives
    return output


glider = {Point._make(x) for x in [(0, 0), (1, 0), (2, 0), (2, 1), (1, 2)]}
result = glider.copy()
for n in range(4):
    result = next_frame(result)

print(glider == {item + Point(-1, 1) for item in result})