1 """ Count number of paths through caves """
3 from collections import defaultdict
5 def walk_from_node(current_node, path_taken_so_far, visited_small_cave_twice=False):
7 for node in caves[current_node]:
11 possible_paths.append(path_taken_so_far + ["end"])
12 elif node == node.lower() and node in path_taken_so_far:
13 if not visited_small_cave_twice:
14 possible_paths += walk_from_node(node, path_taken_so_far + [current_node], True)
16 possible_paths += walk_from_node(node, path_taken_so_far + [current_node], visited_small_cave_twice)
20 caves = defaultdict(set)
22 with open("12_input.txt") as f:
24 node_a, node_b = line.strip().split("-")
26 caves[node_a].add(node_b)
27 caves[node_b].add(node_a)
29 walked_paths = walk_from_node("start", [])
30 print(len(walked_paths))