Need help with Project Euler algorithm

[Garrett Rowe]

Hey everyone, I posted in another thread that I was having problems coming up with an algorithm for this problem in Project Euler:

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 5
 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)

Could someone please give me a nudge in the direction of the "clever algorithm" that they could be referring to?. I thought about just taking the maximum from each decision point, but I can't prove that that would always give me the correct answer. As a matter of fact it seems like I can prove that it doesn't:

   1
  2 3
 6 3 5
9 3 6 2

Just choosing the best local decision here would give me
1 + 3 + 5 + 6 = 15

when the real maximum path is
1 + 2 + 6 + 9 = 18
[ March 21, 2008: Message edited by: Garrett Rowe ]

[David O'Meara]

Have you done any 'graph' problems? that is node-vector stuff.

You should be able to come up with a greedy algorithm that looks at the largest number in each row and tries to match with the largest on the row up and down - like the inverse of Djikstra (sp?)

Actually, you probably want to find largest pairs, then try to join them into a link from the top to the bottom eg in the first rom you have

"from one to two max is 75 + 95" so we store (1, 1, 2, 1, 180)
(row one item one and row two item 1 gives 180)
Then "From two to three max is 64 + 82" giving (2, 2, 3, 3, 146)
Looking back, we can't match these two, so you need to either decide to add
(1,1,2,2,75+64) so you can join them to make (1,1,3,3,75+64+146) or select the next largest from row 2 to 3.

Not perfect, but drop us a line if you refine it.

[Garrett Rowe]

Alright so here's the algorithm I thought of, although is seems like this would have to check every path also:

if x is a leaf node
   maxPath from x = x
else maxPath from x = x + max(max path lf child, max path rt child)

I just need to translate that into code.

[David O'Meara]

Hmm, also consider the following:

Given:

    A
  B   C
    D

If B>=C choose A-B-D, otherwise choose A-C-D

[Garrett Rowe]

Originally posted by David O'Meara:
Hmm, also consider the following:

Given:

    A
  B   C
    D

If B>=C choose A-B-D, otherwise choose A-C-D

My thinking was given the triangle

   A
  B C
 D E F
G H I J

There is exactly 1 maximum path from B to the end and 1 maximum path from C to the end, so the maximum path from A to the end is A + max(maximumPath(B), maximumPath(C)), that way A doesn't have to explore the entire path, it just looks at B and C's maximum path and appends itself to whichever is greater. I wrote the code in Haskell, because I'm trying to learn the language:

tri = [              [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]]
       
data Tree a = Leaf a | Branch a (Tree a) (Tree a)
 
maxPath tree = case tree of
                  Leaf a -> a
                  Branch a b c -> a + max (maxPath b) (maxPath c)
                  
build xss =
   let leaves = map (\x -> Leaf x) (last xss)
       attach ys xs = case (ys, xs) of
                        (_, []) -> []
                        ((y:z:rest), (x:xs)) -> Branch x y z : attach (z:rest) xs
   in head (foldl attach leaves (reverse . init $ xss))
            
answer18 = maxPath (build tri)

I got the right answer, but my algorithm isn't efficient enough to complete Problem 67

[Vikrant Pandit]

Garrett,

You can try the following pseudo code . Not sure if it is same as yours

  input_array [n][]
  = {
{n1},
{n2,n3},
{n4,n4,n5},
        ...........
............
    }
// Array index start at 0
for(i = n-1; i>=1 ; i--)
{
 
for(j=input_array[n].length -1;j>=1;j--)
{
if(element[i][j] > element [i][j-1])
element [i-1][j-1] += element[i][j];
else
element [i-1][j-1] += element[i][j-1];
}
 
}
 

For a try of height 100 (having 100 leaf nodes), it would require around 100 * 99 /2 iterations
Not very effcient , but just might work.

[Garrett Rowe]

Here's some Java code that's a quick and dirty translation of the Haskell code:

public class Euler
{
   private static int[][] triangle =
   {
     {75},
     {95, 64},
     {17, 47, 82},
     {18, 35, 87, 10},
     {20,  4, 82, 47, 65},
     {19,  1, 23, 75,  3, 34},
     {88,  2, 77, 73,  7, 63, 67},
     {99, 65,  4, 28,  6, 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},
     { 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23}
   };
 
   /**
    * Starts from the "bottom" of the int[][] and builds up to the root.
    * Returns a reference to the root node of the tree.
    */
   public static Node build(int[][] vals)
   {
       int lastRow = vals.length - 1;
       Node[] nodes = new Node[vals[lastRow].length];
 
       for (int i = 0; i < nodes.length; i++)
       {
          nodes[i] = new Node(vals[lastRow][i], null, null);
       }
 
       for (int j = lastRow - 1; j >= 0; j--)
       {
          nodes = buildH(vals[j], nodes);
       }
 
       return nodes[0];
 
   }
 
   private static Node[] buildH(int[] vs, Node[] children)
   {
      Node[] newChildren = new Node[vs.length];
      for (int i = 0; i < newChildren.length; i++)
      {
         newChildren[i] = new Node(vs[i], children[i], children[i + 1]);
      }
      return newChildren;
   }
 
   public static int maxPath(Node n)
   {
      if (n.isLeaf())
      {
         return n.value();
      }
 
      else
      {
         return n.value() + Math.max(maxPath(n.left()), maxPath(n.right()));
      }
   }
 
   private static class Node
   {
      private int value;
      private Node left;
      private Node right;
 
      public Node(int val, Node lf, Node rt)
      {
         value = val;
         left = lf;
         right = rt;
      }
 
      public boolean isLeaf()
      {
         return left == null && right == null;
      }
 
      public int value()
      {
         return value;
      }
 
      public Node left()
      {
         return left;
      }
 
      public Node right()
      {
         return right;
      }
 
   }
 
   public static void main(String[] args)
   {
      Node root = build(triangle);
      System.out.println(maxPath(root));
   }
}

[ March 22, 2008: Message edited by: Garrett Rowe ]
[ March 22, 2008: Message edited by: Garrett Rowe ]

[Garrett Rowe]

If I understand what you're saying correctly Vivek, you're saying I should reduce the Triangle from the bottom up:

   6
  2 1
 5 7 8 
9 4 6 3

So starting from the second to last line, the max sum for the 5 is 5 + 9, the max sum for the 7 is 7 + 6, and the max sum for the 8 is 8 + 6, so I can reduce the triangle by eliminating the bottom line and replace the second to last line with each corresponding max sum.

    6            6           22
  2  1     --> 16 15  --> 
14 13 14

I like that, I think thats a very workable solution.
[ March 22, 2008: Message edited by: Garrett Rowe ]

[Garrett Rowe]

FWIW, that algorithm worked flawlessly and almost instantaneously. Again I coded the solution in Haskell, but I'm sure it would work equally fast in Java. It even eliminated the need to create the unnecessary data structure.