Best path through a grid of point values

best_path.py

# Nathan Lehrer

def get_best_path(grid):
# Finds the best path through an M x N grid of point values, and that path's score
# Input: grid = grid of point values = M x N list of lists
# Returns: best_score = best possible score = int, path = best possible path = string
    M,N = len(grid),len(grid[0])
    scores = {(0,0):grid[0][0]} # best score for a path to each cell; score of (0,0) is grid value
    trace = {} # whether we optimally come from up ('U') or left ('L') into each cell
    
    # run dynamic programming algorithm to find best possible score, one diagonal at a time
    # in the first diagonal, the coordinates sum to 0, second, they sum to 1, etc.
    for coord_sum in range(1,M+N+1): # start with second diagonal
        for row in range(coord_sum+1):
            col = coord_sum-row
            if (row >= M) or (col >= N): # skip nonexistent coordinates
                continue
            cands = {'U':(row-1,col),'L':(row,col-1)} # candidates for where we come from
            for ul in ['U','L']: # remove impossible candidates
                if (min(cands[ul]) == -1):
                    del cands[ul]
            cand_scores = {ul:scores[cands[ul]] for ul in cands}
            best_cand = max(cand_scores, key=cand_scores.get) # this returns 'U' or 'L'
            scores[(row,col)] = grid[row][col] + cand_scores[best_cand]
            trace[(row,col)] = best_cand
    best_score = scores[M-1,N-1]

    # trace back to find best path
    pos = (M-1,N-1)
    path = ''
    while pos != (0,0):
        if trace[pos] == 'U':
            path = 'D'+path
            pos = (pos[0]-1,pos[1])
        else:
            path = 'R'+path
            pos = (pos[0],pos[1]-1)

    return best_score,path

sample_grid = \
[[0,5,0,8,1,8],
[3,6,1,3,6,3],
[9,5,7,9,1,1],
[8,7,9,4,8,3],
[7,8,7,6,2,5],
[3,4,0,5,0,4]]

sample_score,sample_path = get_best_path(sample_grid)
print 'Sample score: {0}, sample path: {1}'.format(sample_score,sample_path)