I am trying to solve problem 18 in project Euler. See here, https://projecteuler.net/problem=18.
def maxpath(triangle):
p = 0
total = 0
for x in range(0,len(triangle)):
if p + 1 < len(triangle[x]) - 1:
if triangle[x][p+1] > triangle[x][p]:
p += 1
total += triangle[x][p]
return total
Given a 2-Dimensional list, it will find the maximum route from top of the triangle to the bottom. Can somebody please explain what's wrong with this code?
Everything checks out except for this line:
if p + 1 < len(triangle[x]) - 1:
There are actually two issues here. The first one is that it should be p instead of p + 1. Thinking about it, p's current value carries over from the previous row, for any row after the first. So p + 1 is guaranteed to be well defined. Actually, you could just start your total from 1, iterating from the second row onwards, and you wouldn't even need to have that condition.
The second issue is minor, but you don't need to compute the length each time. The length of a row is always equal to it's 0-index plus one, so just compare with x instead.
This is what your code looks like after fixing:
def maxpath(triangle):
p = 0
total = 0
for x in range(len(triangle)):
if p < x and (triangle[x][p + 1] > triangle[x][p]):
p += 1
total += triangle[x][p]
return total
And now,
maxpath([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) # Euler website example
Produces
23
If you want to optimise it even further (removing the x < p check, you can do this:
def maxpath(triangle):
p = 0
total = triangle[0][0]
for x in range(1, len(triangle)):
if triangle[x][p + 1] > triangle[x][p]:
... # the rest stays the same