2023 d5 p2

k2bd · k2bd · commit 97323d0067e9 · 2023-12-05T19:17:18.000Z
diff --git a/src/advent_of_code/y2023/d5.py b/src/advent_of_code/y2023/d5.py
@@ -1,8 +1,8 @@
-from typing import Any
-from advent_of_code.util import format_solution, puzzle_input
 from collections import UserDict
 from dataclasses import dataclass, field
 
+from advent_of_code.util import format_solution, puzzle_input
+
 
 @dataclass
 class AlmanacMap(UserDict):
@@ -18,11 +18,53 @@ def set_key_range(self, key_start: int, value_start: int, map_range: int):
 
     def __getitem__(self, key: int) -> int:
         for key_start, value_start, map_range in self.key_ranges:
-            if key_start <= key <= key_start + map_range:
+            if key_start <= key < key_start + map_range:
                 return value_start + (key - key_start)
         else:
             return key
 
+    def transform_range(
+        self, range_start: int, range_size: int
+    ) -> list[tuple[int, int]]:
+        """
+        Transform a range of numbers by the mapping, returning potentially many
+        (start, size) pairs
+        """
+        untransformed_ranges = [(range_start, range_size)]
+        result = []
+
+        for map_key_start, map_value_start, map_range in self.key_ranges:
+            new_untransformed = []
+            for u_range_start, u_range_size in untransformed_ranges:
+                overlap_min = max(map_key_start, u_range_start)
+                overlap_max = min(
+                    map_key_start + map_range - 1,
+                    u_range_start + u_range_size - 1,
+                )
+
+                if overlap_min <= overlap_max:
+                    # Transform the overlap and add the rest to the new
+                    # untransformed list
+                    map_offset = overlap_min - map_key_start
+                    transformed_start = map_value_start + map_offset
+                    transformed_size = overlap_max + 1 - overlap_min
+                    result.append((transformed_start, transformed_size))
+
+                    if overlap_min > u_range_start:
+                        nu_start = u_range_start
+                        nu_size = overlap_min - nu_start
+                        untransformed_ranges.append((nu_start, nu_size))
+                    if overlap_max < (u_range_start + u_range_size - 1):
+                        nu_start = overlap_max + 1
+                        nu_size = (u_range_start + u_range_size) - nu_start
+                        untransformed_ranges.append((nu_start, nu_size))
+                else:
+                    new_untransformed.append((u_range_start, u_range_size))
+
+            untransformed_ranges = new_untransformed
+
+        return result + untransformed_ranges
+
 
 @dataclass
 class Almanac:
@@ -84,6 +126,24 @@ def get_seed_location(self, seed: int):
             ]
         ]
 
+    def get_min_seed_range_location(self, seed_range: tuple[int, int]) -> int:
+        """
+        Get the minimum location across the given seed range
+        """
+        range_mins = set()
+        for r0 in self.seed_to_soil.transform_range(*seed_range):
+            for r1 in self.soil_to_fertilizer.transform_range(*r0):
+                for r2 in self.fertilizer_to_water.transform_range(*r1):
+                    for r3 in self.water_to_light.transform_range(*r2):
+                        for r4 in self.light_to_temperature.transform_range(*r3):
+                            for r5 in self.temperature_to_humidity.transform_range(*r4):
+                                for r6 in self.humidity_to_location.transform_range(
+                                    *r5
+                                ):
+                                    range_mins.add(r6[0])
+
+        return min(range_mins)
+
 
 def part_1(almanac_input: list[str]) -> int:
     almanac = Almanac.from_input(almanac_input)
@@ -94,6 +154,17 @@ def part_1(almanac_input: list[str]) -> int:
 
 def part_2(almanac_input: list[str]) -> int:
     almanac = Almanac.from_input(almanac_input)
+    seed_range_values = [
+        int(s) for s in almanac_input[0].split("seeds:")[1].strip().split()
+    ]
+    seed_ranges = [
+        (seed_range_values[i], seed_range_values[i + 1])
+        for i in range(0, len(seed_range_values), 2)
+    ]
+
+    return min(
+        almanac.get_min_seed_range_location(seed_range) for seed_range in seed_ranges
+    )
 
 
 if __name__ == "__main__":
diff --git a/tests/test_y2023/test_d5.py b/tests/test_y2023/test_d5.py
@@ -1,5 +1,4 @@
-from advent_of_code.y2023.d5 import part_1, part_2, AlmanacMap
-
+from advent_of_code.y2023.d5 import AlmanacMap, part_1, part_2
 
 TEST_INPUT = [
     "seeds: 79 14 55 13",
@@ -42,5 +41,15 @@ def test_part_1():
     assert part_1(TEST_INPUT) == 35
 
 
+def test_transform_range():
+    almanac = AlmanacMap()
+    almanac.set_key_range(3, 13, 6)
+    almanac.set_key_range(11, 31, 3)
+
+    transformed = almanac.transform_range(7, 6)
+
+    assert transformed == [(17, 2), (31, 2), (9, 2)]
+
+
 def test_part_2():
-    assert part_2(TEST_INPUT) == 0
+    assert part_2(TEST_INPUT) == 46
