/gist:59af0fd5bddbed1a0399 Secret
| /* package whatever; // don't place package name! */ | |
| import java.util.*; | |
| import java.lang.*; | |
| import java.io.*; | |
| /* Name of the class has to be "Main" only if the class is public. */ | |
| class Ideone | |
| { | |
| public static void main (String[] args) throws java.lang.Exception | |
| { | |
| int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6}; | |
| System.out.println(calculateVolume(myIntArray)); | |
| } | |
| public static int calculateVolume(int[] land) { | |
| int leftMax = 0; | |
| int rightMax = 0; | |
| int left = 0; | |
| int right = land.length - 1; | |
| int volume = 0; | |
| while(left < right) { | |
| if(land[left] > leftMax) { | |
| leftMax = land[left]; | |
| } | |
| if(land[right] > rightMax) { | |
| rightMax = land[right]; | |
| } | |
| if(leftMax >= rightMax) { | |
| volume += rightMax - land[right]; | |
| right--; | |
| } else { | |
| volume += leftMax - land[left]; | |
| left++; | |
| } | |
| } | |
| return volume; | |
| } | |
| } |
Yet another solution: https://gist.github.com/syfou/7364514
It uses recursion: I tried to go for a readable and a painless, quickly implemented solution rather than something more clever.
my dumb but working version
def get_volumn(seq):
total = 0
for level in xrange(max(seq)-1, 0, -1):
row = [ 1 if row-level > 0 else 0 for row in seq]
first = row.index(1)
last = len(row) - row[::-1].index(1) - 1
if last - first > 0:
total += row[first:last].count(0)
return total
if '__main__' == __name__:
s1 = [2,5,1,2,3,4,7,7,6]
print get_volumn(s1)
s2 = [ 2, 5, 1, 3, 1, 2, 1, 7, 7, 6]
print get_volumn(s2)
mkozakov's solution is quite perfect, no allocations, no stack uage.
single pass, recursive in python: https://gist.github.com/thulka/7429806
btw, est, your solution wrong: [7,0,5,0,7,0] should be 16, yours returns 14. also you might have hidden loops in the list selectors, so not perfectly single pass. finally, it was about an elegant solution, not just a dumb working one. a simple working one, non single pass would be:
for each bin the water = min(leftmax, rightmax) - current height
My first thought was to use a spreadsheet. Here's that in Haskell:
import Control.Lens
import qualified Data.Vector as V
import Data.Vector ((!),Vector)
-- | Calculate the water volume.
water :: Vector Int -> Int
water = V.sum . V.map (view _3) . loeb . V.imap cell where
cell i x xs
| i == 0 = edge _1
| i == V.length xs - 1 = edge _2
| otherwise = col i x xs
where edge ln = set l (view l (col i x xs)) (x,x,0)
where l = cloneLens ln
col i x xs = (l,r,min l r - x)
where l = neighbor _1 (+)
r = neighbor _2 (-)
neighbor l o = max x (view l (xs ! (i `o` 1)))
It makes a vector where the value of each cell is calculated based on the two neighboring cells. Except edges, who only have one neighbor. It's a direct way of writing how I thought of the problem statement:
- I'm a cell. My puddle's extent is determined by finding the largest cell to the left of me, and the largest to the right of me.
- My potential volume is calculated by taking the minimum height of said two cells.
- My actual volume is calculated by subtracting from that my height.
- If I'm on the edge (either side), then my height on one side is restricted to me, and my volume is zero.
Done.
Oh, the loeb function is from here:
-- | Map over a structure, passing in itself.
loeb :: Functor f => f (f b -> b) -> f b
loeb x = fmap (\f -> f (loeb x)) x
Short, single-pass python solution
q = [2,5,1,3,1,2,1,7,7,6]
def solve(heights):
water = [0]*len(heights)
total = 0
runoff = 0
for i,height in enumerate(heights):
if i == 0:
continue
above = max(height, heights[i-1] + water[i-1]) - height
water[i] = above
if water[i] == 0:
runoff = 0
else:
runoff += water[i]
return sum(water)-runoff
print q, solve(q)
@neuronsguy That's an incomplete solution, it only works in one direction. E.g. solve([6,7,7,4,3,2,1,5,2]) → 0
@DrewFitz Only works properly in one direction.
print puddle([2,5,1,2,3,4,7,7,6]) → 10
print puddle([6,7,7,4,3,2,1,5,2]) → 11
@HollyGurza Only works properly in one direction.
You guys really need to think about the problem in both directions.
@igor47 Only works in one direction.
Thanks for the fun problem :-)
I ended up solving it recursively, working from the base cases up to a general solution, and then I converted the recursive algorithm into the following Python function taking a height array A. For a problem of size len(A) = N, the function requires O(N) time and O(1) space. For a full derivation of the algorithm, starting from first principles, see the (extensive) discussion in the source code:
https://github.com/tmoertel/practice/blob/master/water-holding-capacity/water_holding_capacity.py
def water_holding_capacity_iterative(A):
(i, j) = (0, len(A) - 1)
lm = rm = vol = 0
# while segments remain, consume left- or right-end segment
while i <= j:
if lm < rm:
vol += max(0, lm - A[i])
lm = max(lm, A[i])
i += 1
else:
vol += max(0, rm - A[j])
rm = max(rm, A[j])
j -= 1
return vol
python:
numbers = [6,7,7,4,3,2,1,5,2]
def vol(numbers):
prev_max = 0
total = 0
for n in numbers[0:-1]:
if n > prev_max:
prev_max = n
else:
total = total + (prev_max-n)
total_1 = total
total = 0
numbers = numbers[::-1]
prev_max = 0
for n in numbers[0:-1]:
if n > prev_max:
prev_max = n
else:
total = total + (prev_max-n)
total = min(total_1,total)
return total
or one-way loop in python
def vol2(numbers):
prev_max_left = 0
prev_max_right = 0
total_left = 0
total_right = 0
for n in xrange(0,len(numbers)-1):
if numbers[n] > prev_max_left:
prev_max_left = numbers[n]
elif numbers[n] < prev_max_left:
total_left = total_left + (prev_max_left - numbers[n])
if numbers[-1-n] > prev_max_right:
prev_max_right = numbers[-1-n]
elif numbers[-1-n] < prev_max_right:
total_right = total_right + (prev_max_right - numbers[-1-n])
return min(total_left,total_right)
Another Haskell solution, O(1) space when switched to foldl' and strict tuples:
water is = w1 + w2 + t1 - length is * m1 where
(t1,m1,w1) = foldl f (0,0,0) is
(t2,m2,w2) = foldl f (0,0,0) $ reverse is
f (t,m,w) i = (t+i, max m i, w + max 0 (m-i))
Elegant one liners are cool! Sadly mine is not one of those.
I start by calculating what the maximum amount of water that could be held is. Then, I go level by level and remove blocks that would have fallen off. Think of it as if you dipped a lego structure into a bathtub and pulled it out: every hole is filled at first, but as you pull it out of the water, each level loses some water.
rightMax should be equals land.length - 1
Short JS solution:
https://gist.github.com/allumbra/8035125
1 pass. Keeps track of last time wall height was seen.
Another Python solution - https://gist.github.com/joneschris/8049901
Here is a solution using C# and one lambda
using System;
using System.Linq;
namespace TwitterInterviewAnswer
{
class Program
{
static void Main(string[] args)
{
//the data
int[] wallHeights = {2, 5, 1, 2, 3, 4, 7, 7, 6};
//the lambda expression
Func<int[], int> volume = walls => walls.Skip(1).Take(walls.Count() - 2)
.Select((s, i) => new {s, i})
.Select(v => new[]
{
walls.Take(v.i + 1)
.Max(),
walls
.Skip(v.i + 2)
.Max()
}
.Min() - v.s)
.Where(w => w > 0)
.Sum();
//the output
Console.WriteLine("The volume is: {0}", volume.Invoke(wallHeights));
Console.ReadKey();
}
}
}
@jbojcic your code won't work for something like [7,3,2,4].
You will fill in water that should spill out
@mkozakov it won't fill up water that should spill out but it will spill out everything, which is also wrong
# Actually the original implementation is as following which is done in n-pass:
def water_vol_orig(a):
lv = rv = -1
result = lmax = rmax = l = 0
r = len(a)-1 # no pass on array
while (l < r):
lv = a[l]
if lv > lmax:
lmax = lv
rv = a[r]
if rv > rmax:
rmax = rv
if lmax >= rmax:
result += rmax - rv
r -= 1
else:
result += lmax - lv
l += 1
return result
# This implementation avoids the lookup for the max item in the array to finish in n-pass.
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java
# indexed access to an array is expensive, using enumerators is far more effective.
# So more efficient way of doing this in Python may be:
#1) find the max item
#2) approach to max item from left and right.
def water_vol_fast(a):
def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
max_idx = max_val = 0
for i, v in enumerate(a):
if v > max_val:
max_val = v
max_idx = i
return max_idx
def _volp(x):
max = result = 0
for e in x:
if e > max:
max = e
else:
result += max - e
return result
imax = _imax(a) # n-pass
return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass
# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index
# based access to any array.
# If these are profiled, one can see the difference:
# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.
# You can test above by:
# for test:
import random
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a)
Hm... tried to run original solution against the data with 3 maximums and it didn't work...
public class TestTest {
public static void main (String[] args) throws java.lang.Exception
{
int[] testData1 = {1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
int expectedResult1 = 17;
int[] testData2 = {4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
int expectedResult2 = 40;
int[] testData3 = {1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
int expectedResult3 = 40;
int[] testData4 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
int expectedResult4 = 41;
int[] testData5 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};
int expectedResult5 = 61;
test(expectedResult1, testData1);
test(expectedResult2, testData2);
test(expectedResult3, testData3);
test(expectedResult4, testData4);
test(expectedResult5, testData5); //[ERROR] Test failure! Expected: 61 but was: 62
}
public static void test(int expected, int[] array){
int result = calculateVolume(array);
if(result != expected) {
System.out.println("[ERROR] Test failure! Expected: " + expected + " but was: " + result);
} else {
System.out.println("[INFO] Test successful!");
}
}
public static int calculateVolume(int[] land) {
int leftMax = 0;
int rightMax = 0;
int left = 0;
int right = land.length - 1;
int volume = 0;
while(left < right) {
if(land[left] > leftMax) {
leftMax = land[left];
}
if(land[right] > rightMax) {
rightMax = land[right];
}
if(leftMax >= rightMax) {
volume += rightMax - land[right];
right--;
} else {
volume += leftMax - land[left];
left++;
}
}
return volume;
}
}
@Mak-Sym Original implementation returns 51 and your expectation should not be 61. 51 is the correct volume for input set: {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3}.
Please do not forget the fact that water will spill from left/right if there is no surrounding block.
Thanks!
There is typo in my post - sorry about that
I meant this one:
int[] testData5 = {2, 1, 3, 5, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3}; //should be 61, but was 62
Whoops - found bug in my calculations - it should be 62 (not sure how I missed this during numerous manual verifications and my v1 impl :) )
unspoiled solution; I think mine works the same way as yours.
https://gist.github.com/Pranz/45eff77d201ef1e2dc61
This seems to work ...
https://gist.github.com/bourneagain/0cb90851106756746933
here is an alternate but simple nlog(n) solution
https://gist.github.com/isaiah-perumalla/105b72e6b99f69b599ec
just an F# solution for aestetic pleasure
let oneWayCapacity a =
let mutable max = 0
a |> List.map (fun e -> if e > max then max <- e; 0 else max - e)
let totalCapacity a =
let aL = a |> oneWayCapacity
let aR = a |> List.rev |> oneWayCapacity |> List.rev
List.map2 min aL aR |> List.sum
let test a =
a |> totalCapacity |>
printfn "totalCapacity %A = %i" a
let () =
[1; 2; 1; 3; 5; 3; 1; 2; 4; 1] |> test
[2; 5; 10; 7; 3; 8; 5; 2] |> test
[2; 5; 1; 2; 3; 4; 7; 7; 6] |> testhttps://gist.github.com/harry-tallbelt/cc236e710c9edf858853c118bc38c9ad
So does this work for:
4,0,0,4,0,4,0,0,4,2
?