Project Euler 18

Question

Hey, been working at Project Euler, and this one is giving me some problems

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:

...

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)

here's the algorithm I've used to solve it

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Problem18
{
    class Program
    {
        static void Main(string[] args)
        {
            string triangle = @"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";
            string[] rows = triangle.Split('\n');
            int currindex = 1;
            int total = int.Parse(rows[0]);
            Console.WriteLine(rows[0]);
            for (int i = 1; i < rows.Length; i++)
            {
                string[] array1 = rows[i].Split(' ');
                if (array1.Length > 1)
                {
                    if (int.Parse(array1[currindex - 1]) > int.Parse(array1[currindex]))
                    {
                        Console.WriteLine(array1[currindex - 1]);
                        total += int.Parse(array1[currindex - 1]);
                    }
                    else
                    {
                        Console.WriteLine(array1[currindex]);
                        total += int.Parse(array1[currindex]);
                        currindex++;
                    }
                }
            }
            Console.WriteLine("Total: " + total);
            Console.ReadKey();
        }
    }
}

now whenever i run it, it comes up with 1064, only 10 less then the solution -- 1074

i haven't found any problems with the algorithm and I did the problem by hand and also came up with 1064, anyone know if the solution is wrong, i'm interpreting the question wrong, or if there's just a flaw in the algorithm?

Answer 1

It is a good question based on dynamic programming. You need to create a 2d data structure(like vector in c++) then follow the bottom to up approach of dp.

The formula is dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]). Try coding on your own then if you are stuck at some point see my solution.

vector< vector<int> > dp(n); // n is the number of rows
for (int i = 0 ; i < n; i++){
    for (int j = 0; j <= i; j++){
        cin >> val;
        dp[i].push_back(val);
    }
}
for (int i = n - 2 ; i >= 0; i--)
{
    for (int j = 0; j <= i; j++)
        dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);    
}
cout << dp[0][0] << endl;   
return 0;
}

input: 3 2 4 5 6 8 9

output: 16

Answer 2

Recursive (not necessarily the best) approach:

    static int q18(){
        int matrix[][] = // BIG MATRIX;
        return getMaxPath(matrix, 0, 0, 0);
    }
    static int getMaxPath(int matrix[][], int sum, int row, int col){
        if(row==matrix.length) return sum;
        return Math.max(getMaxPath(matrix, sum+matrix[row][col], row+1, col),
                        getMaxPath(matrix, sum+matrix[row][col], row+1, col+1));
    }

Answer 3

Here is a graphical description:

Answer 4

Here's what the bottom up method belisarius describes--using the trivial triangle given in problem 18--looks like, just in case the image in his post is confusing to anyone else.

      03
    07  04
  02  04  06
08  05  09  03

      03
    07  04
  02  04  06
08  05  09  03
^^^^^^

      03
    07  04
  10  04  06
08  05  09  03
    ^^^^^^

      03
    07  04
  10  13  06
08  05  09  03
        ^^^^^^

      03
    07  04
  10  13  15
  ^^^^^^
08  05  09  03

      03
    20  04
  10  13  15
      ^^^^^^
08  05  09  03

      03
    20  04
  10  13  15
      ^^^^^^
08  05  09  03

      03
    20  19
    ^^^^^^
  10  13  15
08  05  09  03

      23
      ^^
    20  19
  10  13  15
08  05  09  03

Answer 5

Your problem is that your algorithm is a greedy algorithm, always finding local maxima. Unfortunately that causes it to miss higher numbers down below because they are directly below lower numbers. For example, if the triangle were only 3 levels, your algorithm would pick 75 + 95 + 47 = 217, while the correct answer is 75 + 64 + 82 = 221.

The correct algorithm will either try every path and choose the one with the highest total, or compute paths from the bottom up (which allows you to avoid trying every one, thus being much faster). I should add that working from the bottom-up is not only much faster (O(n^2) instead of O(2^n)!), but also much easier to write (I did it in about 3 lines of code).

Answer 6

You've written a greedy algorithm, which I don't think fits the requirements here. Here's a quick example to demonstrate that point:

  1
 2 1
1 1 100 

Using your algorithm you'll reach a sum of 4, although the optimal solution is 102.