The gist behind Project Euler 18 and 67.

Explanation.md

The voila moment came for me when I realised I had to seed the fold computation with the base layer in the triangle.

The triangle is represented as a nested list, like so: List(List(1), List(2, 3), List(4, 5, 6)) and so forth.

     1
    / \
   2   3
  / \ / \
 4   5   6    <- this is the "base layer" in my explanation.

Since you need to add the maximum of the two immediate children to the layer above, a foldRight wouldn’t give me all the info I need in the curent iteration. foldRight for me means “the data is coming FROM the right”, i.e. List(4, 5, 6) will be processed first, then List(2, 3) but at no point in the iteration will they be available together so I can do the sum. List(4, 5, 6) would need to come into the iteration with List(2, 3) in another way, and I realised I can use the foldRight’s accumulator for that by seeding the foldRight with the base layer in the triangle (aka the last list List(4, 5, 6)).

The easiest way was to just seed the foldRight with a list of zeros one element larger than the base layer. You then break it up into pairs using sliding(2,1), take the max of the pairs, and sum the max with the corresponding (thanks to zip) element in the layer above.

      1
     / \
    2   3
   / \ / \
  4   5   6
 / \ / \ / \
0   0   0   0    <- this becomes the new "base layer", or "seed"

No mutable state; no recursion; simple to understand. As Erik Meijer would say: “baby code”.

gistfile1.txt

  type Triangle = List[List[Int]]

  def maxPathSum(tr: Triangle): Int = {
    val seed = List.fill(tr.last.size + 1)(0)
    tr.foldRight(seed)((next, acc) => {
      next.zip(acc.sliding(2,1).toList.map(pair => pair.max)).map(pair => pair._1 + pair._2)
    }).max
  }