Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# opyate/Explanation.md

Last active Dec 14, 2018
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 }
to join this conversation on GitHub. Already have an account? Sign in to comment