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 /23_2023.py | |
download | aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip |
intial
Diffstat (limited to '23_2023.py')
-rw-r--r-- | 23_2023.py | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/23_2023.py b/23_2023.py new file mode 100644 index 0000000..8607554 --- /dev/null +++ b/23_2023.py @@ -0,0 +1,80 @@ +import sys +import re +from copy import deepcopy +from math import gcd +from collections import defaultdict, Counter, deque +import heapq +import math + +D = open(sys.argv[1]).read().strip() +L = D.split("\n") +G = [[c for c in row] for row in L] +R = len(G) +C = len(G[0]) + +sys.setrecursionlimit(10**6) + + +def solve(part1): + V = set() + for r in range(R): + for c in range(C): + nbr = 0 + for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]: + if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#": + nbr += 1 + if nbr > 2 and G[r][c] != "#": + V.add((r, c)) + + for c in range(C): + if G[0][c] == ".": + V.add((0, c)) + start = (0, c) + if G[R - 1][c] == ".": + V.add((R - 1, c)) + end = (R - 1, c) + + E = {} + for rv, cv in V: + E[(rv, cv)] = [] + Q = deque([(rv, cv, 0)]) + SEEN = set() + while Q: + r, c, d = Q.popleft() + if (r, c) in SEEN: + continue + SEEN.add((r, c)) + if (r, c) in V and (r, c) != (rv, cv): + E[(rv, cv)].append(((r, c), d)) + continue + for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]: + if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#": + if part1 and G[r][c] in ["<", ">", "^", "v"] and G[r][c] != ch: + continue + Q.append((r + dr, c + dc, d + 1)) + + count = 0 + ans = 0 + SEEN = [[False for _ in range(C)] for _ in range(R)] + seen = set() + + def dfs(v, d): + nonlocal count + nonlocal ans + count += 1 + r, c = v + if SEEN[r][c]: + return + SEEN[r][c] = True + if r == R - 1: + ans = max(ans, d) + for y, yd in E[v]: + dfs(y, d + yd) + SEEN[r][c] = False + + dfs(start, 0) + return ans + + +print(solve(True)) +print(solve(False)) |