adventofcode2021/12_1.py at master · glovekyl/adventofcode2021 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
from utils import *

lines = read_lines(day=12)

example_small = ( # 10 paths
  "start-A",
  "start-b",
  "A-c",
  "A-b",
  "b-d",
  "A-end",
  "b-end"
)

example_med = ( # 19 paths
  "dc-end",
  "HN-start",
  "start-kj",
  "dc-start",
  "dc-HN",
  "LN-dc",
  "HN-end",
  "kj-sa",
  "kj-HN",
  "kj-dc",
)

example_large = ( # 226 paths
  "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"
)

class NodeObject(object):
  pass

class Node(NodeObject):
  def __init__(self, key: str):
    super().__init__()
    self._key = key
    self._edges: list[NodeObject] = []
    self._visited_count = 0

  def __repr__(self) -> str:
    return self.key

  def __str__(self) -> str:
    return "{}: {}".format(self.key, [e.key for e in self._edges])

  def add_edge(self, node: object) -> list[NodeObject]:
    self._edges.append(node)
    return self.edges

  @property
  def key(self) -> str:
    return self._key

  @property
  def edges(self) -> list[NodeObject]:
    return self._edges

  @property
  def count(self) -> int:
    return self._visited_count

  @count.setter
  def count(self, i) -> int:
    self._visited_count = i
    return self._visited_count

def dfs(known: list[str], node: Node, visited: set[Node]=set(), path: list=list()):
  if node.key == 'end':
    known.append(','.join(path + ['end',]))
    return

  if node not in visited:
    path.append(node.key)
    if node.key.islower():
      visited.add(node)
    for edge in node.edges:
      dfs(known, edge, visited.copy(), path.copy())

def main(data):
  data = tuple(line.split('-') for line in data)

  cave: dict[str: Node] = dict()
  for a, b in data:
    if a not in cave: cave[a] = Node(a)
    if b not in cave: cave[b] = Node(b)
    a: Node = cave[a]
    b: Node = cave[b]
    a.add_edge(b)
    b.add_edge(a)

  dfs(paths := [], cave['start'])
  print(len(paths))

if __name__ == "__main__":
  main(lines) # answer: 3410