# 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(2^{n}) time (exponential). There exists a solution that can be solved in O(n^{2}) time (quadratic). Find this solution.

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.

yes, it modifies values in

`pyramid`

while looping over it, but only ones that have already been seen, so itshouldbe fine.Edit: MORE GOLFING!

Here's my GNU APL solution:

The part

`{⍵,⊂⎕}⍣⎕ ⍬`

gets the input:`⍬`

)`{⍵,⊂⎕}`

) 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`{⍵,⊂⎕}`

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 onThe part

`{⍺+2⌈/⍵}/`

computes the sum:`/`

), 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)`{⍺+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 leftThanks for posting these coding challenges, they're fun! Here's a O(n^2) solution in C:

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 :)

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.Ah, that's a neat trick! I hadn't considered the possibility of a pseudo-multidimensional array.

Are you sure this is O(n²)?

you iterate over every value only once while setting it up bottom to top?

Yeah, the body of this loop:

will execute exactly

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

times.

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

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?

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`

.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 = (n

^{2}+ n)/2 elements to iterate over. Since our largest term there is n^{2}, 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.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 :)