JavaScript Implementation of Problem 67
View source code here on GitHub!
- p0067()
Project Euler Problem 67
Thinking from the bottom up got the answer
Problem:
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3 7 4 2 4 6 8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
- Returns:
number --
1/**
2 * Project Euler Problem 67
3 *
4 * Thinking from the bottom up got the answer
5 *
6 * Problem:
7 *
8 * By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from
9 * top to bottom is 23.
10 *
11 * 3
12 * 7 4
13 * 2 4 6
14 * 8 5 9 3
15 *
16 * That is, 3 + 7 + 4 + 9 = 23.
17 *
18 * Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file
19 * containing a triangle with one-hundred rows.
20 *
21 * NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this
22 * problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take
23 * over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
24 *
25 * @return {number}
26 */
27exports.p0067 = function() {
28 const rows = [];
29 for (const line of utils.get_data_file('p0067_triangle.txt').trim().split(/\r?\n|\r|\n/g)) {
30 rows.push(line.split(' ').map(Number));
31 }
32 return triangles.reduceTriangle(rows);
33};
34
35const triangles = require('./lib/triangles.js');
36const utils = require('./lib/utils.js');