Problem #82 is a more complex version of Problem #81. The question reads:
Project Euler Problem 82: Path sum: three ways The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994. 131 673 234 103 018 201 096 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 037 331 Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
As mentioned above, this problem is very similar to Problem 81. The only difference is that in this case, the path can start anywhere on the left edge and it can move up. These changes do not require the solution to be significantly different, so my solution for this problem is similar to my solution for Problem 81. Here’s my solution:
Solution #1: Dynamic Approach
We simply go from left to right across the grid, finding the minimum path sum to each cell one column at a time. The first column can be found by simply storing the first column of the given grid. Each successive column can be calculated by iterating through the previous column and finding the minimum path sum from each cell in the previous column to each cell in the next column. By this method, the minimum path to each column can be generated dynamically. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #82
'''
import time
f = open("PE82Grid.txt","r")
if(f.mode == "r"):
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(map(int,x.split(",")))
else:
raise ValueError("Cannot read from file")
def projectEulerProblemEightyTwo(myGrid):
newGrid = []
rows = len(myGrid)
cols = len(myGrid[0])
for x in range(rows):
newGrid.append([myGrid[x][0]])
for y in range(1,cols):
theColumn = []
for x in range(rows):
theColumn.append(myGrid[x][y])
forwardPartials = [0]
t = 0
for x in theColumn:
t+=x
forwardPartials.append(t)
backwardPartials = [t]
for x in range(rows-1,-1,-1):
t-=theColumn[x]
backwardPartials.append(t)
newColumn = []
for z in range(rows):
minFound = newGrid[z][y-1]+myGrid[z][y]
for a in range(rows):
if(a<z):
total = myGrid[z][y] + forwardPartials[z]-forwardPartials[a] + newGrid[a][y-1]
elif(a>z):
total = myGrid[z][y] + forwardPartials[a+1] - forwardPartials[z+1] + newGrid[a][y-1]
else:
total = minFound
if(total<minFound):
minFound = total
newColumn.append(minFound)
for x in range(rows):
newGrid[x].append(newColumn[x])
minFound = newGrid[0][cols-1]
for a in range(1,rows):
v = newGrid[a][cols-1]
if(v<minFound):
minFound = v
return minFound
start = time.time()
print projectEulerProblemEightyTwo(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
260324
--- 0.0795319080353 seconds ---
for input of given grid.
'''
And with that, we’re done. This solution still managed to run in under a tenth of a second, but it still took over an order of magnitude longer than the solution for Problem #81. I may come back to this problem to look for a more efficient implementation.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 