« Boston Python puzzles

Twitter Puddle

[We found this puzzle here: Twitter Puddle on programmingpraxis]

Consider the following picture:

In this picture we have walls of different heights. This picture is represented by an array of integers, where the value at each index is the height of the wall. The picture above is represented with an array as [2,5,1,2,3,4,7,7,6].

Now imagine it rains. How much water is going to be accumulated in puddles between walls?

We count volume in square blocks of 1×1. So in the picture above, everything to the left of index 1 spills out. Water to the right of index 7 also spills out. We are left with a puddle between 1 and 6 and the volume is 10.

Your task is to write a program to compute the volume of water in the puddle; you should strive for an algorithm that completes the task in a single pass.

Solutions

• Brett Smith's solution is puddles.py
• Edward Stronge's solution is twitter_puddle.py
• Ned Batchelder's solutions are puddle.py
• Andrew Ross's solutions are twitter_puddle.py
• Steve Witham's solutions are twitter_puddle.ipynb
• Ankur Aggarwal's solution is TwitterPuddle.py
• Will Sutton's solution is twitterpuddle.ipynb

If you have a solution you'd like to share see the Solutions page for instructions.