Chiton - Advent of Code 2021 Day 15

 

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