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.

# 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 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