Python algorithm to find total of some numbers

Question

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

tobias_k · Accepted Answer · 2014-07-29 18:57:32Z

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. ;-)

ojy · Accepted Answer · 2014-07-29 18:51:38Z

1

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.

edited Jul 29, 2014 at 18:51

answered Jul 29, 2014 at 18:40

ojy

2,4922 gold badges20 silver badges23 bronze badges

Collectives™ on Stack Overflow

Python algorithm to find total of some numbers

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related