I've recently applied to Toptal and sucked miserably at the entry exam. My algo chops were blunt, and I thought I'd rectify it by revisiting Project Euler. With the startup last year and the baby this year I just haven't been able to find the time for programming challenges, but that has to change.

Looking at my Project Euler source directory, I saw that I left it at problem 17, so next up will be 18. The problem description, however, mentions that the problem repeats itself as 67, but with a bigger input that will run 20 billion years if you go the brute force route.

I worked a little on this problem last night and decided to by-pass the brute force solution altogether. It was a bit late, though, and I pulled my eyelids open far enough to make it to bed. I then went on to dream about the damn problem all night. I knew there had to be a simple bottom-up fold-based solution, and the *voila* moment came for me when I realised I had to seed the fold computation with the base layer in the triangle.

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 }

# An explanation

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 current 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. 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".