Problem #81 concerns finding the minimum weighted path along the rows and columns of a grid. The question reads:
Project Euler Problem 81: Path sum: two ways In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427. 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 top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
This is another great example of the powers of dynamic programming. Here is my solution:
Solution #1: Dynamic Programming Approach
We can simply observe that the minimum path sum from the top left corner to any given cell is the value of the cell plus the minimum of the path sum to the cell above it and the path sum to the cell to the left of it. Branching off from the top left corner and using this observation, the minimum path sum to each cell can be generated dynamically. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #81
'''
import time
f = open("PE81Grid.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 projectEulerProblemEightyOne(myGrid):
firstRow = []
total = 0
for x in myGrid[0]:
total+=x
firstRow.append(total)
newGrid = [firstRow]
for c in range(1,len(myGrid)):
newRow = [myGrid[c][0]+newGrid[c-1][0]]
for x in range(1,len(myGrid[c])):
v = myGrid[c][x]+min(newGrid[c-1][x],newRow[x-1])
newRow.append(v)
newGrid.append(newRow)
return newGrid[len(myGrid)-1][len(myGrid[0])-1]
start = time.time()
print projectEulerProblemEightyOne(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
427337
--- 0.00197601318359 seconds ---
for input of given grid.
'''
And with that, we’re done. An 80×80 grid can be searched in just over a millisecond in Python 2.7 with Dynamic Programming.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 