TL;DR: Just my solution to the maximum path sum II puzzle from project euler

I though I would give this little puzzle a go and try a functional programming solution. Now even though I’ve solved the problem and it’s only a few functions it sure is hard to wrap you head around what is going on.

https://projecteuler.net/problem=67

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 1016.

import {map, reduceRight} from "lodash"


const data = [
  [75],
  [95, 64],
  [17, 47, 82],
  [18, 35, 87, 10],
  [20,  4, 82, 47, 65],
  [19,  1, 23, 75,  3, 34],
  [88,  2, 77, 73,  7, 63, 67],
  [99, 65,  4, 28,  6, 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],
  [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  [5, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]
]

const getMaxChild = (xs: number[], index: number) => Math.max(xs[index],  xs[index +1])

const reduceSumLine = (parent: number[], child: number[]) =>
                           map(parent, (value: number, i) => getMaxChild(child, i) + value)

const maxPathSum = (dataTree: number[][]) =>
                    reduceRight(dataTree, (sum: number[], xs: number[], i: number) =>
                            reduceSumLine( dataTree[i], sum ? sum: xs));

test("should return the max path", () => {
  let result = maxPathSum(data);
  expect(result[0]).toEqual(1016);
});

How it works

The idea is that you have a tree of numbers, if we traverse the tree, and follow a path from top to bottom, adding each number in the path together. What would the largest possible sum be?

The solution is to start from the bottom and work your way to the top.

Trying to start at the top does not work, you end up having to check every possible path through the tree. Which even if that’s a cool thing to try. It is not an optimum way to get the max sum.

The Solution

I’ve described the solution below. I’ve attempted to solve this is a more functional programming way using map and reduce.

Take the bottom row Take the first pair of number. Get the largest Add that to the node above.

The node above is the 10 in the example below :

     10
    /  \
   11  12

Step 1 : 

     22


Another example :

     10
    /  \
   11  12
  / \  /  \
 5  4 7  100

Step 1 :

     10
    /  \
   16  112


Step 2 :

     212