aoc-2023/d10/main.py
2023-12-11 11:50:34 -08:00

276 lines
7.4 KiB
Python

from collections.abc import Generator
from itertools import product
from pathlib import Path
from typing import NamedTuple
class Point(NamedTuple):
x: int
y: int
def iter_adjacent(self, wrap=False) -> Generator["Point", None, None]:
for offset in product((1, 0, -1), (1, 0, -1)):
adj = Point(self.x + offset[0], self.y + offset[1])
if adj == self:
continue
if not wrap and (adj.x < 0 or adj.y < 0):
continue
yield adj
def add_point(self, delta: "Point") -> "Point":
return Point(self.x + delta.x, self.y + delta.y)
def add(self, x=0, y=0) -> "Point":
return Point(self.x + x, self.y + y)
def __str__(self) -> str:
return f"Point({self.x}, {self.y})"
class Cell(NamedTuple):
coord: Point
pipe: str
@property
def n(self) -> Point | None:
if self.pipe in {"S", "|", "L", "J"}:
return Point(self.coord.x, self.coord.y - 1)
@property
def e(self) -> Point | None:
if self.pipe in {"S", "-", "L", "F"}:
return Point(self.coord.x + 1, self.coord.y)
@property
def s(self) -> Point | None:
if self.pipe in {"S", "|", "7", "F"}:
return Point(self.coord.x, self.coord.y + 1)
@property
def w(self) -> Point | None:
if self.pipe in {"S", "-", "J", "7"}:
return Point(self.coord.x - 1, self.coord.y)
def iter_pipes(self) -> Generator[Point, None, None]:
if coord := self.n:
yield coord
if coord := self.e:
yield coord
if coord := self.s:
yield coord
if coord := self.w:
yield coord
class Grid:
def __init__(self, lines: list[str]):
self.lines = lines
self.loop: list[Point] = []
self.start_val = ""
@property
def start(self) -> Point:
for y, row in enumerate(self.lines):
for x, cell in enumerate(row):
if cell == "S":
return Point(x, y)
raise ValueError("No S")
def get_cell(self, coord: Point) -> Cell:
if coord == self.start and self.start_val:
return Cell(coord, self.start_val)
return Cell(coord, self.lines[coord.y][coord.x])
def replace_start(self):
d = ""
for neighbor in (self.get_cell(p) for p in self.start.iter_adjacent()):
if neighbor.n == self.start:
d += "S"
if neighbor.e == self.start:
d += "W"
if neighbor.s == self.start:
d += "N"
if neighbor.w == self.start:
d += "E"
d = "".join(sorted(d))
if d == "NS":
self.start_val = "|"
if d == "EW":
self.start_val = "-"
if d == "EN":
self.start_val = "L"
if d == "ES":
self.start_val = "F"
if d == "SW":
self.start_val = "7"
if d == "NW":
self.start_val = "J"
print(d, "Replaced S with", self.start_val)
def find_loop(self) -> None:
current = self.get_cell(self.start)
print(current)
self.loop.append(current.coord)
for neighbor_coord in current.iter_pipes():
if not all(a >= 0 for a in neighbor_coord):
continue
for nn_coord in self.get_cell(neighbor_coord).iter_pipes():
if nn_coord == self.start:
current = self.get_cell(neighbor_coord)
while True:
# print("Now at", current)
self.loop.append(current.coord)
# Go through neighbors
for neighbor_coord in current.iter_pipes():
# If we've already seen this, we skip because we only want to go forward
if neighbor_coord in self.loop:
continue
# Take first non-backtrack
current = self.get_cell(neighbor_coord)
break
else:
print("Nothing we haven't seen here")
break
def cast_ray_nw(self, point: Point) -> int:
# Incomplete accounting of edge cases
count = 0
steps = min(point.x, point.y)
for s in range(steps):
p = Point(point.x - s, point.y - s)
if p in self.border:
if self.get_cell(p).pipe not in {"L", "7"}:
count += 1
return count
def cast_ray_w(self, point: Point) -> int:
count = 0
# Technically we walk left to right, so this should be the order of corners
tan_corners = {
"L": "J",
"F": "7",
}
last_corner = ""
for s in range(point.x):
p = Point(s, point.y)
if p in self.border:
c = self.get_cell(p).pipe
if c == "S":
raise ValueError("An S?")
if c in tan_corners:
print("Found tan corner", c, "at", p)
last_corner = c
elif c == "-":
continue
elif last_corner and c == tan_corners[last_corner]:
print("Found tan corner end", c, "at", p)
last_corner = ""
else:
print("Non-tan", c, "at", p)
count += 1
last_corner = ""
return count
def cast_ray_s(self, point: Point) -> int:
# Incomplete accounting of edge cases
count = 0
for s in range(point.y):
p = Point(point.x, s)
if p in self.border:
count += 1
return count
def inside(self, point: Point) -> bool:
if point in self.border:
return False
return all(
(count % 2) == 1
for count in (
# self.cast_ray_nw(point),
self.cast_ray_w(point),
# self.cast_ray_s(point),
)
)
def count_area(self) -> int:
self.border = set(self.loop)
self.replace_start()
total_area = 0
for y, row in enumerate(self.lines):
for x, _ in enumerate(row):
point = Point(x, y)
# This could be optimized by caching the counts for points to do it in O(n), but yolo
if self.inside(point):
print(point, "inside")
total_area += 1
else:
print(point, "outside")
return total_area
def area(coords: list[Point]) -> int:
area = 0
last: Point | None = None
for point in coords:
if last is None:
last = point
else:
dx = point.x - last.x
dy = point.y - last.y
area += 0.5 * (last.y * dx - last.x * dy)
last = point
return int(area)
def part1(input: Path) -> int:
grid = Grid(input.read_text().split("\n"))
grid.find_loop()
return int(len(grid.loop) / 2)
def part2(input: Path) -> int:
grid = Grid(input.read_text().split("\n"))
grid.find_loop()
return grid.count_area()
if __name__ == "__main__":
# input = Path("sample1.txt")
# input = Path("sample2.txt")
input = Path("input.txt")
result1 = part1(input)
print("part 1", result1)
# input = Path("sample3.txt")
# input = Path("sample4.txt")
# input = Path("sample5.txt")
result2 = part2(input)
print("part 2", result2)