CODEWITHSUNDEEP
python
user428502
user428502

Reputation: 131

Project Euler problem 67 not quite correct

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?

Upvotes: 2

Views: 913

Answers (2)

anadir47
anadir47

Reputation: 31

This code might help. Done in java using concepts of DP

 public static int max(int a,int b)
{
    return a>=b?a:b;
}
public static int maxSumPath(int a[][],int cacher[][],int r,int k) 
{
    if(r==100)
        return 0;
    else if(cacher[r][k]!=0)
    {
        return cacher[r][k];
    }
    else
    {
        cacher[r][k] = cacher[r][k] + max(maxSumPath(a,cacher,r+1,k),maxSumPath(a,cacher,r+1,k+1)) + a[r][k];
        return cacher[r][k];
    }
}

Upvotes: 0

Johannes Charra
Johannes Charra

Reputation: 29913

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.

Upvotes: 4

Related Questions