Skip to content

Instantly share code, notes, and snippets.

@opyate

opyate/Explanation.md

Last active Dec 14, 2018
Embed
What would you like to do?
The gist behind Project Euler 18 and 67.

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

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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment