Project Euler problem 67 not quite correct...

Question

I have the following Python code, which I wrote for the sister problem 18.

It works perfectly for problem 18, but is slightly out for problem 67. I can't for the life of me figure out why.

triangle = [
[59],
[73, 41],
[52, 40, 9],
[26, 53, 6, 34],
[10, 51, 87, 86, 81],
[61, 95, 66, 57, 25, 68],
...
]

def max_adjacent(row,col):
    return max(triangle[row][col]+triangle[(row+1)][col], triangle[row][col]+triangle[(row+1)][(col+1)])

if __name__ == '__main__':
    row = len(triangle)-2
    while row >= 0:
        triangle[row] = [max_adjacent(row,triangle[row].index(i)) for i in triangle[row]]
        row -= 1
    print(triangle[0][0])

The algorithm is to start on the last-but-one row, and replace each number in this row with itself plus the largest adjacent number on the row below. (e.g., in the triangle partly defined above, 10 in the last but one row would be replaced with 105.) It simply loops this until it's at row 0 at the top of the triangle, and prints out the first element of this row, which is now the maximum sum.

This gives the answer of 7220, which I know to be close but wrong. I wonder why it works for problem 18 though?

Can anyone see what I'm assuming or doing wrong?

Answer 1

The problem might be that you're using the index function. If you have a number twice in a row, index will always give you the index of the number's first occurrence.

I guess Problem 18 has no duplicates within one row, the current problem has.