-
Notifications
You must be signed in to change notification settings - Fork 0
/
15-2.py
executable file
·65 lines (51 loc) · 1.88 KB
/
15-2.py
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
#!/usr/bin/env python
import heapq
import numpy
class Map:
def __init__(self, input):
tile_size = len(input)
self.size = tile_size * 5
self.map = numpy.zeros((self.size, self.size), dtype=numpy.uint)
self.risk = numpy.empty((self.size, self.size), dtype=numpy.uint)
self.risk.fill(pow(2, 32) - 1)
for row in range(len(input)):
for col in range(len(input)):
for x in range(5):
for y in range(5):
r = int(input[row][col]) + x + y
if r > 9:
r -= 9
self.map[row + tile_size * x, col + tile_size * y] = r
def find_risk(self):
self.risk[0, 0] = 0
queue = []
heapq.heappush(queue, (0, (0, 0)))
while len(queue) > 0:
risk, coords = heapq.heappop(queue)
x, y = coords
if risk > self.risk[x, y]:
continue
ns = [
[x + 1, y],
[x - 1, y],
[x, y + 1],
[x, y - 1]
]
neighbours = []
for n in ns:
if n[0] >= 0 and \
n[0] < self.size and \
n[1] >= 0 and \
n[1] < self.size:
neighbours.append((n[0], n[1]))
for v in neighbours:
alt = risk + self.map[v[0], v[1]]
if alt < self.risk[v[0], v[1]]:
self.risk[v[0], v[1]] = alt
heapq.heappush(queue, (self.risk[v[0], v[1]], (v[0], v[1])))
return self.risk[self.size - 1, self.size - 1]
def __str__(self):
return f"<{self.__class__.__name__}:\Size: {self.size}\n{self.map}\n>"
lines = [list(line.strip()) for line in open('15.input').readlines()]
map = Map(lines)
print(map.find_risk())