I am doing the euler "maximum path sum" exercice.
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 of the triangle.
I created a simple method which calculates for each position in the row, the maximum possible value. If we take the previous example, it becomes:
3
10 7
12 14 13
22 19 23 16
The maximum value in the last row is 23.
Here is is the code:
function maximumPathSumI(triangle) {
let columnSum = [];
for (let row=0; row<triangle.length; row++) {
let newColumnSum = [];
for (let column=0; column<triangle[row].length; column++) {
let maxPreviousValue = getMaxPreviousValueForPosition(column, columnSum);
newColumnSum[column] = maxPreviousValue + triangle[row][column];
}
columnSum = newColumnSum;
}
return Math.max(...columnSum);
}
function getMaxPreviousValueForPosition(position, previousValues) {
let maxValue = previousValues[position] || 0;
if (position > 0 && maxValue < previousValues[position-1]) maxValue = previousValues[position-1];
if (position < previousValues.length && maxValue < previousValues[position+1]) maxValue = previousValues[position+1];
return maxValue;
}
It works with the first test, but doesn't seem to give the right result with this triangel
const testTriangle = [
[75,],
[95, 64,],
[17, 47, 82,],
[18, 35, 87, 10,],
[20, 04, 82, 47, 65],
[19, 01, 23, 75, 03, 34,],
[88, 02, 77, 73, 07, 63, 67,],
[99, 65, 04, 28, 06, 16, 70, 92,],
[41, 41, 26, 56, 83, 40, 80, 70, 33,],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23,],
];
It returns 1116 instead of 1074.
When I go through the results row by row, everything seems fine to me.
Here is the intermediary calculations:
[ 75 ]
//[95, 64,],
[ 170, 139 ]
//[17, 47, 82,],
[ 187, 217, 221 ]
//[18, 35, 87, 10,],
[ 235, 256, 308, 231 ]
//[20, 04, 82, 47, 65],
[ 276, 312, 390, 355, 296 ]
//[19, 01, 23, 75, 03, 34,],
[ 331, 391, 413, 465, 358, 330 ]
//[88, 02, 77, 73, 07, 63, 67,],
[ 479, 415, 542, 538, 472, 421, 397 ]
//[99, 65, 04, 28, 06, 16, 70, 92,],
[ 578, 607, 546, 570, 544, 488, 491, 489 ]
//[41, 41, 26, 56, 83, 40, 80, 70, 33,],
[ 648, 648, 633, 626, 653, 584, 571, 561, 522 ]
//[41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
[ 689, 696, 720, 686, 700, 685, 621, 587, 655, 551 ]
//[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
[ 749, 791, 764, 785, 725, 743, 776, 707, 752, 706, 565 ]
//[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
[ 861, 802, 824, 813, 862, 849, 793, 854, 791, 820, 723, 622 ]
//[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
[ 952, 932, 876, 900, 879, 876, 945, 897, 912, 870, 847, 752, 670 ]
//[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
[ 1015, 1018, 936, 968, 989, 998, 1012, 975, 985, 928, 939, 934, 792, 701 ]
//[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23,],
[ 1022, 1080, 1116, 1016, 1021, 1021, 1082, 1110, 1058, 1078, 977, 992, 994, 796, 724 ]
