Project Euler 82 – Find the minimal path sum from the left column to the right column

http://projecteuler.net/problem=82

I’m looking forward to reading the forums in Euler for this one, as I’m curious to find a more elegant way to solve this problem…

# euler 82

f = open('matrix.txt', 'r')

# grid is a dictionary with key as tuple (i,j) and value as value of node
# i is row, j is column of grid
grid = {}
counter = 1
for line in f:
   temp = line.replace('\n','')
   temp = temp.split(',')
   for a in range(len(temp)):
       grid[(counter,a+1)] = int(temp[a])
   counter += 1

rows = 80
cols = 80

minGrid = {}
# first column of min grid is just the value of the node
for i in range(1,rows+1):
    minGrid[(i,1)] = grid[(i,1)]

def compare(location):  # takes a node (i,j) returns cheapest way to get there
    i, j = location[0], location[1]
    lookleft = minGrid[(i,j-1)]
    upSum = 0
    cellsUp = 0
    maxUp = i-1 #this is the max number of cells up to check
    while cellsUp < maxUp:
        cellsUp += 1
        upSum += grid[(i-cellsUp, j)]
        if upSum > lookleft:   #going up is too expensive
            cellsUp -= 1
            break
    downSum = 0
    cellsDown = 0
    maxDown = rows - i
    while cellsDown < maxDown:  #checking cells down
        cellsDown += 1
        downSum += grid[(i+cellsDown, j)]
        if downSum > lookleft:
            cellsDown -= 1
            break
    upMemo = {0:0}
    upMin = []
    downMemo = {0:0}
    downMin = []
    if cellsUp > 0:
        for cu in range(1, cellsUp+1):
            upMemo[cu] = upMemo[cu-1] + grid[(i-cu,j)]
            upMin.append(upMemo[cu] + minGrid[(i-cu, j-1)])
    if cellsDown > 0:
        for cd in range(1, cellsDown+1):
            downMemo[cd] = downMemo[cd-1] + grid[(i+cd,j)]
            downMin.append(downMemo[cd] + minGrid[(i+cd, j-1)])
    bigList = [lookleft]
    for a in upMin:
        bigList.append(a)
    for b in downMin:
        bigList.append(b)
    lowest = min(bigList)
    return grid[(i,j)] + lowest

for c in range(2, cols+1):
    for d in range(1, rows+1):
        minGrid[(d,c)] = compare((d,c))

cheapestList = []
for a in range(1, rows+1):
    cheapestList.append(minGrid[(a,cols)])

print "Cheapest path is ", min(cheapestList)