Problem #83 is a more complex version of Problems #81 and #82. The question reads:
Project Euler Problem 83: Path sum: four ways In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. 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 moving left, right, up, and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
Unlike my solution for Problem #82, I could not find a way to simply alter my solution for Problem #81 to solve this problem. Thus, my solution for this problem is quite bad, and I am unsure whether it will always be able to find the minimum path. Here’s my solution:
Solution #1: Arbitrary Checking Approach
We can observe that even when all four directions are allowed, the minimum path cannot pass through more than n*(n+1)/2 cells (in the case where the path passes through every other complete row or column). Thus, the minimum path sum to every cell can be initially estimated as the path which moves along the top row until it reaches the column in question and then moves down the column. Then, the minimum path for each cell can be updated n*(n+1)/2 times to account for every other possible minimum path. After this is done, the minimum path to the bottom right corner should be correct. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #83
'''
import time
f = open("PE83Grid.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 projectEulerProblemEightyThree(realContents):
row = len(realContents)
col = len(realContents[0])
new = []
rowTotal = 0
for r in range(row):
myRow = []
colTotal = rowTotal
a = realContents[r]
rowTotal+=a[0]
for x in a:
colTotal+=x
myRow.append(colTotal)
new.append(myRow)
for _ in range((row+col)):
for r in range(row):
for c in range(col):
minPos = new[r][c]
v = realContents[r][c]
if(r>0):
minPos = min(minPos,v+new[r-1][c])
if(r<row-1):
minPos = min(minPos,v+new[r+1][c])
if(c>0):
minPos = min(minPos,v+new[r][c-1])
if(c<col-1):
minPos = min(minPos,v+new[r][c+1])
new[r][c] = minPos
return new[row-1][col-1]
start = time.time()
print projectEulerProblemEightyThree(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
425185
--- 0.708230018616 seconds ---
for input of given grid.
'''
And with that, we’re done! To speed up my code, I only updated the minimum paths 2*n times instead of n*(n+1)/2 times. Thus, this code will not find the minimum path for any grid, but for grids with normally shaped minimum paths, it should find the minimum path. Even with this risky optimization, my solution took over half a second to run. I definitely want to return to this question eventually to look for a more efficient solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 