704 lines
18 KiB
Python
Executable File
704 lines
18 KiB
Python
Executable File
#! /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()
|