From e82eac08de8966e49ecc909c8a5e3593db7e158b Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <mcsinyx@disroot.org>
Date: Sun, 12 Dec 2021 15:59:41 +0700
Subject: [aoc/2021] Finish day 12

---
 aoc/2021/12/part-one.py | 19 +++++++++++++++++++
 aoc/2021/12/part-two.py | 20 ++++++++++++++++++++
 2 files changed, 39 insertions(+)
 create mode 100644 aoc/2021/12/part-one.py
 create mode 100644 aoc/2021/12/part-two.py

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))
-- 
cgit 1.4.1