Reputation: 17

Project Euler Problem 18: What mistake did I make in my code?

Given a triangle of integers, the problem is to find the maximum path sum from top to bottom (where all the numbers in the path must be adjacent).

I had an idea for an algorithm: starting at the very top, calculate the sum of the left and right paths (left all the way down, and right all the way down), if the left sum is greater, jump to the left-adjacent number, if the right sum is greater, jump to the right-adjacent number, repeat the algorithm starting from the current number, and so on until you get to the bottom row.

triangle = ['75', '9564', '174782', '18358710', '2004824765', '190123750334', '88027773076367', '9965042806167092', '414126568340807033', '41487233473237169429', '5371446525439152975114', '701133287773177839681757', '91715238171491435850272948', '6366046889536730731669874031', '046298272309709873933853600423']

maximumPath = [75]
maxSum = 75 #Start it with the starting element of the triangle.

def triNum(row, index): #Returns the number at given row, number in row
    return(int(triangle[row][2*index:2*(index+1)])) #Nota bene: returns an integer.

def options(row, index): #Rows start at 0, index starts at 0
    return(triNum(row+1, index), triNum(row+1, index+1))

def criticalPathSum(startRow, startIndex, direction):
    critPath = []
    if direction == 'left':
        directionNum = 0
    else:
        directionNum = 1
    sum = triNum(startRow, startIndex) #Starting sum of left and right paths is just the number at the start of both paths.
    for i in range(startRow + 1, len(triangle)):
        startIndex += directionNum
        sum += triNum(i, startIndex)
        critPath.append(triNum(i, startIndex))
        #print(triNum(i, startIndex + directionNum))
    return(sum, critPath)

pathIndex = 0
for row in range(0, len(triangle)-1):
    print('These are my options: ' + str(options(row, pathIndex)))
    print('Left Sum: ' + str(criticalPathSum(row, pathIndex, 'left')) + ', ' + 'Right Sum: ' + str(criticalPathSum(row, pathIndex, 'right')))
    if criticalPathSum(row, pathIndex, 'left') > criticalPathSum(row, pathIndex, 'right'):
        maximumPath.append(triNum(row + 1, pathIndex))
        print('Left. ' + str(triNum(row + 1, pathIndex)))
    else:
        print('Right. ' + str(triNum(row + 1, pathIndex + 1)))
        pathIndex += 1
        maximumPath.append(triNum(row + 1, pathIndex))
    maxSum += triNum(row + 1, pathIndex)
    print('_______________________________')
    print('\n')
print(maximumPath)
print(maxSum)

The answer is 1067, but I get 883. This is the maximum path, according to the algorithm:

[75, 95, 17, 35, 82, 75, 7, 16, 80, 37, 91, 17, 91, 67, 98].

Upvotes: 0

Answers (3)

Sigmatest

Reputation: 461

listOfLists = [
          [75],
          [95, 64],
          [17, 47, 82],
          [18, 35, 87, 10],
          [20, 4, 82, 47, 65],
          [19, 1, 23, 75, 3, 34],
          [88, 2, 77, 73, 7, 63, 67],
          [99, 65, 4, 28, 6, 16, 70, 92],
          [41, 41, 26, 56, 83, 40, 80, 70, 33],
          [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
          [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
          [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
          [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
          [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
          [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]


for i in range(len(listOfLists) - 2, -1, -1):
    for j in range(len(listOfLists[i])):
        listOfLists[i][j] += max(listOfLists[i+1][j], listOfLists[i+1][j+1])

print(listOfLists[0][0])

The bottom - top approach and it gets the right answer according to PE. Thanks!

Upvotes: 1

Prune

Reputation: 77837

This is one of the many wrong algorithms that the test data was designed to defeat. You chose what is called a "greedy" algorithm, one that takes the maximum value for any single step, without considering long-term characteristics of the problem.

Rather, you need to work from the bottom of the triangle upward. At each juncture, note which of the two paths gives the maximum sum to the bottom of the triangle, and record that as the optimum result from that node. When you hit the apex, you will have the desired answer as the larger of the two elements underneath.

For instance, given the triangle

your algorithm will be greedy and take the path 1-2-2-2; the lower choice of a 1 in row two cuts off that branch from the short-sighted logic.

Rather, you need to build up the totals from the bottom, taking the best of two paths at each node:

In case this isn't clear enough ... the bottom row has no further choices; each value is its own best path to the end. For the row above, let's go right to left, considering each value and its two "children":

 2 1 9
1 2 1 9

The 2 has two values below, 1 and 2. Obviously, the 2 is better, so the best path from there is 2+2 = 4. The 1 likewise has a 2 and 1 below; again, the better path is 1+2, giving 3. The 9 has children of 1 and 9; we choose 9+9=18. The rows now appear as

Now we move up one row, cosindering the two choices for 2 1 there. The 2 has 4 and 3; the 1 has 3 and 18. Again taking the higher value in each case and adding the node value, we get 2+4 = 6 and 1+18 = 19:

Finally, the top node chooses the larger value of 19, giving a total of 20 along the path 1-1-9-9.

Got it?

Upvotes: 1

lynn

Reputation: 10784

Your algorithm is wrong: in a triangle like

it is too tempted by the 9 (always going left) to see the optimal 1+4+4+4 = 13 route.

Upvotes: 2

Project Euler Problem 18: What mistake did I make in my code?

Answers (3)

Related Questions