8

Problem number 18 from Project Euler's site is as follows:

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)

The formulation of this problems does not make clear if

  • the "Traversor" is greedy, meaning that he always choosed the child with be higher value
  • the maximum of every single walkthrough is asked

The NOTE says, that it is possible to solve this problem by trying every route. This means to me, that is is also possible without!

This leads to my actual question: Assumed that not the greedy one is the max, is there any algorithm that finds the max walkthrough value without trying every route and that doesn't act like the greedy algorithm?

I implemented an algorithm in Java, putting the values first in a node structure, then applying the greedy algorithm. The result, however, is cosidered as wrong by Project Euler.

sum = 0;

void findWay(Node node){
    sum += node.value;
    if(node.nodeLeft != null && node.nodeRight != null){
            if(node.nodeLeft.value > node.nodeRight.value){
                findWay(node.nodeLeft);
            }else{
                findWay(node.nodeRight);
            }
        }
}
6
  • 1
    Sometimes choosing the lower number will result in choosing a higher number on the next choice, one high enough to offset the differencec in the previous choice, this is why your algorithm is wrong. Nov 30, 2012 at 23:49
  • Of course it is, but is this asked in the problem? Nov 30, 2012 at 23:50
  • "maximum total" to me means exactly that. Maximum is an absolute word, so read it as "absolute maximum total possible". Nov 30, 2012 at 23:56
  • 2
    I'd tackle it with a modified Dijkstra's algorithm I think. I'll try it out tomorrow. It should let you figure quickly when to early-terminate a route. Maybe there's a better way... there goes my good night's sleep.
    – James
    Dec 1, 2012 at 1:50
  • This is typically an example of a dynamic programming problem, which can often appear to be solvable with a greedy method. Dynamic programming requires the solution of subproblems to solve the main problem. Dec 1, 2012 at 1:59

4 Answers 4

9

Spoiler alert: This answer leads you to a solution, but does not implement it


Using WuHoUnited's example, modified for uniqueness:

   9
  7 0
 2 4 6
8 5 1 3

Ask yourself this: If you found yourself at 2, would you ever take 8 instead of 5, knowing they are the leaf nodes of the tree? Similarly, If you found yourself at 6, would you ever take 3 instead of 1, knowing those are the leaf nodes of the tree?

Certainly not. We can now reduce the tree, knowing what decision we'd take at the penultimate branch (regardless of how we got there):

   9
  7 0
10 9 9

I think you see where this is going.

1

As somebody who has solved the problem I can tell you that the greedy algorithm is NOT what they are looking.

It is looking for the maximum value of all possible routes.

example

   3
  7 4
 2 4 6
8 5 1 3

3+7+4+5 = 19 <- greedy
3+7+2+8 = 20 <- not greedy

So the answer should be 20

3
  • ok but this will mean that there is no other way than walk every route, isn't it? Dec 1, 2012 at 0:54
  • 1
    @ValentinoRu obviously not, the euler problem says so. This is a graph problem, so try drawing graphs with the small number sets in various ways and see if you can identify any representations of them that brings the information you want to the forefront. Dec 1, 2012 at 1:05
  • It is like Project Euler and Jimmy Hoffa say: There is a very efficient way to solve the problem without trying every route.
    – WuHoUnited
    Dec 1, 2012 at 1:17
-1

Dijkstra's algorithm for shortest paths (turn all edges negative).

1
  • 5
    You could be a little more verbose in your answer. Even a link to Dijkstra's algorithm would be more helpful. Dec 1, 2012 at 13:21
-1

Greedy approach is definitely not the approach you should consider for this problem. Think of a solution that exhaustively checks all possible routes and find the maximum. Then optimize it using Dynamic programming.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.