12_1.py

   1 """ Count number of paths through caves """
   2 from collections import defaultdict
   3
   4 def walk_from_node(current_node, path_taken_so_far):
   5     possible_paths = []
   6     for node in caves[current_node]:
   7         if node == "end":
   8             possible_paths.append(path_taken_so_far + ["end"])
   9         elif node == node.lower() and node in path_taken_so_far:
  10             pass
  11         else:
  12             possible_paths += walk_from_node(node, path_taken_so_far + [current_node])
  13
  14     return possible_paths
  15
  16 caves = defaultdict(set)
  17
  18 with open("12_input.txt") as f:
  19     for line in f:
  20         node_a, node_b = line.strip().split("-")
  21
  22         caves[node_a].add(node_b)
  23         caves[node_b].add(node_a)
  24
  25 walked_paths = walk_from_node("start", [])
  26 print(len(walked_paths))
  27
  28 filtered_walked_paths = [path for path in walked_paths if path[-1] == "end"]
  29 print(len(filtered_walked_paths))