CODEWITHSUNDEEP
pythonpython-2.7
chamathabeysinghe
chamathabeysinghe

Reputation: 868

Python algorithm to find total of some numbers

By starting at the top of the triangle below and moving to adjacent numbers on the row below, find the maximum total from top to bottom of the triangle below.

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

This is Project Euler, Problem 18.

I got an answer as 1064. But they say it is wrong. Help me...in python 2.7

This is my code:

s='''Here the sequence'''
s=s.split("\n")
value=0
total=0
for x in range(len(s)):
    y=s[x].split()
    if (value+1)>x:
        total+=int(y[value])
        print int(y[value])
    else:
        if int(y[value])>int(y[value+1]):
            total+=int(y[value])
            print int(y[value])
        else: 
            total+=int(y[value+1])
            print int(y[value+1])
            value+=1
print "Total:::%d"%total

Upvotes: 1

Views: 257

Answers (2)

tobias_k
tobias_k

Reputation: 82889

The problem with your algorithm is that you only explore a single path through the triangle: At each "junction", you always select the higher value and proceed down that path. But this "greedy" algorithm does not always work. Consider this example:

    1          Yours:    (1)           Best:   (1)
  1   2                 1  (2)               (1)  2
9   1   1             9  (1)  1            (9)  1   1

When presented with the choice of 1 or 2, you select 2 and go down the right path, missing out the 9. Instead, you have to consider all the paths. You can do this in a "dynamic programming" kind of fashion, where you store the highest-possible value that can be reached in each cell and then just add them up. You can do this top-down or bottom-up, and then just select the highest value in the final row.

Example (bottom-up): In each step, add the maximum of the two adjacent lower cells to the cell above.

   5               5               5             5            5   ==> 5+17 
  2 4            2   4           2   4   ==> 2+11 4+13  ==> 13 17
 3 5 7   ==>  3+5 5+6 7+6  ==> 8  11  13
1 5 6 2

Implementing this idea in an algorithm is left as an excercise to the reader. ;-)

Upvotes: 2

ojy
ojy

Reputation: 2482

You have a greedy algorithm, which appends the largest adjacent number at every iteration. It produces a suboptimal solution. Simple explanation - consider just a triangle that consists of three top rows. Your solution will be 75 + 95 + 47 = 217. While the optimal solution in this case is 75 + 64 + 82 = 221. How to solve this? I would recommend designing a dynamic programming algorithm.

Upvotes: 1

Related Questions