# Programming Challenge: Given a triangle of numbers, find the path from the top to the bottom of the triangle with the largest sum.

This problem is based on the Project Euler problem here.

Goal: Given some input describing a triangle of numbers, find the path starting from the top-most row of the triangle and ending at the bottom-most row of the triangle that contains the largest sum of all of the numbers along the path. You may only move downward and you must select an adjacent position to move to. Efficiency is not a requirement for completion.

Constraints:

• The first line of input for a triangle will be a single integer telling you how many rows the triangle will have.
• Each following line of input will be the next row of the number triangle, starting at the first row.
• For each line describing the number triangle, the individual numbers will be separated by a single space.

Note: The constraints above are to keep hard-coded triangles out of submitted solutions while also ensuring that all languages can equally handle this problem without annoying workarounds for lower-level languages. The consistency also makes it easier for beginners to review and understand someone else's code, and makes it easier to receive help if you get stuck. They're not necessarily required, but are highly encouraged.

Example input:

``````4
1
3 2
4 5 6
7 8 9 10
``````

Corresponding triangle:

``````   1
3 2
4 5 6
7 8 9 10
``````

Expected result: `19` (1 + 2 + 6 + 10)

Extra Credit: As noted on the Project Euler page, you can solve this using a brute force method, but it's incredibly inefficient. Specifically, a brute force solution would be O(2n) time (exponential). There exists a solution that can be solved in O(n2) time (quadratic). Find this solution.

1. xiretza
(edited )
I think I did this one on codewars before, couldn't find the code anymore though. So here, have some fresh, ugly, probably-correct Python3. num_rows = int(input()) pyramid = [ [int(c) for c in...

I think I did this one on codewars before, couldn't find the code anymore though. So here, have some fresh, ugly, probably-correct Python3.

``````num_rows = int(input())

pyramid = [
[int(c) for c in input().split()]
for i in range(num_rows)
][::-1]

for rownum, row in enumerate(pyramid[1:], 1):
prev_row = pyramid[rownum-1]
pyramid[rownum] = [
d + max(prev_row[i], prev_row[i+1])
for i, d in enumerate(row)
]

print(pyramid[-1])
``````

yes, it modifies values in `pyramid` while looping over it, but only ones that have already been seen, so it should be fine.

Edit: MORE GOLFING!

``````from functools import reduce
print(reduce(lambda s,r:[d+max(s[i:i+2])for i,d in enumerate(r)],[list(map(int,input().split()))for _ in range(int(input()))][::-1]))
``````
2. mironimous
(edited )
Here's my GNU APL solution: {⍺+2⌈/⍵}/{⍵,⊂⎕}⍣⎕ ⍬ The part {⍵,⊂⎕}⍣⎕ ⍬ gets the input: We start with an empty value (⍬) The ⍣ in this case applies the function before it ({⍵,⊂⎕}) as often as the...

Here's my GNU APL solution:

``````{⍺+2⌈/⍵}/{⍵,⊂⎕}⍣⎕ ⍬
``````

The part `{⍵,⊂⎕}⍣⎕ ⍬` gets the input:

• We start with an empty value (`⍬`)
• The ⍣ in this case applies the function before it (`{⍵,⊂⎕}`) as often as the number behind it (`⎕`, which is a number inputted by the user and the first line) to the result of the previous iteration and starts with the empty value
• The function `{⍵,⊂⎕}` gets a new line from input, encloses it (so it is a single array element even if it is an array itself) and appends it to the existing array we are iterating on

The part `{⍺+2⌈/⍵}/` computes the sum:

• Now we have an array which contains the arrays of the triangle in ascending order, where we apply the reduce operator (`/`), which evaluates by essentially putting the function before it (`{⍺+2⌈/⍵}`) between every element in the target array (the indiviual triangle rows) and applies them from right to left in usual apl fashion (from the longest triangle row to the smallest one)
• The function `{⍺+2⌈/⍵}` takes the maximum per two neighboring elements from the right array (`2⌈/⍵`, which is just the reduce operator per 2 elements with the maximum function `⌈`) and adds them element-wise to the array on the left
3. 
panic
Thanks for posting these coding challenges, they're fun! Here's a O(n^2) solution in C: #include <stdlib.h> #include <stdio.h> int main() { int rows = 0; fscanf(stdin, "%d", &rows); // Fill in...

Thanks for posting these coding challenges, they're fun! Here's a O(n^2) solution in C:

``````#include <stdlib.h>
#include <stdio.h>

int main()
{
int rows = 0;
fscanf(stdin, "%d", &rows);
// Fill in triangle from the input.
int *triangle = calloc(rows * rows, sizeof(int));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < i + 1; ++j)
fscanf(stdin, "%d", &triangle[i * rows + j]);
}
// Compute maximum sums bottom-up.
int *sums = calloc((rows + 1) * (rows + 1), sizeof(int));
for (int i = rows - 1; i >= 0; --i) {
for (int j = 0; j < i + 1; ++j) {
int left = sums[(i + 1) * (rows + 1) + j];
int right = sums[(i + 1) * (rows + 1) + j + 1];
sums[i * (rows + 1) + j] = triangle[i * rows + j] +
(left > right ? left : right);
}
}
printf("%d\n", sums);
return 0;
}
``````
1. 
Emerald_Knight
No problem! I'm trying to leave enough time in between my own submissions to allow others the opportunity to post coding challenges, but since it's been a week since the last one I posted without...

No problem! I'm trying to leave enough time in between my own submissions to allow others the opportunity to post coding challenges, but since it's been a week since the last one I posted without anyone else submitting one, I figured it was about time to get a new one going :)

A solution in C right out of the gate! My C is a bit rusty, so I'll need to review this when I'm a little more awake (i.e. tomorrow). If your solution is as I expect, then the bottom-up approach is probably more appropriate than my top-down approach from years ago because it would shave off an additional linear step :)

1. 
panic
Yeah, sorry if the code is a bit dense. The pattern array[x * width + y] for accessing two-dimensional arrays is kind of a silly C-ism (since there's no built-in support for dynamic 2-D arrays...

Yeah, sorry if the code is a bit dense. The pattern `array[x * width + y]` for accessing two-dimensional arrays is kind of a silly C-ism (since there's no built-in support for dynamic 2-D arrays unless you want to allocate each row separately). For example, `sums[(i + 1) * (rows + 1) + j]` is really just `sums[i + 1][j]` but with an explicit row width.

1 vote
1. Emerald_Knight
Ah, that's a neat trick! I hadn't considered the possibility of a pseudo-multidimensional array.

Ah, that's a neat trick! I hadn't considered the possibility of a pseudo-multidimensional array.

1 vote
2. 
ali
Are you sure this is O(n²)? you iterate over every value only once while setting it up bottom to top?

Are you sure this is O(n²)?
you iterate over every value only once while setting it up bottom to top?

1. 
panic
Yeah, the body of this loop: for (int i = rows - 1; i >= 0; --i) { for (int j = 0; j < i + 1; ++j) { will execute exactly rows + … + 1 = rows * (rows + 1) / 2 times.

Yeah, the body of this loop:

``````    for (int i = rows - 1; i >= 0; --i) {
for (int j = 0; j < i + 1; ++j) {
``````

will execute exactly

rows + … + 1 = rows * (rows + 1) / 2

times.

1. ali
Thanks for the explanation, I guess I gotta practice a bit more

Thanks for the explanation, I guess I gotta practice a bit more

4. 
ali
I did it on a whiteboard to practice for my upcoming job interview. I got some off by one errors when I typed it in. And I didn't use user input but a given String. When I typed it in I used the...

I did it on a whiteboard to practice for my upcoming job interview. I got some off by one errors when I typed it in. And I didn't use user input but a given String. When I typed it in I used the user input but java was causing trouble with the scanner and whitespace so instead I seperate the values by dots

My solution and If I see it right some others here, was basically to fill the table up top to bottom with the highest value of the 2 values under it. This should solve it in linear time? Please correct me if I am wrong.
Also, isn't this dynamic programming?

``````import java.util.Arrays;
import java.util.Scanner;

public class HighestValuePyramid {
public static void main(String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rows");
int rows = s.nextInt();

int[][] pyramidArray = new int[rows][rows];
for(int i = 0;i<rows;i++){
System.out.println("Enter values for the pyramid");
String row = s.next();
String[] rowA = row.split("\\.");
for(int j = 0; j<rowA.length;j++){
pyramidArray[i][j]=Integer.parseInt(rowA[j]);
}
}
int highestValue = highestValue(pyramidArray);
System.out.println(highestValue);

}

private static int highestValue(int[][] pyramidArray) {
int[][] valuePyramid = new int[pyramidArray.length][pyramidArray.length];
valuePyramid[pyramidArray.length-1]=pyramidArray[pyramidArray.length-1]; // keep last row the same
for(int row=pyramidArray.length-2;row>=0;row--){
for(int col = 0;col<=row;col++){
valuePyramid[row][col]= Math.max(valuePyramid[row+1][col],valuePyramid[row+1][col+1])+pyramidArray[row][col];
}
}
System.out.println(Arrays.deepToString(valuePyramid));

return valuePyramid;
}
}
``````
1 vote
1. Emerald_Knight
By "input" I didn't necessarily mean from the user, but that the pyramid description is to be received via standard input. This can come in the form of user input, or you could redirect file...

And I didn't use user input but a given String.

By "input" I didn't necessarily mean from the user, but that the pyramid description is to be received via standard input. This can come in the form of user input, or you could redirect file contents instead, e.g. `java your_java_program < pyramid_description.txt`.

This should solve it in linear time? Please correct me if I am wrong.

Not linear, no. While the number of rows grows linearly, the number of elements that you have to iterate through grows as a summation of integers from 1 to n, meaning you'll have n(n+1)/2 = (n2 + n)/2 elements to iterate over. Since our largest term there is n2, our time complexity is thus quadratic. Although it's not a concrete rule and you should definitely verify, the nested `for` loops that grow with the size of the array length should serve as a good intuitive section of your code to help identify that it's probably quadratic.

Also, isn't this dynamic programming?

Excellent question. I think you're right. This would be an example of bottom-up dynamic programming, where we're solving the smaller sub-problems then using those solutions to solve the larger sub-problems. In this case, even if we're modifying the array(s) in place, we're essentially solving "maximum path sum so far up to this row", then using that step to solve "maximum path sum so far up to the next row". Good eye!

Also, good luck with the job interview! I'm sure you'll do well :)

1 vote