How to resolve the algorithm Maximum triangle path sum step by step in the JavaScript programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Maximum triangle path sum step by step in the JavaScript programming language
Table of Contents
Problem Statement
Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row: One of such walks is 55 - 94 - 30 - 26. You can compute the total of the numbers you have seen in such walk, in this case it's 205. Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.
Find the maximum total in the triangle below: Such numbers can be included in the solution code, or read from a "triangle.txt" file. This task is derived from the Euler Problem #18.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Maximum triangle path sum step by step in the JavaScript programming language
-
Imperative Approach:
- This approach uses a loop to iteratively combine adjacent elements into a single row.
- It creates a new row by adding the current element to the maximum of the element below it and the element below and to the right of it.
- It then removes the last two rows and adds the new row to the array.
- This process is repeated until there is only one row left, which contains the maximum sum path.
-
Functional Approach Using Foldr1 and ZipWith3:
- This approach uses higher-order functions to transform the list of lists into a single value.
- It employs the
foldr1function to apply a function (in this case, adding adjacent elements and selecting the maximum) to a list, reducing it to a single value. - The
zipWith3function is used to combine elements from multiple lists at the same index.
-
Functional Approach Using Distillation:
- This approach iteratively removes the last two rows of the triangle and combines their elements to create a new row.
- It uses the
distilLastLinefunction to perform this operation. - This process continues until there is only one row left, which contains the maximum sum path.
-
Functional Approach Using Foldr1 (Second Example):
- This approach is similar to the previous functional approach, but it uses a slightly different way to define the function.
- It uses the
foldr1function to apply a function to a list, reducing it to a single value. - The function in this case combines adjacent elements and selects the maximum.
-
Recursive Approach:
- This approach recursively combines adjacent elements into a single row until there is only one row left, which contains the maximum sum path.
- It recursively calls itself on the last two rows of the triangle, adding the current element to the maximum of the element below it and the element below and to the right of it.
- The base case is when there are only two rows left, in which case the two rows are combined into one.
Source code in the javascript programming language
var arr = [
[55],
[94, 48],
[95, 30, 96],
[77, 71, 26, 67],
[97, 13, 76, 38, 45],
[07, 36, 79, 16, 37, 68],
[48, 07, 09, 18, 70, 26, 06],
[18, 72, 79, 46, 59, 79, 29, 90],
[20, 76, 87, 11, 32, 07, 07, 49, 18],
[27, 83, 58, 35, 71, 11, 25, 57, 29, 85],
[14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55],
[02, 90, 03, 60, 48, 49, 41, 46, 33, 36, 47, 23],
[92, 50, 48, 02, 36, 59, 42, 79, 72, 20, 82, 77, 42],
[56, 78, 38, 80, 39, 75, 02, 71, 66, 66, 01, 03, 55, 72],
[44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36],
[85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 01, 01, 99, 89, 52],
[06, 71, 28, 75, 94, 48, 37, 10, 23, 51, 06, 48, 53, 18, 74, 98, 15],
[27, 02, 92, 23, 08, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
];
while (arr.length !== 1) {
var len = arr.length;
var row = [];
var current = arr[len-2];
var currentLen = current.length - 1;
var end = arr[len-1];
for ( var i = 0; i <= currentLen; i++ ) {
row.push(Math.max(current[i] + end[i] || 0, current[i] + end[i+1] || 0) )
}
arr.pop();
arr.pop();
arr.push(row);
}
console.log(arr);
[ [ 1320 ] ]
(function () {
// Right fold using final element as initial accumulator
// (a -> a -> a) -> t a -> a
function foldr1(f, lst) {
return lst.length > 1 ? (
f(lst[0], foldr1(f, lst.slice(1)))
) : lst[0];
}
// function of arity 3 mapped over nth items of each of 3 lists
// (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
function zipWith3(f, xs, ys, zs) {
return zs.length ? [f(xs[0], ys[0], zs[0])].concat(
zipWith3(f, xs.slice(1), ys.slice(1), zs.slice(1))) : [];
}
// Evaluating from bottom up (right fold)
// and with recursion left to right (head and first item of tail at each stage)
return foldr1(
function (xs, ys) {
return zipWith3(
function (x, y, z) {
return x + (y < z ? z : y);
},
xs, ys, ys.slice(1) // item above, and larger of two below
);
}, [
[55],
[94, 48],
[95, 30, 96],
[77, 71, 26, 67],
[97, 13, 76, 38, 45],
[07, 36, 79, 16, 37, 68],
[48, 07, 09, 18, 70, 26, 06],
[18, 72, 79, 46, 59, 79, 29, 90],
[20, 76, 87, 11, 32, 07, 07, 49, 18],
[27, 83, 58, 35, 71, 11, 25, 57, 29, 85],
[14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55],
[02, 90, 03, 60, 48, 49, 41, 46, 33, 36, 47, 23],
[92, 50, 48, 02, 36, 59, 42, 79, 72, 20, 82, 77, 42],
[56, 78, 38, 80, 39, 75, 02, 71, 66, 66, 01, 03, 55, 72],
[44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36],
[85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 01, 01, 99, 89, 52],
[06, 71, 28, 75, 94, 48, 37, 10, 23, 51, 06, 48, 53, 18, 74, 98, 15],
[27, 02, 92, 23, 08, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
]
)[0];
})();
1320
function maximumTrianglePathSum(triangle) {
function distilLastLine() {
let lastLine = triangle.pop(),
aboveLine = triangle.pop();
for (let i = 0; i < aboveLine.length; i++)
aboveLine[i] = Math.max(
aboveLine[i] + lastLine[i],
aboveLine[i] + lastLine[i + 1]
);
triangle.push(aboveLine);
}
do {
distilLastLine();
} while (triangle.length > 1);
return triangle[0][0];
}
// testing
let theTriangle = [
[55],
[94, 48],
[95, 30, 96],
[77, 71, 26, 67],
[97, 13, 76, 38, 45],
[ 7, 36, 79, 16, 37, 68],
[48, 7, 9, 18, 70, 26, 6],
[18, 72, 79, 46, 59, 79, 29, 90],
[20, 76, 87, 11, 32, 7, 7, 49, 18],
[27, 83, 58, 35, 71, 11, 25, 57, 29, 85],
[14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55],
[ 2, 90, 3, 60, 48, 49, 41, 46, 33, 36, 47, 23],
[92, 50, 48, 2, 36, 59, 42, 79, 72, 20, 82, 77, 42],
[56, 78, 38, 80, 39, 75, 2, 71, 66, 66, 1, 3, 55, 72],
[44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36],
[85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 1, 1, 99, 89, 52],
[ 6, 71, 28, 75, 94, 48, 37, 10, 23, 51, 6, 48, 53, 18, 74, 98, 15],
[27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
];
console.log(maximumTrianglePathSum(theTriangle));
1320
(() => {
"use strict";
// ------------------ MAX PATH SUM -------------------
// Working from the bottom of the triangle upwards,
// summing each number with the larger of the two below
// until the maximum emerges at the top.
// maxPathSum ::[[Int]] -> Int
const maxPathSum = xss =>
// A list of lists folded down to a list of just one
// remaining integer.
foldr1(
// The accumulator, zipped with the tail of the
// accumulator, yields pairs of adjacent sums.
(ys, xs) => zipWith3(
// Plus greater of two below
(a, b, c) => a + Math.max(b, c)
)(xs)(ys)(ys.slice(1))
)(xss)[0];
// ---------------- GENERIC FUNCTIONS ----------------
// foldr1 :: (a -> a -> a) -> [a] -> a
const foldr1 = f =>
xs => 0 < xs.length ? (
xs.slice(0, -1).reduceRight(
f, xs.slice(-1)[0]
)
) : [];
// zipWith3 :: (a -> b -> c -> d) ->
// [a] -> [b] -> [c] -> [d]
const zipWith3 = f =>
xs => ys => zs => Array.from({
length: Math.min(
...[xs, ys, zs].map(x => x.length)
)
}, (_, i) => f(xs[i], ys[i], zs[i]));
// ---------------------- TEST -----------------------
return maxPathSum([
[55],
[94, 48],
[95, 30, 96],
[77, 71, 26, 67],
[97, 13, 76, 38, 45],
[7, 36, 79, 16, 37, 68],
[48, 7, 9, 18, 70, 26, 6],
[18, 72, 79, 46, 59, 79, 29, 90],
[20, 76, 87, 11, 32, 7, 7, 49, 18],
[27, 83, 58, 35, 71, 11, 25, 57, 29, 85],
[14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55],
[2, 90, 3, 60, 48, 49, 41, 46, 33, 36, 47, 23],
[92, 50, 48, 2, 36, 59, 42, 79, 72, 20, 82, 77, 42],
[56, 78, 38, 80, 39, 75, 2, 71, 66, 66, 1, 3, 55, 72],
[44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36],
[85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 1, 1, 99, 89, 52],
[6, 71, 28, 75, 94, 48, 37, 10, 23, 51, 6, 48, 53, 18, 74, 98, 15],
[27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
]);
})();
You may also check:How to resolve the algorithm Emirp primes step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Mouse position step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Flatten a list step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Longest common subsequence step by step in the M4 programming language
You may also check:How to resolve the algorithm Sum of a series step by step in the Nim programming language