initial commit

1 files changed, 32 insertions, 0 deletions

diff --git a/2021/day12/12b.py b/2021/day12/12b.py
new file mode 100644
index 0000000..149749e
--- /dev/null
+++ b/2021/day12/12b.py
@@ -0,0 +1,32 @@
+from collections import deque
+
+def parseInput(contents):
+    edges = [l.split("-") for l in contents.strip().split("\n")]
+    edges_set = set([])
+    for (f, t) in edges:
+        edges_set.add((f, t))
+        if t != "end" and f != "start":
+            edges_set.add((t, f))
+
+    return edges_set
+
+def visitableNeighbours(edges, path, doubleVisited):
+    curr = path[0]
+    banned = [e for e in path if e.islower()] if doubleVisited else ["start"]
+    for (f, t) in edges:
+        if f == curr and t not in banned:
+            yield t
+
+
+edges = parseInput(open("./input").read())
+
+locs = deque() # each element is a tuple of (double visited, list of all the visited nodes)
+finished = set()
+locs.append((False, ["start"]))
+while len(locs) > 0:
+    doubleVisited, path = locs.pop()
+    if path[0] == "end":
+        finished.add("-".join(path))
+    else:
+        for neighbour in visitableNeighbours(edges, path, doubleVisited):
+            locs.append((doubleVisited or (neighbour.islower() and neighbour in path), [neighbour] + path))