summaryrefslogtreecommitdiff
path: root/10_2020.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-06-15 22:20:32 -0600
committerJack Sangdahl <[email protected]>2024-06-15 22:20:32 -0600
commit8e313e2614c7a0fe5af924febdbacc650e33835e (patch)
tree63426b6942ceebe17708140c972a7d7451bd2f74 /10_2020.py
downloadaoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz
aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip
intial
Diffstat (limited to '10_2020.py')
-rw-r--r--10_2020.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/10_2020.py b/10_2020.py
new file mode 100644
index 0000000..211f2ba
--- /dev/null
+++ b/10_2020.py
@@ -0,0 +1,43 @@
+import fileinput
+import re
+
+p1 = 0
+p2 = 0
+
+xs = [int(x) for x in list(fileinput.input())]
+xs.append(0)
+xs = sorted(xs)
+xs.append(max(xs) + 3)
+n1 = 0
+n3 = 0
+for i in range(len(xs) - 1):
+ d = xs[i + 1] - xs[i]
+ if d == 1:
+ n1 += 1
+ elif d == 3:
+ n3 += 1
+
+# dynamic programming
+DP = {}
+
+
+# dp(i) = the number of ways to complete the adapter chain given
+# that you are currently at adapter xs[i]
+def dp(i):
+ if i == len(xs) - 1:
+ return 1
+ if i in DP:
+ return DP[i]
+ ans = 0
+ for j in range(i + 1, len(xs)):
+ if xs[j] - xs[i] <= 3:
+ # one way to get from i to the end is to first step to j
+ # the number of paths from i that *start* by stepping to xs[j] is just DP[j]
+ # So dp(i) = \sum_{valid j} dp(j)
+ ans += dp(j)
+ DP[i] = ans
+ return ans
+
+
+print(n1 * n3)
+print(dp(0))