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
• 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]). Jul 15 '12 at 14:06
• ok, thanks for letting me know as I am new to this site, let me remove code-golf as I want efficient solution. Jul 15 '12 at 14:07
• Jul 15 '12 at 17:39
• Stolen from Project Euler. -1 Jul 26 '12 at 11:55
• 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?
– xnor
Sep 18 '14 at 19:10

(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

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
}

Output:

Recursive: 108146
Bottom up: 108146

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; 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; } else { throw new Exception("Invalid data"); } } 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| .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 • 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 Jul 15 '12 at 15:48 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 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. 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 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)); } } } 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 [, [9, 6], [4, 6, 8], [0, 7, 1, 5]]

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

triangle = parse_file("triangle.txt")
max_weight = traverse_triangle_bottom_up(triangle)
print(max_weight)
• Classic case of unnecessary OO. Sep 18 '14 at 21:09
• I have "refactored" to procedural... May I ask you to elaborate on when it is appropriate and when it is not? Sep 18 '14 at 23:11
• 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. Sep 19 '14 at 4:57
• Not very elaborate of an explanation but thank you, nonetheless. Sep 19 '14 at 20:20
• Well, it is completely subjective, which is the reason I'm now wondering why I even said that. So, eh, sorry about that. Sep 20 '14 at 18:43