Euler project #18 approach

Question

I am looking into an Euler project. Specifically #18.
To sum up, the idea is to find the max path from a triangle:

   3
  7 4
 2 4 6  
8 5 9 3

3 + 7 + 4 + 9 = 23.

Reading for this, most people indicate that this is solved correctly by working bottom to top instead of using an algorithm that works "greedy" from top to bottom.

I can understand that starting from top and going down selecting the max you find is "shortsighted" and may not be the overall max.

But why is the approach of going from bottom to top any better?
It seems to me it suffers from the same problem.

For example in the triangle in the example we would get (starting from bottom):
9+6+4+3=22 < 23

So why start from bottom-up?

Answer 1

Although there are multiple answers, there is inadequate exploration of the top-down approach. This made me feel that I could contribute by giving a new answer. Top-down is not necessarily greedy and bottom-up is not automatically dynamic programming. Appreciate Jeffrey Sax's response in providing clarity.

Here is a top-down approach. Like elsewhere, we represent the triangle of numbers as a two-dimensional array. Let L(i, j) denote the number at the (i, j) coordinate.The maximum total in reaching (i, j) from the top is given by the recurrence relation:

M(i, j) = L(i, j) + max(M(i-1, j), M(i-1, j-1))

Further:

• Wherever a cell does not exist, the value can be regarded as 0.
• 0 <= j <= i. This follows from the fact that every row has one cell more than the preceding one.
• M(0, 0) = L(0, 0). This is the base case. To avoid confusion due to difference from implementation (due to programming language semantics), I have chosen 0 as the start index.

The solution is to find the maximum among all M(i, j) when i is the last row in the triangle. Here is a syntactically correct implementation in Go:

func maxPathSumTopDown(t [][]int) int {
    if t == nil {
        return 0
    }
    var i int = 1
    for ; i < len(t); i++ {
        t[i][0] += t[i-1][0]
        t[i][i] += t[i-1][i-1]
        for j := 1; j <= i-1; j++ {
            t[i][j] += max(t[i-1][j-1], t[i-1][j])
        }
    }
    var sum int
    for _, v := range t[i-1] {
        sum = max(sum, v)
    }
    return sum
}

The main benefit of bottom-up is that its implementation is more succinct: It reduces the number of cells in each iteration (traveling upwards) till just one cell is left. This helps avoid running an extra loop to find the maximum.

For sake of completeness, here is the bottom-up code:

func maxPathSum(t [][]int) int {
    if t == nil {
        return 0
    }
    var i = len(t) - 2
    for ; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            t[i][j] += max(t[i+1][j], t[i+1][j+1])
        }
    }
    return t[0][0]
}

Answer 2

static int getTriangle() throws FileNotFoundException, IOException{
        File file = new File("/home/rakib/This Pc/programming/problem solving/ProjectEuler/src/projecteuler/euluer17.txt");
        BufferedReader br = new BufferedReader(new FileReader(file));
        String n;
        int i = 0;
        int [][] array = new int[15][15];
        while((n = br.readLine()) != null){
            String [] temp = n.split(" ");
            for(int j = 0; j < temp.length; j++){
                 array[i][j] = Integer.parseInt(temp[j]);         
            }
             i++;
        }


    for(int j = array.length-2; j >= 0; j--){
        int []tempArray = new int [j+1];
           for(int k =0; k <= j; k++){
               tempArray[k] = array[j][k] + Math.max(array[j+1][k], array[j+1][k+1]);
           }
           array[j] = tempArray;
    }

 return array[0][0];
}

i used bottom up approach to solve this problem. working from last two row. just add max value with path element.

Answer 3

Here is a complete answer:

#include <iostream>

using namespace std;

int main()
{
  int sum1,sum2;
  int A[4][4] = {{3,0,0,0},{7,4,0,0},{3,4,6,0},{8,5,9,3}};
  for(int i=2;i>=0;i--){
     for(int j=0;j<4;j++){
        sum1=A[i][j]+A[i+1][j];
        sum2=A[i][j]+A[i+1][j+1];
        if(sum1>sum2){
            A[i][j]=sum1;
        }
        else{
            A[i][j]=sum2;
        }
     }
  }
  cout<<A[0][0]<<endl;
}

Answer 4

Since the rows are small in number you can use also recursion to compute the greatest sum :

import sys
def max_sum(i,j):
    if i==14:
        return a[i][j]
    return a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1))
a=[]
for i in range(15):
    b=list(map(int,sys.stdin.readline().split()))
    a.append(b)
print(max_sum(0,0))

for question 67 -(Maximum path sum II) you can use memoisation:

import sys
d={}
def max_sum(i,j):
    if (i,j) in d:
        return d[(i,j)]
    if i==99:
        return a[i][j]
    d[(i,j)]=a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1))
    return d[(i,j)]
a=[]
for i in range(100):
    b=list(map(int,sys.stdin.readline().split()))
    a.append(b)
print(max_sum(0,0))

Answer 5

It's something called dynamic programming.

You have such triangle:

   3
  7 4
 2 4 6  
8 5 9 3

When you move from the bottom to the top, you can calculate the best choices on last iteration. In this case you take the last row 8 5 9 3 and maximize sum in addition to previous line.

Iteration 1: Assume that you are on last-1 step.

You have line 2 4 6, let's iterate on it.

From 2, you can go to either 8 or 5, so 8 is better (maximize your result from 2) so you calculate first sum 8 + 2 = 10.

From 4, you can go to either 5 or 9, so 9 is better (maximize your result from 4) so you calculate second sum 9 + 4 = 13.

From 6, you can go to either 9 or 3, so 9 is better again (maximize your result from 6) so you calculate third sum 9 + 6 = 15.

This is the end of first iteration and you got the line of sums 10 13 15.

Now you've got triangle of lower dimension:

    3
  7  4
10 13 15  

Now go on until you get one value, which is exactly 23.

Answer 6

Actually, you needn't start bottom-up; you may as well start top-down, providing you do it properly.

The way it works bottom up is best illustrated by the taking what happes at each level of the pyramid. The path surely must cross each level at some point.

    x
   x x
  x h x
 x y y x
x y y y x

Let's say it's h. From the definition of allowable paths, the path can only follow down into the y-marked places, which forms a problem similar to the original - if we find a maximal path through the ys and the maximal path of the whole triangle actually goes through h, it will surely follow along a maximal path in ys (if not, you can switch the part of path in the smaller triangle and get an overall better path).

So if you structure your algorithm top-down computing the maximal path from the current node down, you get the correct result (ie. maximal path value, from which you can easily get the path itself).

Now, this takes O(N) (N meaning the number of the numbers), because for each place, you just consider two paths and use the pre-computed values from the lower level.

Virtually the same algorithm can be implemented top down, where you start at the top and recurse down, provided you memoize the result.

best_length(node)
{ 
  if(node is terminal)
    return value(node)
  int m = 0
  for(next : lower neighbors of node)
    m = max(best_length(next), m)
  return m + value(node);
}

Another possibility of doing this top-down would be just reverse the computation. You start at the top, for each node considering its upper neighbors, and get the path length from the top ending in this node (instead of the path going from this node down to the bottom row). At the end, you gather the data from the bottom row and you're done.

Answer 7

This is a problem that can be solved using graph theory. For each point, you can only travel to each of it's two 'children' (the left and right node below it). For all of the leaf nodes (the bottom row) include a path to an "end node" (with zero cost).

You want the largest number, which in turn is the longest path.

To do this, you implement a BFS (which is generally a shortest path algorithm), but instead of having the weight between a parent and child node being the value of the child node, you make it be the additive inverse of the child nodes value.

You cannot use Dijkstra easily here because Dijkstra is for non-negative paths only.

BFS has running time of O(|E|+|V|).
In a triangle there are 1+2+3+4+5+..+n = (1/2)(n)(n-1) nodes
This means that there are (n)(n-1) paths, plus the (n) for the final node connection
Total: (1/2) (3n^2 -n) where n is the number of rows.

Answer 8

The difference is not between top-down and bottom-up. The difference is between greedy and 'frontier' methods.

A greedy algorithm won't necessarily help you, because you can't recover if the best part of the tree gets out of reach. For example: a greedy algorithm would choose the path 1-3 from top to bottom. It would miss the 9 entirely.

    1
   2 3
  9 1 1

In order to find the true maximum, you'd have to essentially traverse nearly all paths.

The bottom-up approach, as it is described, doesn't have this problem. It examines at most n*(n-1) paths: 2 for each element. However, calling it the 'bottom-up' approach is misleading.

Why? Because there is a top-down approach that is equivalent. The essence is that you have a kind of 'frontier' with best results for all trees behind the frontier. Whether you move the frontier up or down is secondary. For the top-down approach in the above example, you calculate for each row the sum of each element and the maximum of the two best totals above it:

     1
    3 4
  12 5 5

In the bottom-up approach, you calculate for each row the sum of each element and the maximum of the two best totals below it. In reverse order:

  9  1 1
   11 4
    12

There is about equal work in both these top-down and bottom-up approaches.

Answer 9

Using your example, the "bottom up" way to approach it is:

Examining the bottom row, the most you can get from each element is

8,5,9,3

Examining the next-to-bottom row, the most you can get from each element is (depending on whether you go left or right from it):

2+max(8,5),4+max(5,9),6+max(9,3) = 10,13,15

So this is great; we've eliminated 2 rows by squishing them together to replace them with one row, reducing the problem to

     3
   7   4
10  13  15

Obviously we can just keep repeating this. Examining the next row up, the most you can get from each element is

7+max(10,13),4+max(13,15) = 20,19

And so from the top, the most you can get is

3+max(20,19) = 23

QED.

Answer 10

Taking a bottom up approach eliminates paths while going top-down only adds potential paths.

Because you're eliminating bad paths quicker, doing a breadth-first search becomes the optimal solution. A depth-first search in either direction is both wrong (as you've shown) and slow.