Skip to main content

Problem 18 Project Euler Solution with python

Maximum path sum I

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
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

 As stated in the question, yes this problem has a clever way to solve. But it is very simple. The approach is dynamic programming.

 They both gave a very good explanation in a simple way. I will try my level best explaining the solution in my way. We are not going to consider the main problem, but the example problem for explanation.
Have a look at the following photograph:
Bottom Up Approach
Bottom Up Approach
Sorry for bad handwriting 😐.
I am not sure if we can call this approach bottom up approach, but I am using this term because it seemed relevant for me. Now let us understand the concept.
First I took the last but one row in the pyramid.
Now in the case of 2: we had option of 8 and 5. 8 has maximum value when compared to 5 and so the sum is 10.
Now for 4: 9 is better when compared to 5.
For 6: 9 is better when compared to 4.
Now the values are changed to 10(2+8), 13(4+9), 15(6+9)
Going one step further
considering 7: between 10 and 13, 13 is better.
For 4: between 13 and 15, 15 is better.
So the values change to 20(7+13), 19(4+15)
This is the final step. We have to choose between 20 and 19, in which 20 is better so the final solution will be 23.

 Now you may have a  doubt that why we have chosen bottom up approach when compared to top down approach. To explain this I will consider Jeffery Sax Answer on StackOverflow.
See the following photograph and the pyramid.
1
2 3
9 1 1
Top Down approach
Top Down approach
Now as you can see that if we follow path 1 then we get our maximum sum as 5, but if we follow path2 then we get the sum of 12. Which one do you think is maximum?

 If we were to solve this problem using bottom up approach, then we will get correct solution. See photograph if you want.
Bottom up approach solution for example 2
Bottom up approach solution for example 2
As you can see using bottom up approach we have arrived at the correct solution.
you can also apply this concept for reverse pyramid.
I have used Bottom Up approach to solve this problem. I have also counted the number of iterations in which we have arrived at the solution and compared it with the number of iterations one would take to arrive at the solution if we were to follow all the paths.
Compared to 16384 paths given in the question, my program only did 105 iterations and I have arrived at the solution. That means that using this approach I have eliminated 16279(99%) extra iterations. Also I have obtained the solution in a very small amount of run time.

 Okay, by now after reading till here, I am assuming that you have understood the algorithm. Lets get into the programming part.

Program

The program which I wrote is as follows:
The code is well commented again.
You can see the execution of the algorithm which I've discussed above from Line41 in the program.
If you want to download above program then you can download it from Github Gist pep18.py

Output

Summary

I think this problem had a little twist. When the problem was introduced in the question it was introduced in the form of top down approach, but the wise solution was to solve the problem using bottom up approach. Anyways we have solved the problem in less than 1% iterations given in the question. So we can call this program as optimized or framing it other way performance of the program is satisfactory 😉.

I hope you enjoyed reading solution for this problem. If you have any doubt or didn't understand anything then comment in the comment box below and I will be glad to help you.

Please don't hesitate to comment if you have found any typo or you have better/different solution.

You can also contact me if you want .

Thank you. Have a nice day.😀
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more