1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
import heapq
grid = [[int(x) for x in l] for l in open("./input").read().strip().split("\n")]
GRID_SIZE_X = len(grid)
GRID_SIZE_Y = len(grid[0])
def in_bounds(c, tiles):
x, y = c
return x >= 0 and y >= 0 and y < (GRID_SIZE_Y * tiles) and x < (GRID_SIZE_X * tiles)
def next_steps(path, tiles):
sx, sy = path[0]
for c in [(sx + 1, sy), (sx - 1, sy), (sx, sy + 1), (sx, sy - 1)]:
if c not in path and in_bounds(c, tiles):
yield c
def step_path(path, tiles):
for c in next_steps(path, tiles):
yield [c] + path
def risk_for(x, y):
tile_x = x // GRID_SIZE_X
tile_y = y // GRID_SIZE_Y
delta = tile_x + tile_y
risk = grid[y % GRID_SIZE_Y][x % GRID_SIZE_X] + delta
while risk > 9:
risk -= 9
return risk
def total_risk(path):
acc = 0
for x, y in path:
if (x, y) == (0, 0):
continue
risk = risk_for(x, y)
acc += risk
return acc
def manhattan(a, b):
dx = abs(a[0] - b[0])
dy = abs(a[1] - b[1])
return dx + dy
def heuristic(path, dst):
return total_risk(path) - manhattan(path[0], dst)
class HeapItem:
def __init__(self, heur, path):
self.heur = heur
self.path = path
def __lt__(self, other):
return self.heur < other.heur
def find_path(start, tiles):
q = []
max_x = (GRID_SIZE_X * tiles) - 1
max_y = (GRID_SIZE_Y * tiles) - 1
dst = (max_x, max_y)
visited = set()
heapq.heappush(q, HeapItem(0, [start]))
while True:
i = heapq.heappop(q)
heur = i.heur
path = i.path
if path[0] == (max_x, max_y):
return path
if path[0] in visited:
continue
visited.add(path[0])
for new in step_path(path, tiles):
loc = new[0]
heapq.heappush(q, HeapItem(heur + risk_for(loc[0], loc[1]), new))
path = find_path((0, 0), 5)
print(path)
print(total_risk(path))
|
