# Project Euler 18 & 67 - Maximum Path Sum - Solved with JavaScript

The 18th and 67th Project Euler problem - Maximum Path Sum - is stated as follows. 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 3 + 7 + 4 + 9, 23.

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

Find the maximum total from top to bottom of the larger triangle here and the very large triangle here.

``````// The triangle.
const str = `
3
7 4
2 4 6
8 5 9 3`

const getTopsyTurvyTriangleArray = (str) =>
// Split the string on every new line.
str.split('\n')
// Remove empty rows.
.filter(row => parseInt(row))
// Split the row every row on every space
// and convert it to an int.
.map(row => row.split(' ').map(str => parseInt(str, 10)))
// Reverse the array, since we want to process our
// triangle from the bottom up.
.reverse();

const getLongestPathLength = (triangle, legs = ) => {

// Sum the top of the triangle with its longest leg
// if we have reaced the top (now pointing downward)
// of our upside-down triangle.
if(triangle.length === 1){
return triangle + legs;
}

// Get the foundation of our upside down triangle.
const [foundation, ...top] = triangle

// Sum the current triangle foundation with its legs.
// There will be no legs the first time around.
const sums = [foundation.map((n, i) => n + (legs[i] || 0))]

// Get the longest legs. We only need all but one,
// since the next level is one less in length.
const longestLegs = sums.map((n, index, row) =>
row[index + 1] && row[index + 1] > n ? row[index + 1] : n,
).splice(0, sums.length - 1)

return getLongestPathLength(top, longestLegs);

}

// Convert triangle string to an array.
const triangle = getTopsyTurvyTriangleArray(str);

// Traverse the triangle bottom up and get the longest path.
const length = getLongestPathLength(triangle);``````