Project Euler #18 In Python- Beginner

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 +

Solution 1:

Your approach is incorrect. You can't just do a greedy algorithm. Consider the example:

3
7 4
2 4 6
8 5 9 500

Clearly:

3 + 7 + 4 + 9 = 23 < 500 + (other terms here)

Yet you follow this algorithm.

However if the triangle were just:

3
7 4

The greedy approach works, in other words, we need to reduce the problem to a kind of "3 number" triangle. So, assume the path you follow gets to 6, what choice should be made? Go to 500. (What happens if the apath goes to 4? What about 2?)

How can we use these results to make a smaller triangle?

Solution 2:

It looks like you always choose the larger number (of left and right) in the next line (This is called a greedy algorithm.) But maybe choosing the smaller number first, you could choose larger numbers in the subsequent lines. (And indeed, by doing so, 1074 can be achieved.)

The hints in the comments are useful:

• A backtrack approach would give the correct result.

• A dynamic programming approach would give the correct result, and it's faster than the backtrack, thus it can work for problem 67 as well.

Solution 3:

Small remark on your code. The maximum sum in this triangle is indeed 1074. Your numbers are correct, just change your for-loop code from

    for i,cell in enumerate(line):
    newline.append(int(cell)+max(map(int,topline[max([0,i-1]):min([len(line),i+2])])))

to

    for i,cell in enumerate(line):
    newline.append(int(cell)+max(map(int,topline[max([0,i-1]):min([len(line),i+1])])))

(The "1" instead of "2")

Kindly

Solution 4:

You can reach each cell only from the adjacent (at most) three cells on the top line, and the most favorable will be the one with the highest number among these, you don't need to keep track of the others.

I put an example of the code. This works for the pyramid aligned to the left as in your question (the original problem is with a centered pyramid, but at least I don't completely spoil the problem). Max total for my case is 1116:

d="""
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""

ll=[line.split() for line in d.split('\n')][1:-1]
topline=ll[0]
for line in ll[1:]:
    newline=[]
    for i,cell inenumerate(line):
        newline.append(int(cell)+max(map(int,topline[max([0,i-1]):min([len(line),i+2])])))
    topline=newline
    print newline
print"final results is %i"%max(newline)

Solution 5:

I thought about this problem all day and night. Here is my solution:

# Maximum path sum I
import time
def e18():
    start = time.time()
    f=open("num_triangle.txt")
    summ=[75]
    for s in f:
        slst=s.split()
        lst=[int(item) for item in slst]
        for i in range(len(lst)):
            if i==0:
                lst[i]+=summ[i]
            elif i==len(lst)-1:
                lst[i]+=summ[i-1]
            elif (lst[i]+summ[i-1])>(lst[i]+summ[i]):
                lst[i]+=summ[i-1]
            else:
                lst[i]+=summ[i]
        summ=lst
    end = time.time() - start
    print("Runtime =", end)
    f.close()
    returnmax(summ)
print(e18()) #1074

P.S. num_triangle.txt is without first string '75'