Home > Programming > Project euler problem 18 and 67

Project euler problem 18 and 67


Project euler problem 67 and 16 both are almost same. The only difference is that for the first problem the input is very small and for the 67th problem it is large. This problem is one another classic example of Dynamic programming.

Problem:

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 + 9 = 23.

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

Solution:

Just by looking at the problem we can quickly discern that it has optimal sub structure and overlapping sub problems. This gives an idea that we can use dynamic programming methodology.

Here is my code in Python.

apyr=[]
def pyr():
    with open("pyramid.txt", "r")as out:
        for i in out:
            apyr.append(i.split())

    for i in range(len(apyr) - 2, -1, -1):
        for j in range(len(apyr[i])):
            apyr[i][j] = str(int(apyr[i][j]) + max(int(apyr[i + 1][j]), int(apyr[i + 1][j + 1])))
    print apyr[0][0]

pyr()

Answer for problem 16: 1074

Answer for problem 67: 7273

real 0m0.195s
user 0m0.046s
sys 0m0.140s

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: