about summary refs log tree commit diff
path: root/aoc
diff options
context:
space:
mode:
authorNguyễn Gia Phong <mcsinyx@disroot.org>2021-12-12 15:59:41 +0700
committerNguyễn Gia Phong <mcsinyx@disroot.org>2021-12-12 15:59:41 +0700
commite82eac08de8966e49ecc909c8a5e3593db7e158b (patch)
tree6faeae66df9d4404631307ae00b8246b102f8c87 /aoc
parentc1b6b94528efc48af820bda7c7557b95729c6af7 (diff)
downloadcp-e82eac08de8966e49ecc909c8a5e3593db7e158b.tar.gz
[aoc/2021] Finish day 12
Diffstat (limited to 'aoc')
-rw-r--r--aoc/2021/12/part-one.py19
-rw-r--r--aoc/2021/12/part-two.py20
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))