advent_of_code_2021

commit cc54381e861ab4c06c07210cdfc8b68c88f6f862
parent 154c34ba3b80eae475fec44d1601030b3bf68063
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Wed, 15 Dec 2021 16:09:04 -0500

Solution to day 15, part 2

Diffstat:
A
day15_part2.py
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 47 insertions(+), 0 deletions(-)
diff --git a/day15_part2.py b/day15_part2.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 15 (part 2): Chiton
+Another graph search problem, but this one requires even more more care"""
+
+# Uh oh, is scipy's implementation of Dijkstra's algorithm fast enough to do a
+# humongous graph? I certainly hope so!
+
+#from typing import List, Tuple, cast
+import numpy as np
+from day15_part1 import (EXAMPLE_INPUT,
+                         grid_to_distance_matrix,
+                         find_shortest_path)
+from utils import get_puzzle_input, convert_input_to_array
+
+def quintuple_grid(input_array: np.ndarray) -> np.ndarray:
+    """Quintuple the input grid in each direction, incrementing the values and
+    using modular arithmetic to stay in the range [1, 9]"""
+    output_array_col = input_array.copy()
+    for row in range(1, 5):
+        output_array_col = np.concatenate((output_array_col, input_array + row),
+                                          axis=0)
+    output_array = output_array_col.copy()
+    for col in range(1, 5):
+        output_array = np.concatenate((output_array, output_array_col + col),
+                                      axis=1)
+    return ((output_array - 1) % 9) + 1
+
+def solve_puzzle(input_string: str) -> int:
+    """Return the numeric solution to the puzzle"""
+    return int(
+        find_shortest_path(
+            grid_to_distance_matrix(
+                quintuple_grid(
+                    convert_input_to_array(input_string)
+                )
+            )
+        )[0][-1]
+    )
+
+def main() -> None:
+    """Run when the file is called as a script"""
+    assert solve_puzzle(EXAMPLE_INPUT) == 315
+    print("Total risk of best path (using larger map):",
+          solve_puzzle(get_puzzle_input(15)))
+
+if __name__ == "__main__":
+    main()