commit 2b670b6d4dd9271ab57fdc292d0c619f62b1a3e0
parent 3164e7220836904bd742529f6ab16fd14d7f9632
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Sun, 12 Dec 2021 17:18:18 -0500
Solution to day 12, part 1
Diffstat:
| A | day12_part1.py | | | 128 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 128 insertions(+), 0 deletions(-)
diff --git a/day12_part1.py b/day12_part1.py
@@ -0,0 +1,128 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 12 (part 1): Passage Pathing
+This problem is graph search, with the wrinkle that "large caves" can be
+visited more than once"""
+
+# We'll find all the paths from `start` to `end` in order to count them. This
+# is basically a very straightforward graph traversal, with the caveat that
+# "large caves" can be visited more than once--I'm not going to worry about
+# getting caught in loops between them (and if I have to change that in code, I
+# hope I remember to edit this comment). Since this is my year of pandas and
+# numpy, I am going to implement edges with a 2d numpy array (even though the
+# edge weights are simple--1 or 0--and symmetrical), and node information with
+# 1d numpy arrays.
+
+from typing import Tuple, List
+import numpy as np
+from utils import get_puzzle_input
+
+EXAMPLE_INPUT = \
+"""fs-end
+he-DX
+fs-he
+start-DX
+pj-DX
+end-zg
+zg-sl
+zg-pj
+pj-he
+RW-he
+fs-DX
+pj-RW
+zg-RW
+start-pj
+he-WI
+zg-he
+pj-fs
+start-RW
+"""
+
+def parse_input(input_string: str) -> Tuple[np.ndarray, np.ndarray]:
+ """Read the cave map, and return a tuple containing two arrays:
+ * A 1d array of node names (strings)
+ * A 2d array (number of nodes x number of nodes) to represent edges"""
+ # Read in the data and find the nodes and edges
+ node_set = set()
+ edge_list = []
+ for edge_string in input_string.rstrip('\n').split('\n'):
+ edge_nodes_set = set(edge_string.split('-'))
+ node_set.update(edge_nodes_set)
+ edge_list.append(edge_nodes_set)
+
+ # Create the numpy objects
+ node_names = np.array(list(node_set))
+ edges = np.zeros((node_names.size, node_names.size), dtype=int)
+
+ # Fill in the edges
+ # (Here's where we're punished for representing the data this way, other
+ # models would be much easier to parse)
+ for edge_nodes_set in edge_list:
+ n_1, n_2 = edge_nodes_set
+ edges[node_names == n_1, node_names == n_2] = 1
+ edges[node_names == n_2, node_names == n_1] = 1
+
+ return (node_names, edges)
+
+def is_visitable(node_names: np.ndarray, node_visits: np.ndarray) -> np.ndarray:
+ """Returns a boolean array indicating which nodes are still visitable
+ during search (defined as nodes associated with 'large' caverns or nodes
+ not yet visited)"""
+ return (node_visits == 0) | np.char.isupper(node_names)
+
+def update_visits(node_id: int, node_visits: np.ndarray) -> np.ndarray:
+ """Return a copy of the visit counts with the specified node marked as
+ visited again"""
+ node_visits_copy = node_visits.copy()
+ node_visits_copy[node_id] += 1
+ return node_visits_copy
+
+def traverse_node(node_id: int,
+ node_names: np.ndarray,
+ node_visits: np.ndarray,
+ edges: np.ndarray) -> List[Tuple[int, ...]]:
+ """Perform depth first search through the given node. Search terminates at
+ a node that cannot visit any neighbors or a node that's named 'end'.
+ Returns a list of paths, each path is a tuple of node IDs."""
+ # End of search when we hit 'end'
+ if node_names[node_id] == "end":
+ return [(node_id,)]
+
+ updated_node_visits = update_visits(node_id, node_visits)
+ visitable_nodes = (edges[node_id,] > 0) & is_visitable(node_names, updated_node_visits)
+
+ # Also end of search when (if) we hit somebody with no neighbors
+ if not visitable_nodes.any():
+ return[(node_id,)]
+
+ # Continue the search
+ paths = []
+ for neighbor_id in visitable_nodes.nonzero()[0]:
+ for path in traverse_node(neighbor_id, node_names, updated_node_visits, edges):
+ paths.append((node_id,) + path)
+ return paths
+
+def find_paths_start_to_end(node_names: np.ndarray,
+ edges: np.ndarray) -> List[Tuple[int, ...]]:
+ """Return a list of all paths from the node named 'start' to a node named
+ 'end' (paths are tuples of node IDs)"""
+ start_node = int((node_names == 'start').nonzero()[0][0])
+ end_node = int((node_names == 'end').nonzero()[0][0])
+ return [path for path in \
+ traverse_node(start_node,
+ node_names,
+ np.zeros(node_names.size, dtype=int),
+ edges) \
+ if path[-1] == end_node]
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return len(find_paths_start_to_end(*parse_input(input_string)))
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ assert solve_puzzle(EXAMPLE_INPUT) == 226
+ print("Number of routes from 'start' to 'end':",
+ solve_puzzle(get_puzzle_input(12)))
+
+if __name__ == "__main__":
+ main()
