Problem 82

p82.py

def compute():    
    matrix = [[131, 673, 234, 103,18],
              [201, 96, 342, 965, 150],
              [630, 803, 746, 422, 111],
              [537, 699, 497, 121, 956],
              [805, 732, 524, 37, 331]]
    
    rows = len(matrix)      #Number of rows
    columns = len(matrix[0])#Number of columns
    
    mask = [[0]*columns for i in range(rows)]
    #Create a mask of the matrix, where every entry is 0
    #We will use this mask to keep track of the minimum distance to each cell
    
    for x in range(rows):
        mask[x][0] = matrix[x][0]
    #In the mask we keep the first column the same because those are the starting values
        
    def mindistance(x,y): 
        #This function will find the minimum distance from every cell in the previous column
        #(except the cell directly to the left) to the currect cell (x,y)
        lengths = []
        up_curr = 0 #This will keep a running total of the matrix cells above the starting cell
        for up in range(x-1, -1, -1):
            #This will append the length of the cells up and to the left
            lengths.append(up_curr + matrix[up][y] + mask[up][y-1])
            up_curr += matrix[up][y] #Updated the down_curr
        
        down_curr = 0 #Same as above, except for going down the matrix
        for down in range(x+1, rows):
            lengths.append(down_curr + matrix[down][y] + mask[down][y-1])
            down_curr += matrix[down][y]
        return min(lengths) #We return the least value (shortest path)
            
    for y in range(1,columns): #We start at the second column, and go through the matrix
        for x in range(rows):
            #We want to to find the minimum path to the cell (x,y), it is either between the distance to
            #the cell to the left of it, or up or down + distance to the left + the value of the current cell
            #Note: up or down + distance to the left is exactly or function mindistance(x,y)
            mask[x][y] += (matrix[x][y] + min(mask[x][y-1], mindistance(x,y)))
    return min([mask[x][columns-1] for x in range(0, rows)])