Monday, November 18, 2013

My solution to the Twitter waterflow problem

The Twitter waterflow problem originated in this post. After becoming aware of the existence of functional solutions in this other post, I decided to roll my own in Haskell before looking at them.

It turned out to be more tricky than I had expected. The first version of the algorithm was hideously ugly and verbose, and I couldn't make it to work. I tried a new approach and came up with the following:

I haven't tested it extensively but I think it works.

I "compress" consecutive columns of equal height, so instead of working with a list of heights, I work with a list of (height,width) pairs. The initial list with uncompressed columns is created in the (zip l (repeat 1)) expression.

I traverse the list from left to right, carrying an accumulator parameter for the volume, and also an axiliary list of the "high" columns visited so far. These columns can potentially enclose water if another sufficiently high column is encountered on the other side of a "valley".

The algorithm ensures that the columns in the auxiliary list (a stack, really) are strictly increasing in height, and have all been "compressed".

Lines 3-4 purge columns that go "uphill" from the left border, since these columns can't possibly contain a valley. Once we find the first "peak", we put it into the auxiliary list.

Line 7 compresses "valley floors".

Line 8 identifies "valleys" whose floors have already been compressed. We find how much water that portion of the valley will hold by multiplying the width of the floor with the height of the lowest wall. We add the volume to the accumulator and then fill that portion of the valley with concrete (so to speak) to avoid double-counting that volume in future iterations.