[aoc/2021] Finish day 12

2 files changed, 39 insertions, 0 deletions

diff --git a/aoc/2021/12/part-one.py b/aoc/2021/12/part-one.py
new file mode 100644
index 0000000..7ab0e56
--- /dev/null
+++ b/aoc/2021/12/part-one.py
@@ -0,0 +1,19 @@
+from collections import defaultdict, deque
+from itertools import permutations
+from sys import stdin
+
+edges = defaultdict(list)
+for line in stdin.read().strip().split():
+    for key, value in permutations(line.split('-')):
+        if key != 'end' and value != 'start': edges[key].append(value)
+paths = set()
+queue = deque([('start',)])
+while queue:
+    if (head := queue.popleft()) in paths: continue
+    paths.add(head)
+    if (chin := head[-1]) == 'end': continue
+    for neck in edges[chin]:
+        if neck.islower() and neck in head: continue
+        top = head + (neck,)
+        queue.append(top)
+print(sum(path[-1] == 'end' for path in paths))
diff --git a/aoc/2021/12/part-two.py b/aoc/2021/12/part-two.py
new file mode 100644
index 0000000..7d87da7
--- /dev/null
+++ b/aoc/2021/12/part-two.py
@@ -0,0 +1,20 @@
+from collections import defaultdict, deque
+from itertools import groupby, permutations
+from sys import stdin
+
+edges = defaultdict(list)
+for line in stdin.read().strip().split():
+    for key, value in permutations(line.split('-')):
+        if key != 'end' and value != 'start': edges[key].append(value)
+paths = set()
+queue = deque([('start',)])
+while queue:
+    if (head := queue.popleft()) in paths: continue
+    paths.add(head)
+    if (chin := head[-1]) == 'end': continue
+    for neck in edges[chin]:
+        top = head + (neck,)
+        if sum(len(tuple(group)) - 1 for cave, group in groupby(sorted(top))
+               if cave.islower()) > 1: continue
+        queue.append(top)
+print(sum(path[-1] == 'end' for path in paths))