Pavel Fatin

About a year ago I happen to devise a solution (spoiler!) to a puzzle latter known as “Twitter’s waterflow problem”. Despite the number of alternative solutions, my original approach still stand out in its own way, and can be used to demonstrate a few peculiar things about recursion and list folding.

The puzzle probably existed before Twitter itself, yet it received great popularity after Michael Kozakov’s post about his interview at Twitter. As Reddit commenter noticed, “luxury of time and hindsight are wonderful things indeed”, so here goes the problem specification.

Specification

We are given a list of numbers, representing walls of different height. The goal is to determine how much rain water can be accumulated between the walls.

Here’s a visual representation of [2,5,1,2,3,4,7,7,6]:

In this case, the amount of accumulated water is 10 (note that there are no implicit side walls).

Requirements

Because of the puzzle popularity, many solutions, in different programming languages, were posted:

• Comments to Michael’s Gist (spoiler!)
• Comments on Reddit (spoiler!)

Approach, conciseness, performance and even correctness of those solutions vary greatly. What kind of solution do we want? It must be:

• efficient (O(n)time complexity),
• concise (1-5 lines of code),
• compatible with linear-access sequences (like list),
• preferably “functional”.

Now you may take your time and try to solve this problem by yourself before reading any further. In this way, you will not only enjoy a rather cute puzzle, but be able to comprehend with greater clarity what I’m going to show next.
Continue reading →