summaryrefslogtreecommitdiff
path: root/23_2023.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 /23_2023.py
downloadaoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz
aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip
intial
Diffstat (limited to '23_2023.py')
-rw-r--r--23_2023.py80
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))