-
Notifications
You must be signed in to change notification settings - Fork 0
/
15-B.py
59 lines (43 loc) · 1.96 KB
/
15-B.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
import heapq
with open("15-input.txt") as file:
lines = [x.strip() for x in file.readlines()]
grid = [list(map(int,x)) for x in lines]
newgrid = []
for i in range(5):
for line in grid:
newline = []
for j in range(5):
for x in line:
cur = x + i + j
if cur > 9:
cur = cur -9
newline.append(cur)
newgrid.append(newline)
def get_path(grid):
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
rows = len(grid)
cols = len(grid[0])
#start top left, end bottom right and queue up starting location
start = (0, 0)
end = (rows - 1, cols - 1)
to_visit = [(0, start)]
visited = {start: 0}
heapq.heapify(to_visit) # transform to_visit to a heapqueue. this makes sure the queue is always ordered. Our priority queue
while to_visit:
current_prio, current_location = heapq.heappop(to_visit)
if current_location == end:
break #exit when we hit the end
row, col = current_location[0], current_location[1]
for xoffset, yoffset in dirs: # check adjacent nodes
new_row = row + xoffset
new_col = col + yoffset
if 0 <= new_row < rows and 0 <= new_col < cols: # make sure we dont go out of bounds.
weight = int(grid[new_row][new_col]) #weight is the integer in the grid
new_distance = visited[current_location] + weight # the updated distance to the current node
new_location = (new_row, new_col)
if (new_location in visited and new_distance < visited[new_location]) or new_location not in visited:
visited[new_location] = new_distance # add visited node or update it if shorter way has been found
heapq.heappush(to_visit, (new_distance, new_location)) #check the new node as well
return visited[end]
result = get_path(newgrid)
print(result)