### November 15, 2013

Michael Kozakov described the answer on his blog, and also described a few mis-steps on the way to a solution. We won’t repeat his explanation here; go there to see the whole story. Here’s the solution:

```(define (puddle land)   (let loop ((volume 0) (lmax 0) (rmax 0) (left 0)              (right (- (vector-length land) 1)))     (cond ((<= right left) volume)           ((< lmax (vector-ref land left))             (loop volume (vector-ref land left) rmax left right))           ((< rmax (vector-ref land right))             (loop volume lmax (vector-ref land right) left right))           ((< rmax lmax)             (loop (+ volume rmax (- (vector-ref land right)))                   lmax rmax left (- right 1)))           (else (loop (+ volume lmax (- (vector-ref land left)))                       lmax rmax (+ left 1) right)))))```

Here are some examples:

```> (puddle '#(2 5 1 2 3 4 7 7 6)) 10 > (puddle '#(2 5 1 3 1 2 1 7 7 6)) 17 > (puddle '#(2 7 2 7 4 7 1 7 3 7)) 18 > (puddle '#(6 7 7 4 3 2 1 5 2)) 10```

He didn’t get the job, but is now working at Amazon instead. You can run the program at http://programmingpraxis.codepad.org/tCoLS3CO.

Pages: 1 2

### 26 Responses to “Twitter Puddle”

1. Paul said

In Python. I understood “single pass” as a single scan trough the data from left to right. Then some more bookkeeping is needed, as it is not known until the last moment what the highest wall on the right will be. So, volume is calculated with the height of the wall on the left. If higher wall on the right appears, it is simple and the volume calculated so far can be added to the total volume. If never a higher wall appears, volumes have to be corrected for the lower right wall and all volume at the right of the right wall has to be subtracted again.

```def twitter_puddle(seq):
"""scan seq from left to right
there can be more that one puddle
"""
left = right = 0
number_in_puddle = 0 # number of contributionsin puddle
number_at_top = 0  # number of contributions @ last high on the right
puddle = 0    # volume in current puddle
volume = 0   # volume after last high on the right
xvolume = 0  # volume after last high on the right - splills off for last puddle
for s in seq:
if s >= right:
right = s
number_at_top = number_in_puddle
xvolume = 0
if left > right:
number_in_puddle += 1
puddle += (left - s)
xvolume += (left - s)
else: # puddle if full - right >= left -> next puddle
volume += puddle
xvolume = 0
left = right
right = 0
puddle = number_in_puddle = n_at_top = 0
else:
# last puddle - extra volume has to be subtracted
# right is lower than left, so puddle volume has to be corrected
assert left > right
puddle -= number_at_top * (left - right)
volume += puddle - xvolume
return volume

assert twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6])  == 10
assert twitter_puddle([2, 5, 1, 3, 1, 2, 1, 7, 7, 6])  == 17
assert twitter_puddle([2, 7, 2, 7, 4, 7, 1, 7, 3, 7])  == 18
assert twitter_puddle([6, 7, 7, 4, 3, 2, 1, 5, 2])  == 10
assert twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6,
2, 7, 1, 2, 3, 4, 5, 5, 4])  == 26
```
2. Graham said

A C++11 version of the answer described on his blog (not feeling too
creative today myself):

```#include <algorithm>
#include <iostream> #include <vector>

template <typename UInt>
auto calculate_volume(const std::vector<UInt>& heights) -> UInt {
auto lmax = UInt{0}, rmax = UInt{0}, volume = UInt{0};
auto left = size_t{0}, right = heights.size() - 1;
while (left < right) {
lmax = std::max(lmax, heights[left]);
rmax = std::max(rmax, heights[right]);
if (lmax >= rmax) {
volume += rmax - heights[right];
--right;
} else {
volume += lmax - heights[left];
++left;
}
}
return volume;
}

auto main() -> int {
auto puddles = std::vector<std::vector<uintmax_t>>
{{2, 5, 1, 2, 3, 4, 7, 7, 6},
{2, 5, 1, 3, 1, 2, 1, 7, 7, 6},
{2, 7, 2, 7, 4, 7, 1, 7, 3, 7},
{6, 7, 7, 4, 3, 2, 1, 5, 2},
{2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4}};
for (auto p: puddles) {
std::cout << calculate_volume(p) << std::endl;
}
return EXIT_SUCCESS;
}
```
3. informatimago said

Well, this python program doesn’t even pass its own tests!

Here is a Common Lisp solution that passes its own tests, and those of the python program:

```;; -*- mode:lisp; coding:utf-8 -*-

;;  1|
;;  2|              ___
;;  3|             |7 7|_
;;  4|    _        |    6|
;;  5|   |5|      _|     |
;;  6|   | |    _|4      |
;;  7|  _| |  _|3        |
;;  8| |2  |_|2          |
;;  9|_|____1____________|___
;; 10|  0 1 2 3 4 5 6 7 8 9
;;
;; The vector of altitudes is extended with 0's to the infinites.

(defun make-dvector (length &key (initial-element 0))
(cons (make-array length :adjustable t :initial-element initial-element)
initial-element))

(defun (setf dref) (new-value dvector i &key (initial-element 0))
(unless (< i (length (car dvector)))
(setf (car dvector) (adjust-array (car dvector) (1+ i)
:initial-element initial-element)))
(setf (aref (car dvector) i) new-value))

(defun dref (dvector i  &key initial-element)
(declare (ignore initial-element))
(if (< i (length (car dvector)))
(aref (car dvector) i)
(cdr dvector)))

(defun dref-vector (dvector)
(car dvector))

(defstruct state
(altitude 0)
(safe 0)
(lefts (make-dvector 8 :initial-element -1)))

;;        _h
;; ______|            --> move left wall x,h
;;
;; _
;;  |     _h
;;  |____|            -->  XXXX are safe, move left wall x,h
;;
;;            _h
;;     _     |
;; ___| |____|        -->  XXXX are safe, move left wall x,h
;;
;; |
;; |           _h
;; |    _     | j
;; |___| |____|      --> XXXX and XXXXXXXXXX are safe, move left wall x,j and x,h

;;       _
;;        |
;;  ...   |_h        --> current altitude := h

(defun accumulate-left (state position height)
(with-accessors ((altitude state-altitude)
(safe state-safe)
(lefts state-lefts)) state
(loop
:for a :from altitude :below height
:do (unless (minusp (dref lefts a))
(incf safe (- position (dref lefts a)))
(setf (dref lefts a) -1)))
(setf altitude height)))

(defun move-left (state position height)
(with-accessors ((altitude state-altitude)
(lefts state-lefts)) state
(loop
:for a :from height :below altitude
:do (setf (dref lefts a) position))
(setf altitude height)))

(defun process-step (state position height)
(if (< (state-altitude state) height)
(accumulate-left state position height)
(move-left       state position height)))

(defun compute-retained-water (relief)
(let ((state (make-state)))
(loop
:for position :from 0 :below (length relief)
:do (process-step state position (aref relief position))
:finally (process-step state (length relief) 0))
(state-safe state)))

(assert (= 10 (compute-retained-water #(2 5 1 2 3 4 7 7 6))))
(assert (= 17 (compute-retained-water #(2 5 1 3 1 2 1 7 7 6))))
(assert (= 18 (compute-retained-water #(2 7 2 7 4 7 1 7 3 7))))
(assert (= 10 (compute-retained-water #(6 7 7 4 3 2 1 5 2))))
(assert (= 26 (compute-retained-water #(2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4))))

(defparameter *little*  #(2 5 1 2 3 4 7 7 6))
(defparameter *2little* #(2 2 5 5 1 1 2 2 3 3 4 4 7 7 7 7 6 6))
(defparameter *91719* #(9 1 7 1 9))
(defparameter *91717* #(9 1 7 1 7))
(defparameter *91715* #(9 1 7 1 5))
(defparameter *1917191* #(1 9 1 7 1 9 1))
(defparameter *1917171* #(1 9 1 7 1 7 1))
(defparameter *1917151* #(1 9 1 7 1 5 1))
(defparameter *71917* #(7 1 9 1 7))
(defparameter *719aba917* #(7 1 9 10 11 10 9 1 7))
(defparameter *12345654321* #(1 2 3 4 5 6 5 4 3 2 1))
(defparameter *9* #(9))

(defun twice (x) (+ x x))
(assert (= 10 (compute-retained-water *little*)))
(assert (= 20 (compute-retained-water *2little*)))
(assert (= 10 (compute-retained-water (reverse *little*))))
(assert (= 20 (compute-retained-water (reverse *2little*))))
(assert (= 20 (compute-retained-water (map 'vector (function twice) *little*))))
(assert (= 40 (compute-retained-water (map 'vector (function twice) *2little*))))
(assert (= 18 (compute-retained-water *91719*)))
(assert (= 12 (compute-retained-water *91717*)))
(assert (= 12 (compute-retained-water (reverse *91717*))))
(assert (= 10 (compute-retained-water *91715*)))
(assert (= 10 (compute-retained-water (reverse *91715*))))
(assert (= 18 (compute-retained-water *1917191*)))
(assert (= 12 (compute-retained-water *1917171*)))
(assert (= 12 (compute-retained-water (reverse *1917171*))))
(assert (= 10 (compute-retained-water *1917151*)))
(assert (= 10 (compute-retained-water (reverse *1917151*))))
(assert (= 12 (compute-retained-water *71917*)))
(assert (= 12 (compute-retained-water *719aba917*)))
(assert (= 0 (compute-retained-water *12345654321*)))
(assert (= 0 (compute-retained-water *9*)))

(let ((d (make-dvector 4 :initial-element -1)))
(loop :for i :below 10 :do (assert (= -1 (dref d i))))
(loop :for i :below  7 :do (setf (dref d i) i) (assert (= i (dref d i))))
(loop :for i :from 7 :below 20 :do (assert (= -1 (dref d i))))
d)

```
4. Sam said

# a is a list, e.g. [2,5,1,2,3,4,7,7,6]
def f(a):
water = 0
i = 0
while i a[i+1]:
x = 0
j = 0
while j < a[i]:
x += 1
j = a[i+x]
dwater = (x-1)*a[i]
for k in range(i+1,i+x):
dwater -= a[k]
water += dwater
i += (x-1)
except:
life = 42
i += 1
return water

5. Sam said

sorry for that formatting. how do I make it like the codes above?

6. In C#:

```        /// <summary>
/// Gets the puddle volume.
/// </summary>
/// <param name="wall">The given wall.</param>
/// <returns>The volume of the puddles formed on the wall.</returns>
private static int GetPuddleVolume(int[] wall)
{
int volume = 0;
int currentWaterLevel = 0;

// Run through the wall.
for (int i = 1; i < (wall.Length - 1); i++)
{
// Checks if the current block of the wall is smaller than the next, meaning the puddle will potentially start.
if (wall[i] < wall[i - 1])
{
// Gets the point where the puddle should end.
int j = i;
while ((j < wall.Length) && (wall[j] < wall[i - 1]))
{
j++;
}

// Set the water level to the height of the point where the puddle should end if that's the lower point, or to the point where it started if not.
if ((wall.Length == j) || (wall[j] < wall[i - 1]))
{
currentWaterLevel = (wall.Length == j) ? wall[j - 1] : wall[j];
}
else
{
currentWaterLevel = wall[i - 1];
}
}

// Adds to the volume if current wall is lower than the current water level.
if ((currentWaterLevel - wall[i]) > 0)
{
volume += (currentWaterLevel - wall[i]);
}
}

return volume;
}
```
7. I’ve also created a little routine that displays the wall in a console screen:

```        /// <summary>
/// Displays the wall.
/// </summary>
/// <param name="wall">The wall.</param>
private static void DisplayWall(int[] wall)
{
Console.Clear();

for (int i = 0; i < wall.Length; i++)
{
for (int currentTop = 0; currentTop < (wall[i] * 2); currentTop++)
{
Console.SetCursorPosition(i * 4, Console.WindowHeight - currentTop);
Console.Write("|");
}

for (int currentTop = 0; currentTop < (wall[i] * 2); currentTop++)
{
Console.SetCursorPosition(i * 4 + 4, Console.WindowHeight - currentTop);
Console.Write("|");
}

Console.SetCursorPosition(i * 4 + 1, Console.WindowHeight - (wall[i] * 2));
Console.Write("___");
}
}
```
8. Ugh, sorry, my first post was incorrect, I missed one little extra thing in the first if:

```        /// <summary>
/// Gets the puddle volume.
/// </summary>
/// <param name="wall">The given wall.</param>
/// <returns>The volume of the puddles formed on the wall.</returns>
private static int GetPuddleVolume(int[] wall, out IList<Point> puddle)
{
int volume = 0;
int currentWaterLevel = 0;
puddle = new List<Point>();

// Run through the wall.
for (int i = 1; i < (wall.Length - 1); i++)
{
// Checks if the current block of the wall is smaller than the next, meaning the puddle will potentially start.
if ((wall[i] > currentWaterLevel) && (wall[i] < wall[i - 1]))
{
// Gets the point where the puddle should end.
int j = i;
while ((j < wall.Length) && (wall[j] < wall[i - 1]))
{
j++;
}

// Set the water level to the height of the point where the puddle should end if that's the lower point, or to the point where it started if not.
if ((wall.Length == j) || (wall[j] < wall[i - 1]))
{
currentWaterLevel = (wall.Length == j) ? wall[j - 1] : wall[j];
}
else
{
currentWaterLevel = wall[i - 1];
}
}

// Adds to the volume if current wall is lower than the current water level.
if ((currentWaterLevel - wall[i]) > 0)
{
for (int puddleFiller = wall[i] + 1; puddleFiller <= currentWaterLevel; puddleFiller++)
{
puddle.Add(new Point { X = i, Y = puddleFiller });
}

volume += (currentWaterLevel - wall[i]);
}
}

return volume;
}
```
9. Paul said

Oops. In my post above I was caught by a late edit. I forgot to rename thevariable n_at_top on line 25 into number_at_top. After changing this it works again (at least for the test cases).

10. JP said

A bunch of ‘correct’ solutions here, so I went the other way and made it pretty. :) Basically, I made a falling sand style particle simulation that drops water until all of the puddles are full then counts it up. Pretty far from efficient, but it looks nice.

11. I was trying out “pencilcode.net” (i.e. logo in the age of javascript), and wrote an animated version based on message-passing concurrency.

12. strawhatguy said

Here’s my recursive solution in Common Lisp, which easily be TCO’d away:

(defun walk-heights (area maybe-area heights current lmax)
(cond
((>= current (length heights))
area)
((> lmax (aref heights current))
(walk-heights area (+ maybe-area (- lmax (aref heights current)))
heights (1+ current) lmax))
(t
(walk-heights maybe-area maybe-area heights (1+ current) (aref heights current)))))

(walk-heights 0 0 heights 0 0))

;;; repl
CL-USER> (time (twitter-puddle #(2 5 1 2 3 4 7 7 6)))
Evaluation took:
0.000 seconds of real time
0.000004 seconds of total run time (0.000003 user, 0.000001 system)
100.00% CPU
4,376 processor cycles
0 bytes consed

10

13. strawhatguy said

hmm, that wasn’t formatted like I thought, how does one post code-blocks with the line numbers and everything?

14. strawhatguy said

and it’s not right anyway. argh sorry for the noise

15. treeowl said

I don’t know if you’re watching this, Paul, but I don’t think your solution works. The problem (I believe) will show up if the terrain looks something like 7,6,5,4,3,2,x. Your code appears to traverse the sequence strictly from left to right, holding an almost-finite amount of state. But the value of x determines how much spills in a way that depends on just how the terrain descends. This won’t work. The “official” solution gets around this by working from both ends, so it only inspects each value once but it does so out of order.

16. treeowl said

Addendum: the best way I can see to do it if you have to traverse the sequence from left to right is by using a stack to keep track of the “open” puddles. The stack will grow each time the terrain descends and shrink every time it ascends far enough to close a puddle.

17. Juan Ignacio Saba said

Here’s a simple solution. I found that if the right most position holds the highest value on the list (highest wall), then the algorithm is really simple.

So then what I do is to divide the original list into two lists that meet the above condition and do the simple algorithm on each and add the results.

How to create the two lists?

Find the max value on the entire list, then
part1 = [ 0 .. max_value ]
part2 = reverse [ max_value .. length – 1 ]

Counting water on those two lists is equivalent to counting water in the original input list.

Here’s the code: http://pastebin.com/Fb0ZvYBK

I tested it with the following scenarios:
2 5 1 2 3 4 7 7 6 => 10
2 2 5 1 3 1 2 1 7 7 6 => 17
2 7 2 7 4 7 1 7 3 7 => 18
4 6 7 7 4 3 2 1 5 2 => 10
5 2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4 => 26

This solution (slightly) violates the rule of looping through the input list only once, but it is O(n) anyway.

Cheers!
Juan Ignacio

18. Juan Ignacio Saba said

An additional comment just for the followup option that I forgot to check :P.

19. /*

There are 2 sollutions :

1. When moving from left to right, use a temp variable to store the volume accumulated in a column.
Since there is a potential overflow problem u might have to back track/store the previous values.
Back tracking would result in slightly more than one pass and storing would be complex.

Hence process the list from both the ends. Keep track of the last height point.
when both pointers meet, calculate the overflow voulme, and subract it.

2. arguably a single pass. Code is not efficent but it is much more simple.

cosider the walls to be in a x-y grid.
run a nested loop. inner loop would move from left to right ie in x-direction. outer loop would be for the next level ie y-direction.
when an empty cell is encountered after a wall, start adding to temp. if a wall is encountered , add temp to total volume.

The doubleLoop function prints out the sollution this way.
*/

package problems;

private static Integer[] input = new Integer[] {0,1,2,3,2,1,0,1,2,3,2,1,0};
//{0,1,2,3,2,1,0,1,2,3,2,1,0}
//{2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4};
//{0,1,0,1,0,3,2,1,0,1,1,0,2,0,5,0,2,3}

public static void run() {

Integer totalVoulume = 0;
boolean leftFound = false, rightFound =false, done = false;
int tempVolumeL = 0,tempVolumeR=0, leftHeight=0, rightHeight=0, leftIndex =0, rightIndex = 0;
if ( input[0] > 0 ) {
leftFound = true;
leftHeight= input[0];
leftIndex = 0;

}
if ( input[input.length-1] >0) {
rightFound = true;
rightHeight = input[input.length-1];
rightIndex = input.length-1;
}

for ( int j=0,k= input.length -1; j rightHeight ) {

totalVoulume = totalVoulume + tempVolumeR + tempVolumeL –
( (leftHeight-rightHeight) * (j- leftIndex) );

}
else if ( leftHeight < rightHeight ) {
totalVoulume = totalVoulume + tempVolumeL + tempVolumeR –
( (rightHeight – leftHeight) * (rightIndex-k) );
}
else {
totalVoulume = totalVoulume + tempVolumeR + tempVolumeL;
}
break;
}

if ( j<k)
{
j++;
if( leftFound == true && input[j] =leftHeight) {

totalVoulume = totalVoulume + tempVolumeL;
leftHeight = input[j];
tempVolumeL = 0;
leftIndex = j;

}
else if ( leftFound == false && input[j] > 0 ) {
leftFound = true;
leftHeight= input[j];
leftIndex = j;
}
if ( k-j == 1) { done = true; continue;}
}

{
k–;
if( rightFound == true && input[k] =rightHeight) {
totalVoulume = totalVoulume + tempVolumeR;
rightHeight = input[k];
tempVolumeR = 0;
rightIndex = k;

}
else if ( rightFound == false && input[k] > 0 ) {
rightFound = true;
rightHeight= input[k];
rightIndex = k;
}

if ( k-j == 1) done = true;
}
}

System.out.println(” total volume=”+ totalVoulume);
doubleLoop();
}

private static void doubleLoop() {
Integer totalVoulume = 0;
for ( int i = 1;; i++){
boolean leftFound = false, rightFound= false; int tempVolume = 0;
if ( input[0] >= i ) {
leftFound = true;
}
for ( int j=1 ; j< input.length; j++) {
if( leftFound == true && input[j] =i) {
totalVoulume = totalVoulume + tempVolume;
rightFound = true;
tempVolume = 0;
}
else if ( leftFound == false && input[j] >=i) {
leftFound = true;
}
}
if ( leftFound == false || rightFound == false)
break;
}
System.out.println(” double loop –total volume=”+ totalVoulume);
}
}

20. Ruby version I bashed out the day after getting this question, unfortunately I’m a sysadmin really so I floundered around a bit in the interview. No promise that this is right, it spits out an array of the depths so some for the volume…

#!/usr/bin/ruby

print “Enter terrain heights (space separated): ”

terrain = gets.chomp.split(” “).map { |s| s.to_i }
rainDepth = Array.new(terrain.length)

lInd=0
lMaxInd=0

rInd=terrain.length-1
rMaxInd=terrain.length-1

i=0

while i < terrain.length do

if terrain[lInd] terrain[lMaxInd] then lMaxInd = lInd end
rainDepth[lInd] = terrain[lMaxInd] – terrain[lInd]
lInd+=1
else
if terrain[rInd] > terrain[rMaxInd] then rMaxInd = rInd end
rainDepth[rInd] = terrain[rMaxInd] – terrain[rInd]
rInd-=1
end

i+=1
end

puts “#{rainDepth}”

21. Andrew said

This works and is short?

“`
height = max(wall)
total = 0
for x in range(1, len(wall)-2):
lowest_wall = min(max(wall[:x]), max(wall[x+1:]))
if lowest_wall > wall[x]:
total += lowest_wall – wall[x]

assert(twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6]) == 10)
“`

22. Chris Gruszka said

Here is Python code that completes the task in a single pass. I consider calling max() an additional pass of the list. https://wiki.python.org/moin/TimeComplexity

```def twitter_puddle(t):
state = {}
volume = 0
left_bank = last = t[0]
for cur in t[1:]:
if cur > last:
# height went up
if cur > left_bank:
# height of current left bank went up
left_bank = cur
# save any amount now trapped
# only need to save/reset between last and cur (not 0 and cur) -- reduces dictionary size
for x in range(last,cur):
# use .get for default of 0 if entry does not exist
volume += state.get(x, 0)
state[x] = 0
if cur < left_bank:
# increment area held by left bank but not saved
for x in range(cur,left_bank):
state[x] = state.get(x, 0) + 1
last = cur
return volume
```
23. Chris Marasti-Georg said

JS version to handle arbitrarily large streams (would need to change volume data type at some point, and the walls in the accumulator could get large for a long sequence of descending steps).

``` function processWall(value, accumulator) { var volume = accumulator.volume, walls = [], wallIndex = 0, wall, lastWall;```

``` while(wallIndex value) { walls.push([wall[0], wall[1]+1]); } else if(wall[0] < value && lastWall) { volume += lastWall[1] * (Math.min(value, lastWall[0]) - wall[0]); } lastWall = wall; ++wallIndex; } walls.push([value, 0]); return {volume: volume, walls: walls} } ```

```function calculateVolume(puddle) { var accumulator = { volume: 0, walls: [] }; for(var i = 0; i < puddle.length; ++i) { accumulator = processWall(puddle[i], accumulator); } return accumulator.volume; } ```

24. My solution goes from right to left and always assumes that there’s a big maximum and many local maximums, until there’s a new big maximum.

Let’s say the big maximum is 7, then we create 2 new arrays. One to keep track of how many steps were taken being less than 7,6,5,4,3,2,1. Another array keeps track of the volume less than 7, 6,5,4,3,2,1. If there’s a new local maximum, say 5. We calculate the volume as steps[5]*newmax – accumvol[5]. If there’s a new maximum, say 10. We ignore the local sums, and take the volume between big maxs (between 7 and 10).

Code in java, working and with some tests:
http://pastebin.com/5EF06zGc

25. hakim said

i have a solution made with netbeans and javafx you can watch the demo on youtube :
http://speedysoft.blogspot.com/2015/06/puddles-with-javafx-programmingpraxis.html