day 5

1 files changed, 93 insertions, 0 deletions

diff --git a/5.py b/5.py
new file mode 100644
index 0000000..bcaf85c
--- /dev/null
+++ b/5.py
@@ -0,0 +1,93 @@
+# pyright: strict
+from collections.abc import Iterator
+from dataclasses import dataclass
+from sys import stdin
+
+
+@dataclass(frozen=True)
+class Range:
+    start: int
+    length: int
+
+
+@dataclass
+class MappedRange:
+    destination: int
+    source: int
+    length: int
+
+
+@dataclass
+class Mapping:
+    source: str
+    destination: str
+    ranges: list[MappedRange]
+
+    def map(self, n: int) -> int:
+        for r in self.ranges:
+            if n >= r.source and n < r.source + r.length:
+                return n - r.source + r.destination
+        return n
+
+    def map_range(self, t: Range) -> Iterator[Range]:
+        start = t.start
+        length = t.length
+        for r in sorted(self.ranges, key=lambda r: r.source):
+            if start + length <= r.source:
+                return
+            if start >= r.source + r.length:
+                continue
+            if start < r.source:
+                rlen = r.source - start
+                yield Range(start, rlen)
+                start += rlen
+                length -= rlen
+            rlen = min(length, r.length - (start - r.source))
+            yield Range(start - r.source + r.destination, rlen)
+            start += rlen
+            length -= rlen
+            if length <= 0:
+                return
+        yield Range(start, length)
+
+
+seeds, *maps = stdin.read().rstrip("\n").split("\n\n")
+seeds = list(map(int, seeds.removeprefix("seeds: ").split()))
+mappings: dict[str, Mapping] = dict()
+for m in maps:
+    header, ranges = m.split("\n", maxsplit=1)
+    source, dest = header.removesuffix(" map:").split("-to-")
+    ranges = [MappedRange(*map(int, r.split())) for r in ranges.split("\n")]
+    mappings[source] = Mapping(source, dest, ranges)
+
+
+def recmap(mappings: dict[str, Mapping], current: str, value: int) -> int:
+    if current not in mappings:
+        return value
+    mapping = mappings[current]
+    return recmap(mappings, mapping.destination, mapping.map(value))
+
+
+def recmap_range(
+    mappings: dict[str, Mapping], current: str, range_: Range
+) -> Iterator[Range]:
+    if current not in mappings:
+        yield range_
+        return
+    mapping = mappings[current]
+    for r in mapping.map_range(range_):
+        for s in recmap_range(mappings, mapping.destination, r):
+            yield s
+
+
+print(min(recmap(mappings, "seed", seed) for seed in seeds))
+print(
+    min(
+        (
+            r
+            for i in range(0, len(seeds), 2)
+            for r in recmap_range(mappings, "seed", Range(seeds[i], seeds[i + 1]))
+        ),
+        key=lambda r: r.start,
+    ).start
+)