+/AoC

advent of code

git clone https://git.julia.blue/+/AoC

Joseph RyanDay 1583f3271

master
1.6 KiB53 linesraw
1import heapq
2import sys
3
4grid = [[int(c) for c in line.strip()] for line in open("input").readlines()]
5h = len(grid)
6w = len(grid[0])
7inside = lambda x, y: 0 <= x < w and 0 <= y < h
8inside_big = lambda x, y: 0 <= x < w * 5 and 0 <= y < h * 5
9get_neighbors = lambda x, y, i: [
10    (x + a, y + b) for a, b in [(0, 1), (1, 0), (0, -1), (-1, 0)] if i(x + a, y + b)
11]
12pri = [(0, 0, 0)]
13best = [[sys.maxsize for _ in range(w)] for _ in range(h)]
14visited = [[False for _ in range(w)] for _ in range(h)]
15
16count = 0
17while len(pri) > 0:
18    cost, x, y = heapq.heappop(pri)
19    visited[y][x] = True
20    if (x, y) == (w - 1, h - 1):
21        print(cost)
22        break
23    for a, b in get_neighbors(x, y, inside):
24        if visited[b][a]:
25            continue
26        new = grid[b][a] + cost
27        if new < best[b][a]:
28            best[b][a] = new
29            heapq.heappush(pri, (new, a, b))
30
31pri = [(0, 0, 0)]
32best = [[sys.maxsize for _ in range(w * 5)] for _ in range(h * 5)]
33visited = [[False for _ in range(w * 5)] for _ in range(h * 5)]
34wrap = lambda x: x if x < 10 else x - 9
35
36while len(pri) > 0:
37    cost, x, y = heapq.heappop(pri)
38    visited[y][x] = True
39    if (x, y) == (w * 5 - 1, h * 5 - 1):
40        print(cost)
41        break
42    for a, b in get_neighbors(x, y, inside_big):
43        if visited[b][a]:
44            continue
45        new = wrap(grid[b % h][a % w] + a // w + b // h) + cost
46        if new < best[b][a]:
47            best[b][a] = new
48            heapq.heappush(pri, (new, a, b))
49
50# for y in range(h * 5):
51#     for x in range(w * 5):
52#         print(wrap(grid[y % h][x % w] + x // w + y // h), end="")
53#     print()