Daily Coding Problem Hello everyone and welcome back with another problem to solve! Today we’ll be dealing with paths, calculating the greatest path in a triangle of numbers starting from the top to the bottom! Today’s problem comes from the archives of : a super cool website to look at if you are in the mood for some head scratching! There are more than 800 math and coding problems to solve and a vast archive of discussions about them. It is the perfect tool to train your math skills and learn something new. Go check it out and try to solve your challenges too! ProjectEuler.net Let’s jump to the action! The 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. That is,3+7+4+9=23. Find the maximum total from top to bottom of the triangle below: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, , is the same challenge with a triangle containing one hundred rows; it cannot be solved by brute force, and requires a clever method! ;o) NOTE: Problem 67 So, to recap a bit: we are given a triangle with numbers. Each number is connected to the two directly below it, . What we need to do is go from top to bottom and find the maximum possible path value. The sum of its values will be our answer. Also, as the problem states, since the routes are limited, we could try the solution out from calculating every possible route. As we’ll see just in a moment, , so we should scrap our heads a bit and find a better solution. forming a path directly to solve it by brute-forcing that would not be an efficient solution Ready then? Let’s solve it! Brute forcing the solution Since the problem advises that the brute force solution is not an efficient one, let’s take a moment to understand why is by looking at some smaller triangles. To know which path is the most valuable one, we first need to . It would be nice to know how many of them there are in the first place. walk over all the possible paths So, let’s try to count them: When there is one row (just one element) we have only one possible path. With two rows there are two possible paths we can take, with three rows there are 4 paths, and so on. Hopefully, you can see what’s happening here: : so for instance, with 4 rows we have 2³ = 8. In the problem’s example, the triangles have 15 rows so we count 2¹⁴ possible paths, which are 16384 possible routes, just as the problem states. the number of paths grows like 2ⁿ⁻¹ Given this, to calculate the maximum path by brute force, we would need to calculate the value of all the 16384 routes and then compare them. Besides the hassle of calculating all those possible paths, for the next similar problem mentioned by the text, which has 100 lines, we are going to have 2⁹⁹ possible paths, meaning roughly a total of 63.382.530.010.000.000.000.000.000.000 possible routes: inconvenient to say the least. Finally, , which is one of the worst results we could hope for. brute forcing the solution would force us with an algorithm with a time complexity of O(2ⁿ) We need a better method. The better method As we saw, the main problem in brute-forcing the solution is that there are so too many steps that our algorithm should do to calculate them all. . Since the number of routes depends on the number of elements in the triangle, we have no control over that variable. way too many possible routes, A better solution should involve either fewer routes or fewer steps to calculate them So, s needed for the algorithm to complete. What if we could calculate the maximum path possible of every given triangle … with just one step? our only chance is to reduce the number of step Let’s take a triangle and reason about it. This is the triangle from the sample given by the problem, for which we already know that the maximum path is 23 (the one in red), or 3 + 7 +4 + 9. This is our first hint: This means that we could track the growing value of each path while we go down the triangle and choose the maximum at the end. We can do this by . we don’t need intermediate values, we just want the sum of them. updating intermediate numbers with their actual path value As you can see we can apply this process row by row, updating all the values until, in the last row, we obtain the exact solution: 23. This is why I called it the avalanche algorithm: ! it’s like a snowball rolling down the mountain, which takes the route with the most snow on it and collects it to grow and grow again We have a problem though: for certain values inside the triangle we obtain multiple values. Take the middle 4, for example, the one in the third line of the first graph. If we come to the 4 from the 10 we are going to get 14 as a result, but if we come from the 7 we are going to obtain 11. If we think about it though, 10 and 7 in the second row are already “path values” updated from the previous row, since we’ve done 3+7=10 and 3+4=7 to get them. This means that the path coming from the 10 has already a higher value than the one coming from the 7 and, since we jump on the 4 only from those two values and from 4 we can only go to 5 and 9, we can conclude that the 10 path has an higher value than the 7 one, at least up to that point, and then we will always choose the route coming from the 10. It’s much clearer if you look it like this: Since we are coming only from 10 and 5, no matter if we are going to 5 or 9, we will always choose the path that already has a value of 10 because it’s higher than the one with a value of 7. This is our second hint: We could also store it, as we’ll do if we want to take the inverse road and print out the final path. besides adding the “path value” row by row and number by number, for each number we can choose the highest previous path value and move on. Each element in the triangle will have two values then: its real value and an “updated value” to keep track of the path value up to that point. OK: we have everything we need to start coding then. Let’s jump to the code! The code As with every good coder out there, I learned during the years to innately hate . Given this though, I feel like that for this project a solid OOP language was needed, to wrap everything up in a clear form. Go, even if is by far my first choice on almost every project, was not that suitable for this kind of task: its lack of a proper class object would have been a pain to deal with. Python is similar, since it has classes but it becomes messy to work with them after a while, in my opinion at least. , which is sold as Java 2.0: much less boilerplate but the same code potential for its interoperability with Java code. If you never used it, you’ll love it in a moment. Java So for this problem, we are going for Kotlin Also, this solution requires building a : if you are not familiar with that kind of data structure go check some resources online if you feel this solution is not clear! tree Let’s write the code then. https://gist.github.com/NicolaM94/81f57ae53d2c79012926047528ea492b?embedable=true We’ll start writing a class, which will be the blueprint for each number inside the triangle. This class must be built with two parameters, , the actual value of the number, and , the list of previous Nodes from which you can jump to this value (always at most 2). Then, inside the class we are going to build two other attributes: , which will hold the updated value of the path up to that point, and , which will hold the biggest parent of that node. We initially set to be equal to . Node value parents updatedValue chosenParent updatedValue value After that, we call the block, which will be the first block executed when the class gets created. In that block, we loop over the two parents (the loop there it’s a bit useless since there always are two parents, but it’s useful to show the idea behind it) and we update the with the found. Finally, we update to be equal to the value of this node plus the updated value of its bigger parent. init chosenParent biggestParent updatedValue We can also write a simple function which recursively print out the chain of values that brought us here. PrintChain That’s it, really: you have everything you need to solve the problem! Of course, you need a wrapper to collect all the numbers and instantiate all of them as nodes. Here’s the one I wrote, but of course you should build one yourself for your implementation. https://gist.github.com/NicolaM94/756a0d5fa2477454f16c4c23537a9b22?embedable=true Lastly, in the main function, we can wrap everything up and loop over the last line to get our solution. As always, for the problems given by ProjectEuler.net, besides presenting math riddles and problems, . And I love that: they are so committed that publishing results and guides for their problems is forbidden (this is one of the first 100 problems, so I understand it is permitted). Given this, . You have everything you need to start working on it! I won’t give out the solution: you need to build this by yourself, if you want to know it! ProjectEuler.net is a lovely project: their main focus is to provide a tool to start learning, thinking, and reasoning about math and algorithms I don’t feel it would be fair to just give out the solution to copy-paste and get the achievement Have a nice coding guys! 😎 Time complexity It’s not that easy to model the time complexity for an algorithm like this one, but we can try to by comparing it with the brute-force solution. reason a bit more generally First off, in both cases, we need to parse the numbers in the triangle somehow, either to collect them as nodes or to store them in lists, arrays, or any other method you can think of. Let’s suppose we use the same parsing algorithm for both solutions, the brute force one and the smart one, and let’s suppose this parsing algorithm takes O(n) time, where n is the number of rows in the triangle. After parsing the elements, in solution, we must calculate the value of each one of the 2ⁿ⁻¹ possible routes. This, again, . the brute force leaves us with a time complexity of O(2ⁿ⁻¹) With the smart solution though we don’t need to do anything else besides parsing the elements correctly. . Since we are using the same parsing algorithm for both solutions, we can discard the time used for parsing while comparing. Thus, Given that we must pass on each element to parse it as a Node, we’ll do exactly n(n+1)/2 operations After this we only need to loop over the last row to find the maximum path, requiring O(n) time. the smarter solution requires only O(n) time while the brute force requires O(2ⁿ⁻¹) time! Conclusion That’s it! As always, I hope you liked the article and found it somehow useful. If so, consider leaving a clap or two or sharing it: it would make my day! I also have a page, if you want to contribute to the redaction of these articles by sharing a coffee with me! Ko-Fi Also, feel free to share your thoughts or questions about this in the comment section: we’re all here to learn! As always, thanks for reading. Nicola

The Avalanche Algorithm — How To Calculate the Maximum Possible Path in a Binary Tree

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

Convert Sorted Array to Binary Search Tree

How to Implement Heap in Data Structure

Implementing Red-Black Tree in Go — Part 1, The Search and Insert Operation

Implementing Red-Black Tree in Go — Part 2: The Delete Operation

Java Algorithms: Linked List in Binary Tree (LeetCode)

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

Convert Sorted Array to Binary Search Tree

How to Implement Heap in Data Structure

Implementing Red-Black Tree in Go — Part 1, The Search and Insert Operation

Implementing Red-Black Tree in Go — Part 2: The Delete Operation

Java Algorithms: Linked List in Binary Tree (LeetCode)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps