diff options
author | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
commit | 8e313e2614c7a0fe5af924febdbacc650e33835e (patch) | |
tree | 63426b6942ceebe17708140c972a7d7451bd2f74 /10_2020.py | |
download | aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip |
intial
Diffstat (limited to '10_2020.py')
-rw-r--r-- | 10_2020.py | 43 |
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)) |