## Twitter Puddle

### November 15, 2013

We have today an interview question from Twitter:

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 1X1. 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. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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.

A C++11 version of the answer described on his blog (not feeling too

creative today myself):

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:

# 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

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

In C#:

I’ve also created a little routine that displays the wall in a console screen:

Ugh, sorry, my first post was incorrect, I missed one little extra thing in the first if:

http://codepad.org/FkazvRJz

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).

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.

Linky: jverkamp.com: Twitter puddle

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

http://coldtortuga.pencilcode.net/home/twitterpuddle

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)))))

(defun twitter-puddle (heights)

(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

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

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

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.

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.

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

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

/*

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;

public class TwitterPuddle {

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);

}

}

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}”

This works and is short?

“`

def twitter_puddle(wall):

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]

return total

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

“`

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

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;

}

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