Day 15 of the Advent of Code problem requires implementing a shortest path algorithm.

The input to this problem is a two dimensional array containing the level of risk in each cell. Our starting point is 0,0 and we have to navigate the submarine to w-1,h-1 whilst maintaining low risk. The submarine is only allowed moves into adjacent cells.

If we were to approach this problem as a directed graph

• Each cell in the array is a node
• Each node has an edge to the adjacent cell
• Each edge has risk as it's weight.
We can use Dijkstra's algorithm to find the path with the shortest path ie. lowest risk to the ending cell.

# Dijkstra's Algorithm

The section explaining my approach to Dijkstra's algorithm was extracted into a separate post here.

I implemented the following code that would determine the lowest risk from the starting point 0,0. At the end of the function's run, the lowest risk would be available in the ending cell.

```def dijkstras(w,h):

# Dijkstra's Algorithm
start = (0,0)
shortestDistFromStart = {start:0} # shortest distances from start to this position
visited = {}  # positions of all visited cells
prev = {}

#  priority queue initialized with the start and it's shortest distance
heap = []
heapq.heappush(heap,(0,start)) # !! important - distance is first in the tuple

while len(heap):

minVal,index = heapq.heappop(heap)
x,y = index

visited[index] = True

# get all adjacent neighors
neighbors =  [ (x+dx, y+dy) for dx,dy in [(0,-1),(-1,0),(0,1),(1,0)] ]
# that are not out of bounds
neighbors = [ (x,y) for x,y in neighbors if x >= 0 and x < w and y >= 0 and y < h]
# and not already visited
neighbors = [ neighbor for neighbor in neighbors if neighbor not in visited ]

if shortestDistFromStart[index] < minVal: continue

for neighbor in neighbors:

# calculate distance of this neighbor from start
nx,ny = neighbor
newDistance = shortestDistFromStart[index] + getRisk(nx,ny)
# if this new distance is better or not set, set it and put this neighbor ```
```            # on the queue
if neighbor not in shortestDistFromStart or\```
```                 newDistance < shortestDistFromStart[neighbor]:
shortestDistFromStart[neighbor] = newDistance
prev[neighbor] = index
heapq.heappush(heap,(newDistance,neighbor))

print(prev[(w-1,h-1)])
return shortestDistFromStart[(w-1,h-1)]
```

# Transposing Risk (Part B)

For Part B of this problem, the input is expanded. If you consider the original input as a single tile - this tile can be expanded 5 times to the right and 5 times down. If we know how "far" the tile is from the original tile, we can calculate the new risk by adding this distance to the original risk. The upper limit of risk is 9 and resets back to 1.

The following code determines -
• The original x,y given the transposed x,y.
• This will give use the original risk
• Distance (count) of the transposed tile from the original tile
• This will let use calculate the new risk. The risk resets past 9.
```def getRisk(x,y):

count = 0

#  transpose x back to the original data
while x > originalW-1:
x = x - (originalW - 1) - 1
count += 1

# transpose y back to the original data
while y > originalH-1:
y = y - (originalH - 1) - 1
count += 1

# get the original risk
risk = int(lines[y][x])

# increase risk
nrisk = risk + count
if nrisk > 9:
nrisk = nrisk % 9

return nrisk
```