Total Triangles
(Challenge added 699 days ago.)
Find the best scoring path through the triangle.
The Problem
Given a triangle of numbers such as:
4 4 1 1 4 1 1 4 1 1
and starting with the top-most number, you should move down a row at a time to one of the adjacent numbers, adding up the numbers as you go. When you reach the bottom-most row, you will have a total. You need to find the maximal total possible.
In the example above, the best path total is 16 which is obtained by taking this path:
4 4 1 1 4 1 1 4 1 1
See the examples section below for more complicated triangles.
More Information
- The triangles above and below are formatted for readability. The actual triangles your code will be given will have no leading spaces (Click on one of the runs below to see this.)
- The triangle will be given to your program on stdin and your code will be expected to display only the total (plus any trailing whitespace you fancy) on stdout.
- On each line, the numbers are separated by a single space and each line ends with a single newline. Numbers in the triangle will be in the rangle 0 to 99 inclusive, and may be padded with leading spaces to a maximum length of 2 digits.
- While you can brute force the smaller triangles, that approach won't succeed on the later and much larger triangles. Remember you only have four seconds of execution time, and run 6 requires you to find the best path through a 50-row triangle (Which has 2**49 unique paths.)
- Your code will be run six times with increasingly larger triangles. You will need to output the correct total for each of the triangles for your code to pass overall.
Examples
Here is a more complicated triangle with the path which yields the best total highlighted. Again, note that the triangle is centred for readability and that the triangles given to your code will not have any leading spaces.
11 66 71 52 32 83 59 69 23 17 79 33 96 18 59
The total for this path is 294.
As mentioned above, your code will be run six times. For the first five runs, the triangles will remain static. You can view each triangle, and the total of the best path by following these links :
- Run 1 - The 4-row triangle above.
- Run 2 - The 5-row triangle above.
- Run 3 - A 10-row triangle.
- Run 4 - A different 10-row triangle.
- Run 5 - A 50-row triangle.
It will be the fifth run which should identify any performance issues with your code.
For Run 6, the triangle will also be a 50-row triangle, but it will be different for each submission you make. Click to see Run 6. You can reload the page to get a different triangle.