99 lines
2.3 KiB
Python
99 lines
2.3 KiB
Python
from math import lcm
|
|
from dataclasses import dataclass
|
|
|
|
with open("input/day13.txt") as f:
|
|
input = f.read()
|
|
|
|
scanners: dict[int, int] = {}
|
|
|
|
for line in input.splitlines():
|
|
parts = line.split(": ")
|
|
d, r = int(parts[0]), int(parts[1])
|
|
|
|
assert d not in scanners, "no overlapping scanners"
|
|
scanners[d] = r
|
|
|
|
|
|
def part1(scanners):
|
|
severity = 0
|
|
for d in range(max(scanners.keys()) + 1):
|
|
r = scanners.get(d)
|
|
if r is None:
|
|
continue
|
|
|
|
assert r > 1, r
|
|
cycle = (r - 1) * 2
|
|
pos = d % cycle
|
|
if pos == 0:
|
|
severity += d * r
|
|
return severity
|
|
|
|
|
|
def is_safe(scanners, delay):
|
|
for depth in range(max(scanners.keys()) + 1):
|
|
r = scanners.get(depth)
|
|
if r is None:
|
|
continue
|
|
|
|
assert r > 1, r
|
|
cycle = (r - 1) * 2
|
|
pos = (delay + depth) % cycle
|
|
if pos == 0:
|
|
return False
|
|
return True
|
|
|
|
|
|
@dataclass
|
|
class Scanner:
|
|
depth: int
|
|
cycle: int
|
|
|
|
|
|
@dataclass(order=True)
|
|
class Candidate:
|
|
delay: int
|
|
increment: int
|
|
|
|
def __init__(self, delay: int, increment: int):
|
|
self.delay = delay % increment
|
|
self.increment = increment
|
|
|
|
def __hash__(self):
|
|
return hash((self.delay % self.increment, self.increment))
|
|
|
|
def scale(self, scalar: int) -> set["Candidate"]:
|
|
res = set()
|
|
increment = self.increment * scalar
|
|
for i in range(scalar + 1):
|
|
res.add(Candidate(self.delay + i * self.increment, increment))
|
|
return res
|
|
|
|
def __str__(self):
|
|
return f"{self.delay} + k * {self.increment}"
|
|
|
|
|
|
def part2(scanner_map: dict[int, int]):
|
|
scanners: list[Scanner] = []
|
|
for depth in range(max(scanner_map.keys()) + 1):
|
|
r = scanner_map.get(depth)
|
|
if r is None:
|
|
continue
|
|
cycle = (r - 1) * 2
|
|
scanners.append(Scanner(depth, cycle))
|
|
|
|
candidates = {Candidate(0, 1)}
|
|
for s in scanners:
|
|
next: set[Candidate] = set()
|
|
for c in candidates:
|
|
scalar = lcm(c.increment, s.cycle) // c.increment
|
|
for n in c.scale(scalar):
|
|
if (n.delay + s.depth) % s.cycle:
|
|
next.add(n)
|
|
|
|
candidates = next
|
|
|
|
return min(c.delay for c in candidates)
|
|
|
|
|
|
print(part1(scanners))
|
|
print(part2(scanners))
|