commit 0b4f3a240951151681ffb0a09e40a39c5961e9af (patch)
parent d19ba5af6e01d2cd8d38d1b0529aa35f282e9e2b
Author: Alex Karle <alex@alexkarle.com>
Date: Sun, 12 Dec 2021 00:46:29 -0500
day12: Add python solution
Def not optimized, and the DFS is kinda jank... but it works?
Diffstat:
5 files changed, 114 insertions(+), 0 deletions(-)
diff --git a/12/a.py b/12/a.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python3
+import sys
+import re
+from collections import defaultdict
+
+E = defaultdict(list)
+
+
+# Parse in edges
+for l in sys.stdin:
+ a, b = l.strip().split('-')
+ E[a].append(b)
+ E[b].append(a)
+
+smallre = re.compile('[a-z]+')
+def issmall(n):
+ return smallre.match(n)
+
+paths = 0
+def search(n, path):
+ global paths
+ if n == 'end':
+ paths += 1
+ return
+ if issmall(n) and n in path:
+ return
+ for c in E[n]:
+ search(c, path + n)
+
+search("start", "")
+
+print(paths)
diff --git a/12/b.py b/12/b.py
@@ -0,0 +1,38 @@
+#!/usr/bin/env python3
+import sys
+import re
+from collections import defaultdict
+
+E = defaultdict(list)
+
+
+# Parse in edges
+for l in sys.stdin:
+ a, b = l.strip().split('-')
+ E[a].append(b)
+ E[b].append(a)
+
+smallre = re.compile('[a-z]+')
+def issmall(n):
+ return smallre.match(n)
+
+paths = 0
+P = []
+def search(n, path, has_doubled):
+ global paths
+ global P
+ if n == 'end':
+ paths += 1
+ P.append(path + n)
+ return
+ if issmall(n) and n in path:
+ if has_doubled:
+ return
+ else:
+ has_doubled = True
+ for c in E[n]:
+ if c != 'start':
+ search(c, path + n, has_doubled)
+
+search("start", "", False)
+print(paths)
diff --git a/12/ex2 b/12/ex2
@@ -0,0 +1,7 @@
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/12/example b/12/example
@@ -0,0 +1,18 @@
+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
diff --git a/12/input b/12/input
@@ -0,0 +1,19 @@
+lg-GW
+pt-start
+pt-uq
+nx-lg
+ve-GW
+start-nx
+GW-start
+GW-nx
+pt-SM
+sx-GW
+lg-end
+nx-SM
+lg-SM
+pt-nx
+end-ve
+ve-SM
+TG-uq
+end-SM
+SM-uq
