#! /usr/bin/env python3
from collections import namedtuple
from itertools import product
from typing import Any
from typing import Callable
from typing import Iterable
from typing import List
from typing import Optional
from typing import Tuple
from typing import Set


Point = namedtuple("Point", "x y z w", defaults=(0,))


back_refs = {
    "left": "right",
    "right": "left",
    "up": "down",
    "down": "up",
    "front": "back",
    "back": "front",
}

ACTIVE = "#"
INACTIVE = "."


def add_points(p1, p2) -> Point:
    return Point(
        p1.x + p2.x,
        p1.y + p2.y,
        p1.z + p2.z,
        p1.w + p2.w,
    )


class Cube(object):

    def __init__(self, loc: Point, world: "World", active=False):
        self._loc = loc
        self._world = world
        self.active = active

        self._ticked = False

        def _tock():
            # print("Default tock")
            pass

        self.tock = _tock

    # def __init__(self, left=None, up=None, right=None,
    #              down=None, front=None, back=None):
    #     # self.set_neighbor("left", left)
    #     # self.set_neighbor("up", up)
    #     # self.set_neighbor("right", right)
    #     # self.set_neighbor("down", down)
    #     # self.set_neighbor("front", front)
    #     # self.set_neighbor("back", back)
    #
    #     # tock func
    #     self.tock = None

    # def set_neighbor(self, direction: str, value: "Cube"):
    #     backref = back_refs[direction]
    #     setattr(self, direction, value)
    #     if value is not None:
    #         setattr(value, backref, self)

    def neighbors(self, expand=False) -> Iterable["Cube"]:
        seen_points: Set[Point] = set()
        for diff in product((0, 1, -1), repeat=4):
            # from pdb import set_trace; set_trace()
            neighbor_point = add_points(
                self._loc,
                Point(
                    diff[0],
                    diff[1],
                    diff[2],
                    diff[3],
                ),
            )
            if self._loc == neighbor_point:
                # skip self
                continue

            if neighbor_point in seen_points:
                # skip points we've already visited
                # print("Already seen, skipping")
                continue

            seen_points.add(neighbor_point)

            # print(f"Getting point {neighbor_point}")
            neighbor = self._world.get_point(neighbor_point, expand=expand)
            if neighbor is not None:
                # print("FOUND!")
                yield neighbor

    def tick(self):
        active_neighbors = 0
        for neighbor in self.neighbors():
            # print(f"Neighbor is active: {neighbor.active}")
            if neighbor.active:
                # print(f"Neighbor is active {neighbor}")
                active_neighbors += 1

        # if self._loc == Point(1, 3, 0):
        #     import pdb; pdb.set_trace()

        if self.active and active_neighbors not in (2, 3):
            # print("Should go inactive")
            def _tock():
                # print("go inactive")
                self.active = False

            self.tock = _tock
        elif not self.active and active_neighbors == 3:
            # print("Should go active")
            def _tock():
                # print("go active")
                self.active = True

            self.tock = _tock

        else:
            # print("Should do nothing")
            def _tock():
                # print("Empty tock")
                pass

            self.tock = _tock

    def __repr__(self) -> str:
        return f"({self._loc.x}, {self._loc.y}, {self._loc.z})"

    def to_str(self) -> str:
        return ACTIVE if self.active else INACTIVE


class AutoExpanding(object):
    _l: List[Any]
    _zero: int
    _item_factory: Callable[[int], Any]

    def __init__(self):
        self._l = [self._item_factory(0)]
        self._zero = 0

    def get(self, i, expand=True):
        if not expand:
            if self._zero+i < 0:
                raise IndexError(f"index {i} is out of bounds")
            return self._l[self._zero+i]

        if self._zero is None:
            self._l = [self._item_factory(0)]
            self._zero = 0

        if i > 0 and i >= len(self._l) - self._zero - 1:
            # print(f"resize pos to {i} with {self._l} zero={self._zero}")
            self._l = self._l + [
                self._item_factory(j)
                for j in range(len(self._l)-self._zero, i+1)
            ]
            # print(f"> done {self._l} zero={self._zero}")
        elif i < 0 and abs(i) > self._zero:
            # print(f"resize neg to {i} with {self._l} zero={self._zero}")
            self._l = [
                self._item_factory(j)
                for j in range(i, -1 * self._zero)
            ] + self._l
            self._zero = abs(i)
            # print(f"> done {self._l} zero={self._zero}")

        # print(f"Now getting item at index {i} from {self._l}")
        return self._l[self._zero+i]

    def __getitem__(self, i):
        if isinstance(i, slice):
            return [
                self[j]
                for j in range(
                    i.start if i.start is not None else self.min_index(),
                    (i.stop if i.stop is not None else self.max_index()) + 1,
                    i.step or 1,
                )
            ]

        return self.get(i, expand=False)

    def __setitem__(self, i, value):
        self.get(i, expand=True)
        self._l[self._zero+i] = value

    def __len__(self) -> int:
        return len(self._l)

    def __iter__(self):
        return iter(self._l)

    def min_index(self) -> int:
        return -1 * self._zero

    def max_index(self) -> int:
        return len(self._l) - self._zero - 1

    def get_bounds(self) -> Tuple[int, int]:
        return self.min_index(), self.max_index()

    def resize(self, min_index: int, max_index: int):
        if min_index < self.min_index():
            self.get(min_index, expand=True)
        else:
            if min_index > 0:
                raise IndexError("Cannot resize to exclude zero")
            self._l = self[min_index:]
            self._zero = abs(min_index)

        if max_index > self.max_index():
            self.get(max_index, expand=True)
        else:
            if max_index < 0:
                raise IndexError("Cannot resize to exclude zero")
            self._l = self[:max_index]

    def __repr__(self) -> str:
        return f"<AutoExpanding {self._l}>"


class World(AutoExpanding):

    def iter_cubes(self) -> Iterable[Cube]:
        raise NotImplementedError()

    def tick(self):
        for c in self.iter_cubes():
            c.tick()

    def tock(self):
        for c in self.iter_cubes():
            c.tock()

    def get_point(self, p: Point, expand=True) -> Optional[Cube]:
        raise NotImplementedError()

    def trim(self):
        raise NotImplementedError()

    def get_all_bounds(self) -> Tuple[Point, Point]:
        raise NotImplementedError()

    def true_up(self):
        raise NotImplementedError()

    def expand_all(self, i: int):
        raise NotImplementedError()

    def count_active(self) -> int:
        total = 0

        for c in self.iter_cubes():
            if c.active:
                total += 1

        return total


class GridRow(AutoExpanding):
    def __init__(self, y: int, z: int, world: World, w: Optional[int] = 0):
        self._y = y
        self._z = z
        self._w = w
        self._world = world
        super().__init__()

    def _item_factory(self, x: int) -> Cube:
        return Cube(Point(x, self._y, self._z, self._w), self._world)

    def __repr__(self) -> str:
        return "[" + " ".join((str(c) for c in self._l)) + "]"

    def to_str(self) -> str:
        return "".join((c.to_str() for c in self._l))


class GridSlice(AutoExpanding):
    def __init__(self, z: int, world: World, w: Optional[int] = 0):
        self._z = z
        self._w = w
        self._world = world
        super().__init__()

    def _item_factory(self, y: int) -> GridRow:
        return GridRow(y, self._z, self._world, w=self._w)

    def __repr__(self) -> str:
        return f"z={self._z}\n" + "\n".join((
            str(r) for r in self._l
        ))

    def to_str(self) -> str:
        return f"z={self._z}\n" + "\n".join([r.to_str() for r in self._l])


class Grid(World):
    def __init__(self, world: Optional[World] = None, w: Optional[int] = 0):
        if world is not None:
            self._world = world
        else:
            self._world = self

        self._w = w

        super().__init__()

    def _item_factory(self, z: int) -> GridSlice:
        return GridSlice(z, self._world, w=self._w)

    def __repr__(self) -> str:
        return "\n\n".join((
            str(s) for s in self._l
        ))

    def to_str(self) -> str:
        return "\n\n".join((
            s.to_str() for s in self._l
        ))

    def iter_cubes(self) -> Iterable[Cube]:
        for s in self:
            for r in s:
                for c in r:
                    yield c

    def get_point(self, p: Point, expand=True) -> Optional[Cube]:
        try:
            # print(f"expand world z to {p.z}")
            c = self.get(
                p.z,
                expand=expand,
            ).get(
                p.y,
                expand=expand,
            ).get(
                p.x,
                expand=expand,
            )
            # from pdb import set_trace; set_trace()
            return c
        except IndexError:
            return None

    def trim(self):
        for s in self:
            for r in s:
                first, last = None, None
                min_index, max_index = r.get_bounds()
                for i in range(min_index, max_index+1):
                    if r[i].active:
                        if first is None:
                            first = i
                        last = i
                if first is None or first > 0:
                    first = 0
                if last is None or last < 0:
                    last = 0
                r.resize(first, last)

            first, last = None, None
            min_index, max_index = s.get_bounds()
            for i in range(min_index, max_index+1):
                if len(s[i]) > 1 or (len(s[i]) == 1 and s[i][0].active):
                    if first is None:
                        first = i
                    last = i
            if first is None or first > 0:
                first = 0
            if last is None or last < 0:
                last = 0
            s.resize(first, last)

    def get_all_bounds(self) -> Tuple[Point, Point]:
        min_z, max_z = self.get_bounds()
        min_y, max_y = 0, 0
        min_x, max_x = 0, 0

        for s in self:
            if s.min_index() < min_y:
                min_y = s.min_index()

            if s.max_index() > max_y:
                max_y = s.max_index()

            for r in s:
                if r.min_index() < min_x:
                    min_x = r.min_index()

                if r.max_index() > max_x:
                    max_x = r.max_index()

        return Point(min_x, min_y, min_z), Point(max_x, max_y, max_z)

    def true_up(self):
        min_point, max_point = self.get_all_bounds()

        for s in self:
            s.resize(min_point.y, max_point.y)
            for r in s:
                r.resize(min_point.x, max_point.x)

    def expand_all(self, i: int):
        min_point, max_point = self.get_all_bounds()
        # print(f"expand {i} cell")
        # print("expsting min, max:", min_point, max_point)
        min_point = add_points(min_point, Point(-i, -i, -i))
        max_point = add_points(max_point, Point(i, i, i))
        # print("new min, max:", min_point, max_point)
        self.get_point(min_point, expand=True)
        self.get_point(max_point, expand=True)


class HyperGrid(World):
    def __init__(self):
        super().__init__()

    def _item_factory(self, w: int) -> Grid:
        return Grid(world=self, w=w)

    def __repr__(self) -> str:
        return "\n\n".join((
            str(s) for s in self._l
        ))

    def to_str(self) -> str:
        return "\n\n".join((
            f"w = {s._w}, " + s.to_str() for s in self._l
        ))

    def iter_cubes(self) -> Iterable[Cube]:
        for g in self:
            for s in g:
                for r in s:
                    for c in r:
                        yield c

    def get_point(self, p: Point, expand=True) -> Optional[Cube]:
        try:
            # print(f"expand world z to {p.z}")
            c = self.get(
                p.w,
                expand=expand,
            ).get(
                p.z,
                expand=expand,
            ).get(
                p.y,
                expand=expand,
            ).get(
                p.x,
                expand=expand,
            )
            # from pdb import set_trace; set_trace()
            return c
        except IndexError:
            return None

    def get_all_bounds(self) -> Tuple[Point, Point]:
        min_w, max_w = self.get_bounds()
        min_z, max_z = 0, 0
        min_y, max_y = 0, 0
        min_x, max_x = 0, 0

        for g in self:
            if g.min_index() < min_z:
                min_z = g.min_index()

            if g.max_index() > max_z:
                max_z = g.max_index()

            for s in g:
                if s.min_index() < min_y:
                    min_y = s.min_index()

                if s.max_index() > max_y:
                    max_y = s.max_index()

                for r in s:
                    if r.min_index() < min_x:
                        min_x = r.min_index()

                    if r.max_index() > max_x:
                        max_x = r.max_index()

        return (
            Point(min_x, min_y, min_z, min_w),
            Point(max_x, max_y, max_z, max_w),
        )

    def true_up(self):
        min_point, max_point = self.get_all_bounds()
        for g in self:
            g.resize(min_point.z, max_point.z),
            for s in g:
                s.resize(min_point.y, max_point.y)
                for r in s:
                    r.resize(min_point.x, max_point.x)

    def expand_all(self, i: int):
        min_point, max_point = self.get_all_bounds()
        # print(f"expand {i} cell")
        # print("existing min, max:", min_point, max_point)
        min_point = add_points(min_point, Point(-i, -i, -i, -i))
        max_point = add_points(max_point, Point(i, i, i, i))
        # print("new min, max:", min_point, max_point)
        self.get_point(min_point, expand=True)
        self.get_point(max_point, expand=True)


def part1():
    # Load world
    g = Grid()
    with open("input.txt") as f:
        for y, row in enumerate(f):
            row.strip()
            for x, c in enumerate(row):
                g.get(0).get(y).get(x).active = c == ACTIVE

    g.true_up()

    print("time = 0\n_____________")
    print(g.to_str())

    for t in range(6):
        g.expand_all(1)
        g.true_up()

        g.tick()
        g.tock()
        # g.trim()
        g.true_up()

        print(f"time = {t+1}\n_____________")
        print(g.to_str())
        # print(g)

    total = g.count_active()
    print(f"Total active: {total}")


def part2():
    # Load world
    g = HyperGrid()
    with open("input.txt") as f:
        for y, row in enumerate(f):
            row.strip()
            for x, c in enumerate(row):
                g.get(0).get(0).get(y).get(x).active = c == ACTIVE

    g.true_up()

    print("time = 0\n_____________")
    print(g.to_str())

    # g.expand_all(1)
    # g.true_up()
    # print("EXPANDED\ntime = 0\n_____________")
    # print(g.to_str())
    # return

    for t in range(6):
        g.expand_all(1)
        g.true_up()

        g.tick()
        g.tock()
        # g.trim()
        g.true_up()

        # print(f"time = {t+1}\n_____________")
        # print(g.to_str())
        # print(g)

    total = g.count_active()
    print(f"Total active: {total}")


def test():
    g = Grid()

    # print("test")
    # s = [
    #     "...",
    #     "###",
    #     "...",
    # ]
    # for y, row in enumerate(s):
    #     row.strip()
    #     for x, c in enumerate(row):
    #         g.get(0).get(y).get(x).active = c == ACTIVE
    #
    # g.true_up()
    #
    # print("time = 0")
    # print(g.to_str())
    # print(g)
    #
    # p = g.get(0).get(0).get(1)
    # from pdb import set_trace; set_trace()
    # p.tick()
    # p.tock()
    # print(g.to_str())
    #
    # p = g.get(0).get(2).get(1)
    # from pdb import set_trace; set_trace()
    # p.tick()
    # p.tock()
    # print(g.to_str())

    # print(list(g[0][0][0].neighbors()))
    #
    # print(g.to_str())
    #
    #
    # return

    # g.get(1).get(1).get(1)
    # g.get_point(Point(1, 1, 1))
    # g.expand_all(1)
    # g.true_up()
    # print(g)

    # r = GridRow(0, 0, None)
    # print(r)
    # r.get(1)
    # print(r)
    # print(r[:3])
    # r.get(-3)
    # # print(r[0:3])
    # print(r[-2:])
    #
    # print("Resize")
    # print(r)
    # r.resize(0, 3)
    # print(r)

    # return

    # c = g.get(0).get(0).get(0)
    # print(g)
    # from pdb import set_trace; set_trace()
    # neigh = list(c.neighbors())
    # print(neigh)
    #
    # return

    print("test")
    s = [
        ".#.",
        "..#",
        "###",
    ]
    for y, row in enumerate(s):
        row.strip()
        for x, c in enumerate(row):
            g.get(0).get(y).get(x).active = c == ACTIVE

    g.true_up()

    print("time = 0\n_____________")
    print(g.to_str())
    # print(g)

    # g.expand_all(1)
    # g.true_up()
    # print(g.to_str())
    # print(g)
    # return

    for t in range(6):
        g.expand_all(1)
        g.true_up()
        # print(g.to_str())
        # p = g.get(0).get(3).get(1)
        # from pdb import set_trace; set_trace()

        g.tick()
        g.tock()
        # g.trim()
        g.true_up()

        print(f"time = {t+1}\n_____________")
        print(g.to_str())
        # print(g)

    total = g.count_active()
    print(f"Total active: {total}")


if __name__ == "__main__":
    # part1()
    part2()