-1
\$\begingroup\$

Triangle Puzzle

Consider the triangle below. This triangle would be represented by the following input file.

   5
  9 6
 4 6 8
0 7 1 5

By starting at the top and moving to adjacent numbers on the row below, one creates a path to the bottom of the triangle. There are many such paths in a triangle, which may have different weights. The weight of a path is the sum of all numbers encountered along the way. Write a program to find the weight of the path with the highest weight for a given triangle.

In above example, the maximum sum from top to bottom is 27, and is found by following the bold text above path. 5 + 9 + 6 + 7 = 27.

(More formally: The triangle is an acyclic digraph, and each number represents the value of a node. Each node has either two or zero direct successors, as shown by the arrows above. A complete path is a path which begins at the root node—the one with no immediate predecessors—and ends at a node with no immediate successors. The weight of a complete path is the sum of the values of all nodes in the path graph. Write a program which finds the weight of the complete path with the largest weight for a given triangle.)

Bigger test sample data :

9235 
9096 637 
973 3269 7039 
3399 3350 4788 7546 
1739 8032 9427 976 2476 
703 9642 4232 1890 704 6463 
9601 1921 5655 1119 3115 5920 1808 
645 3674 246 2023 4440 9607 4112 3215 
660 6345 323 1664 2331 7452 3794 7679 3102 
1383 3058 755 1677 8032 2408 2592 2138 2373 8718    
8117 4602 7324 7545 4014 6970 4342 7682 150 3856 8177 
1966 1782 3248 1745 4864 9443 4900 8115 4120 9015 7040 9258 
4572 6637 9558 5366 7156 1848 2524 4337 5049 7608 8639 8301 1939 
7714 6996 2968 4473 541 3388 5992 2092 2973 9367 2573 2658 9965 8168 
67 1546 3243 752 8497 5215 7319 9245 574 7634 2223 8296 3044 9445 120 
7064 1045 5210 7347 5870 8487 3701 4301 1899 441 9828 3076 7769 8008 4496 6796
\$\endgroup\$
6
  • \$\begingroup\$ I think you need to decide whether you want a lot of small but probably inefficient solutions ([code-golf]), or efficient but maybe not so small solutions ([code-challenge]/[fastest-code]). \$\endgroup\$
    – Gareth
    Jul 15, 2012 at 14:06
  • \$\begingroup\$ ok, thanks for letting me know as I am new to this site, let me remove code-golf as I want efficient solution. \$\endgroup\$
    – Sammy
    Jul 15, 2012 at 14:07
  • 15
    \$\begingroup\$ projecteuler.net/problem=67 :D \$\endgroup\$
    – beary605
    Jul 15, 2012 at 17:39
  • 10
    \$\begingroup\$ Stolen from Project Euler. -1 \$\endgroup\$
    – Mr.Wizard
    Jul 26, 2012 at 11:55
  • \$\begingroup\$ It seems fairly straightforward to get the optimum via a dynamic program. I'd expect that to be asymptotically optimal, though I'm not sure. How are you going to compare among optimal solutions with the same asymptotic running time? Are you going to benchmark actual large test cases? \$\endgroup\$
    – xnor
    Sep 18, 2014 at 19:10

10 Answers 10

2
\$\begingroup\$

(More formally: The triangle is an acyclic digraph, and each number represents the value of a node. <snip /> A complete path is a path which begins at the root node—the one with no immediate predecessors—and ends at a node with no immediate successors. The weight of a complete path is the sum of the values of all nodes in the path graph. Write a program which finds the weight of the complete path with the largest weight for a given triangle.)

This easily generalises to any dag G(V,E) with weighted nodes. Perform a topological sort, and then iterate through the nodes in that order setting weight[v] += max {weight[v'] : v' in predecessors(v)}. Assuming a suitable representation, this is O(E).

As an implementation note, it may be convenient to add a dummy "sink" node with weight 0 to which all the successor-less nodes of the original graph gain an edge. Alternatively it might be convenient to iterate through the topologically sorted nodes in reverse order using successors instead of predecessors.

The latter is the case given the special structure of the triangle, for which in addition it's possible to do an implicit topological sort and to use only O(sqrt(V)) extra space (assuming that we mustn't alter the original graph and hence require extra space).

input: a triangular array T of n rows increasing in length from 1 to n

scratch = clone T[n-1]
for y = n-2 downto 0
    for x = 0 to y-1
        scratch[x] = T[y][x] + max(scratch[x], scratch[x+1])

output: scratch[0]
\$\endgroup\$
1
\$\begingroup\$

Groovy

Here's a groovy script with two solutions, one using recursion and one using a "bottom-up" approach. The file "test_sample_data.txt" is assumed to be in the classpath.

// Read the sample data file, store as List<List<int>>
def triangle = getClass().
        getResource('test_sample_data.txt').        // get the file resource
        text.                                       // contents as string
        split('\n').                                // split into lines
        collect { line ->                           // collect rows
            line.split().collect { it as int }      // collect columns
        }

println "Recursive: ${findLargestWeightRecursively(triangle)}"
println "Bottom up: ${findLargestWeightBottomUp(triangle)}"

def findLargestWeightRecursively(List triangle, row = 0, col = 0) {
    def current = triangle[row][col]
    if (row < triangle.size() - 1) {
        def w1 = findLargestWeightRecursively(triangle, row + 1, col)
        def w2 = findLargestWeightRecursively(triangle, row + 1, col + 1)
        return Math.max(w1, w2) + current
    } else {
        return current
    }
}

def findLargestWeightBottomUp(List triangle) {
    def weights = triangle[triangle.size() - 1].clone()
    for (int row = triangle.size() - 2; row >= 0; row--) {
        def nextRow = triangle[row]
        for (int col = 0; col < nextRow.size(); col++) {
            def largest = Math.max(weights[col], weights[col + 1])
            weights[col] = nextRow[col] + largest
        }
        weights.remove(weights.size() - 1)
    }
    return weights[0]
}

Output:

Recursive: 108146
Bottom up: 108146
\$\endgroup\$
1
\$\begingroup\$

My Perl Solution

input file is named as input.txt

$refarray;
open TRIG, "input.txt";
while(<TRIG>){
$i++;
$_ =~ s/^\s+//g;
$_ =~ s/\s+$//g;
@num=split(/\s+/);
for $j (0...$#num) {
  $refarray[$i]->[$j]=$num[$j];
}
}
close TRIG;
while($i>0){
   for $j (0...$i-2){
      if($refarray[$i]->[$j]>$refarray[$i]->[$j+1])
    {
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j];
    }
      else{
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j+1];
    }
      $total=$refarray[$i-1]->[$j]."\t";
   } 
$i-=1;
}
print $total;
\$\endgroup\$
0
\$\begingroup\$

I solved this problem many years ago in a training for programming contest. Now I just translated to a modern language as C#.

int MaximumSum(List<List<int>> values)
{
    // Making a copy by values of all list and validating the data at same time.
    var numbers = new List<List<int>>();
    int index = 0;
    while ((index < values.Count) && (values[index] != null) && (values[index].Count == index + 1))
    {
        numbers.Add(new List<int>());
        for (int j = 0; j <= index; j++)
            numbers[index].Add(values[index][j]);
        index++;
    }
    if (index == values.Count)
    {
        /* Applying dinamic programming principles we can obtain the maximum value starting from the last row until the first one. 
         * Storing only the optimum result until the specific value being analized.
         * At the end the value on the top of the triangle will be the maximum needed.
         */
        for (int row = numbers.Count - 2; row >= 0; row--)
            for (int col = 0; col <= row; col++)
                numbers[row][col] += (numbers[row + 1][col] > numbers[row + 1][col + 1]) ? numbers[row + 1][col] : numbers[row + 1][col + 1];
        return numbers[0][0];
    }
    else
    {
        throw new Exception("Invalid data");
    }
}
\$\endgroup\$
0
\$\begingroup\$

Ruby, 2nd version

t=%w{
     1
    2 1
   3 2 1
  4 3 2 1
 5 4 3 2 1
1 2 3 4 5 10000
}.map &:to_i

l = []
i=1

loop do
    l.push t.slice!(0,i)
    i += 1
    break if t == []
end
trees = [0, 1].repeated_permutation(l.length-1).to_a.map! do |tree|
    [0].concat tree
end

trees.map! do |tree|
    newt = []
    tree.each_with_index do |e, i|
        newt.push tree.slice(0, i+1).inject :+
    end
    newt
end

rr = []
trees.each do |t|
    r = 0
    t.each_with_index do |v, i|
        r += l[i][v]
    end
    rr.push r
end
p rr.max

Code above outputs: 10005 Sample of data in the question results to 108146

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Doesn't always give the correct answer - the input {1, 2 1, 3 2 1, 4 3 2 1, 5 4 3 2 1, 1 2 3 4 5 10000} gives 17 instead of 10005 \$\endgroup\$
    – Gareth
    Jul 15, 2012 at 15:48
0
\$\begingroup\$

Python

Put the triangle in a file called "triangle.txt", with whitespace only between the numbers.

f=open("triangle.txt", "r")
triangle=eval("[["+f.read().replace(" ", ",").replace("\n", "],[")[:-4]+"]]")
f.close()
for i in range(len(triangle)-2, -1, -1):
    for j in range(len(triangle[i])):
        triangle[i][j]+=max(triangle[i+1][j+1],triangle[i+1][j])
    del triangle[i+1]
print triangle[0][0]

Example Triangle:

1      (   1   )
2 3    (  2 3  )
4 5 6  ( 4 5 6 )

The 2 has 4, 5 below it. 5>4, so replace the 2 with 2+5=7.
The 3 has 5, 6 below it. 6>5, so replace the 3 with 3+6=9.

1    (  1  )
7 9  ( 7 9 )

The 1 has 7, 9 below it. 9>7, so replace the 1 with 1+9=10.

There are no more rows to process, so the maximal sum is 10.

\$\endgroup\$
0
\$\begingroup\$

Q

t:"I"$'/:" "vs'read0`t;
{(-2_x),enlist (1_mmax[2;last x])+last -1_x}/[count[t]-1;t]
exit 0

It assumes the triangle is a space separated triangle of integers stored in a file called t.

On the second test case:

$ time q tri.q -q
108146

real    0m0.018s
user    0m0.010s
sys     0m0.010s
\$\endgroup\$
0
\$\begingroup\$

Here is my solution implementation in java. I got idea from this https://stackoverflow.com/a/8002423/205585

    package com.euler.problems;

    import java.util.*;

    public class Problem18
    {
       private static Map<Integer,List<Integer>> triangle = new HashMap<Integer,List<Integer>>();

       public static void main(String args[])
       {
         _init();
         int res = maxSum(triangle);
         System.out.println("Sum = "+res);
       }

       //max sum from top to bottom of right angled triangle
       public static int maxSum(Map<Integer,List<Integer>> triangle)
       {
         int sum = 0;
         if(triangle == null || triangle.isEmpty())
           return 0;
         int size = triangle.size();
         if(size == 1)
           return triangle.get(0).get(0);
         int i=size-2,tmp,tmp_max,max_value;
         while(i>=0)
         {
           List<Integer> current_row = new ArrayList<Integer>();
           current_row = triangle.get(i);
           for(int index=0; index<current_row.size(); index++)
           {
             tmp = current_row.get(index);
             tmp_max = tmp+triangle.get(i+1).get(index);
             max_value = tmp+triangle.get(i+1).get(index+1);
             if(tmp_max > max_value)
               max_value = tmp_max;
             current_row.set(index,max_value);
           }
           triangle.put(i,current_row);
           current_row = null;
           i--;

        }
      return triangle.get(0).get(0);
    }

    private static void _init()
    {
      List<List<Integer>> tuples = new ArrayList<List<Integer>>();
      tuples.add(Arrays.asList(75));
      tuples.add(Arrays.asList(95,64));
      tuples.add(Arrays.asList(17,47,82));
      tuples.add(Arrays.asList(18,35,87,10));
      tuples.add(Arrays.asList(20,4,82,47,65));
      tuples.add(Arrays.asList(19,1,23,75,3,34));
      tuples.add(Arrays.asList(88,2,77,73,7,63,67));
      tuples.add(Arrays.asList(99,65,4,28,6,16,70,92));
      tuples.add(Arrays.asList(41,41,26,56,83,40,80,70,33));
      tuples.add(Arrays.asList(41,48,72,33,47,32,37,16,94,29));
      tuples.add(Arrays.asList(53,71,44,65,25,43,91,52,97,51,14));
      tuples.add(Arrays.asList(70,11,33,28,77,73,17,78,39,68,17,57));
      tuples.add(Arrays.asList(91,71,52,38,17,14,91,43,58,50,27,29,48));
      tuples.add(Arrays.asList(63,66,4,68,89,53,67,30,73,16,69,87,40,31));
      tuples.add(Arrays.asList(4,62,98,27,23,9,70,98,73,93,38,53,60,4,23));
      int i=0;
      for(List<Integer> tuple : tuples)
      {
        triangle.put(i++,tuple);
      }
      //print
      for(Integer key : triangle.keySet())
     {
       System.out.println(triangle.get(key));
     }
    }
   }
\$\endgroup\$
0
\$\begingroup\$

Haskell solution

maximizeTree tree
    | length tree == 1 = head . head $ tree
    | otherwise = maximizeTree (take (length tree - 2) tree ++ [zipWith (\a b -> maximum a + b) (pairUpList . last $ tree) (tree !! (length tree - 2))])
    where pairUpList list = [[list !! n, list !! (n + 1)] | n <- [0 .. (length list - 2)]]

maximizeTree [[5], [9, 6], [4, 6, 8], [0, 7, 1, 5]]
\$\endgroup\$
0
\$\begingroup\$

Python solution where the file is read as list of lists and processed bottom up:

from io import open

def parse_file(fpath):
    return [[int(i) for i in l.strip('\n').split()] for l in open(fpath, "r").readlines()]

def process_row(lower, upper):
    results = []
    for i in range(0,len(upper)):
        results.append(upper[i] + max(lower[i], lower[i+1]))
    return results

def traverse_triangle_bottom_up(triangle):
    triangle.reverse()
    results = triangle.pop(0)
    for row in triangle:
        results = process_row(results, row)
    return results[0]

triangle = parse_file("triangle.txt")
max_weight = traverse_triangle_bottom_up(triangle)
print(max_weight)
\$\endgroup\$
5
  • \$\begingroup\$ Classic case of unnecessary OO. \$\endgroup\$
    – seequ
    Sep 18, 2014 at 21:09
  • \$\begingroup\$ I have "refactored" to procedural... May I ask you to elaborate on when it is appropriate and when it is not? \$\endgroup\$
    – CoreDump
    Sep 18, 2014 at 23:11
  • \$\begingroup\$ A rule of thumb (at least for me) is: If the data should be presented in a boxed form (i.e. a reader or container), use a class. Otherwise I stick to procedural style. \$\endgroup\$
    – seequ
    Sep 19, 2014 at 4:57
  • \$\begingroup\$ Not very elaborate of an explanation but thank you, nonetheless. \$\endgroup\$
    – CoreDump
    Sep 19, 2014 at 20:20
  • \$\begingroup\$ Well, it is completely subjective, which is the reason I'm now wondering why I even said that. So, eh, sorry about that. \$\endgroup\$
    – seequ
    Sep 20, 2014 at 18:43

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