From 5c91260838a45f4a422fae26aa040420a2770c62 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 16 Dec 2024 02:08:12 -0700 Subject: Day 16 2024 --- 16_2024.py | 79 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) create mode 100644 16_2024.py (limited to '16_2024.py') diff --git a/16_2024.py b/16_2024.py new file mode 100644 index 0000000..2ae5fbe --- /dev/null +++ b/16_2024.py @@ -0,0 +1,79 @@ +import heapq + +input = "data/16_2024.txt" +data = open(input).read().strip() +lines = data.split("\n") +rows = len(lines) +cols = len(lines[0]) +lines = [[lines[r][c] for c in range(cols)] for r in range(rows)] +dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] + + +for r in range(rows): + for c in range(cols): + if lines[r][c] == "S": + sr, sc = r, c + if lines[r][c] == "E": + er, ec = r, c + + +q = [] +vis = set() +heapq.heappush(q, (0, sr, sc, 1)) +dist = {} +best = None +while q: + d, r, c, dir = heapq.heappop(q) + if (r, c, dir) not in dist: + dist[(r, c, dir)] = d + if r == er and c == ec and best is None: + best = d + if (r, c, dir) in vis: + continue + vis.add((r, c, dir)) + dr, dc = dirs[dir] + rr, cc = r + dr, c + dc + if 0 <= cc < cols and 0 <= rr < rows and lines[rr][cc] != "#": + heapq.heappush(q, (d + 1, rr, cc, dir)) + heapq.heappush(q, (d + 1000, r, c, (dir + 1) % 4)) + heapq.heappush(q, (d + 1000, r, c, (dir + 3) % 4)) + + +print(best) + + +q = [] +vis = set() +dist2 = {} +for dir in range(4): + heapq.heappush(q, (0, er, ec, dir)) + + +while q: + d, r, c, dir = heapq.heappop(q) + if (r, c, dir) not in dist2: + dist2[(r, c, dir)] = d + if (r, c, dir) in vis: + continue + vis.add((r, c, dir)) + dr, dc = dirs[(dir + 2) % 4] + rr, cc = r + dr, c + dc + if 0 <= cc < cols and 0 <= rr < rows and lines[rr][cc] != "#": + heapq.heappush(q, (d + 1, rr, cc, dir)) + heapq.heappush(q, (d + 1000, r, c, (dir + 1) % 4)) + heapq.heappush(q, (d + 1000, r, c, (dir + 3) % 4)) + + +valid = set() +for r in range(rows): + for c in range(cols): + for dir in range(4): + if ( + (r, c, dir) in dist + and (r, c, dir) in dist2 + and dist[(r, c, dir)] + dist2[(r, c, dir)] == best + ): + valid.add((r, c)) + + +print(len(valid)) -- cgit v1.2.3