diff options
author | Jack Sangdahl <[email protected]> | 2024-12-09 22:26:30 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-09 22:26:30 -0700 |
commit | f58fe1976f49eefc8d06b7806e00cfcde2647af4 (patch) | |
tree | 064652b51e05f2ea590964e817f0ca762a77ee4e /10_2024.py | |
parent | 9f021d6971920e37f250ea35c52324436aa1b428 (diff) | |
download | aoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.tar.gz aoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.zip |
Day 10 2024
Diffstat (limited to '10_2024.py')
-rw-r--r-- | 10_2024.py | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/10_2024.py b/10_2024.py new file mode 100644 index 0000000..081c07c --- /dev/null +++ b/10_2024.py @@ -0,0 +1,51 @@ +from collections import deque + +input = "data/10_2024.txt" +data = open(input).read().strip() +lines = data.split("\n") +lines = [[int(x) for x in row] for row in lines] +rows, cols = len(lines), len(lines[0]) +p1, p2, dp = 0, 0, {} + + +def ways0(sr, sc): + q = deque([(sr, sc)]) + res, vis = 0, set() + while q: + r, c = q.popleft() + if (r, c) in vis: + continue + vis.add((r, c)) + if lines[r][c] == 0: + res += 1 + for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]: + rr = r + dr + cc = c + dc + if 0 <= rr < rows and 0 <= cc < cols and lines[rr][cc] == lines[r][c] - 1: + q.append((rr, cc)) + return res + + +def ways1(r, c): + if lines[r][c] == 0: + return 1 + if (r, c) in dp: + return dp[(r, c)] + res = 0 + for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]: + rr = r + dr + cc = c + dc + if 0 <= rr < rows and 0 <= cc < cols and lines[rr][cc] == lines[r][c] - 1: + res += ways1(rr, cc) + dp[(r, c)] = res + return res + + +for r in range(rows): + for c in range(cols): + if lines[r][c] == 9: + p1 += ways0(r, c) + p2 += ways1(r, c) + +print(p1) +print(p2) |