99.99% of Sup Forums can't solve this

99.99% of Sup Forums can't solve this

>write a function that interprets a given array as a histogram and outputs the area of water the histogram could hold. water can flow out of of bounds as well as out of any histogram bar of height zero.

Attached: problem.png (815x542, 71K)

Other urls found in this thread:

stackoverflow.com/a/24415547
leetcode.com/articles/trapping-rain-water/
issues.scala-lang.org/browse/SI-1512
twitter.com/NSFWRedditImage

Interesting. Gonna do it.

this is the second histogram related post in this last week
we're not doing your homework, retard

This.

That said: Loop through to find decreasing values, with a break statement in case of 0 value. Once increasing values are found, stop the loop when it reaches the original value(orignal height). That's pool 1, continue for other pools.

I already solved it though

someone posted that fizzbuzz thread a while back and I enjoyed reading through it - so I started that histogram thread a couple of days later. enjoyed that one as well, so here's a more complicated variant.

var area = input => Array(Math.max(...input)).fill(0).map((_, row) => input.map(column => (column == 0) ? 'X' : (column - row > 0) ? '1' : '0').join('').match(/1[0]+1/g)).join().match(/0/g).length;


I'll be the first to admit that my code is pure clusterfuck, but it works and I was determined to get it down to one line

why is there no water in the middle?

>water can flow out of of bounds as well as out of any histogram bar of height zero

Because you should learn to read.

how do you find pools ?

import sys

def gps( d ) :
ps = [ ]
p1 = 0
p2 = 0
while p2 < len( d ) :
if d[ p2 ] == 0 :
p = d[ p1 : p2 ]
if( len( p ) != 0 ) :
ps.append( p )
p2 += 1
p1 = p2
continue
p2 += 1
if( len( d[ p1 : ] ) != 0 ) :
ps.append( d[ p1 : ] )
return ps

def gv( ps ) :
v = 0
for p in ps :
for i in range( 1, len( p ) - 1 ) :
c = min( max( p[ : i ] ), max( p[ i + 1 : ] ) ) - p[ i ]
v += c if c > 0 else 0
return v

def main( ) :
d = [ 2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0 ]
print( gv( gps( d ) ) )
return

if __name__ == "__main__":
sys.exit( main( ) )

I thought of a nice divide-and-conquer method that partitions the list by the largest element and then goes about calculating the sum of the two sides, but I now think we can do this in linear time (my method was n lg n)

sounds interessting

I could probably do it if I spent the whole day working on it (I'm only an amateur coder), and that would actually be quite fun but I don't have the time atm.

The O(n) solution is trivial and intuitive. The last one at least made you think, while this one can be solved by any script kiddie that has never taken a single class or read a book about algorithms.

>let's post it like a challenge, Sup Forums will surely solve my homework for me!

function area(heights) {
const lefts = [0];
for (const [i, height] of heights.entries()) {
lefts.push(height == 0 ? height : Math.max(height, lefts[i]));
}
lefts.reverse();
let total = 0;
let right = 0;
for (const [i, height] of heights.reverse().entries()) {
total += height == 0 ? 0 : Math.max(0, Math.min(lefts[i], right) - height);
right = height == 0 ? height : Math.max(right, height);
}
return total;
}

console.log(area([2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0]));

entry level bullshit

turn to integration by parts in your calc textbook

How about rewrite your fucking question you dolt.

Nice way to get someone to do your work for you. Nice user, nice.

Attached: 1521592522600.gif (640x360, 2.52M)

>it's so easy I won't even bother describing the algorithm
go kill yourself

triggered?
And yes is right. It's easy as fuck

Nice way to hide that you can't do shit. Nice user, nice.

ez pz
#include
#include

int main(int argc, char** argv) {
if (argc bound) {
area += pool;
pool = 0;
bound = a;
}

int d = a - prev;
if (d > 0 && pool > 0) {
pool -= d;
area += d;
}
prev = a;
}

printf("%d\n", area);
}

>javascript soyboy in charge of programming
The web was a mistake.

A decrease in value followed by a increase until the original value(height) is reached is a pool.

The sum of the differences between each of the decreased value from the original value, gives you the "area".

A fun problem, can't think of any real world application for it though

partition it on the 0's
call on the partition the next function

init kill partition
if found -> fill it and recursive call on the remaining segment

O(n)

>99.99% of Sup Forums can't solve this
>says this while being part of the 99.99%

Nice try pajeets.
Won't work on something like 4 2 3 1 2

Why won't my pool thing work on that? You keep the counter running until the original value/height is reached(4 in your case). The loop is broken if: original value reached or 0 reached or the end is reached.

I'm sure there are other flaws though.

man, you're shit at tetris user

Why don't you try it Pajeet?

Find peaks, find valleys, discard valleys with value 0, find all peak/valley/peak trios.

but your own image is wrong, there are many places where water could be holded .

Thays very very good!!

Im talking about the quads.

Thank you, friend.
I appreciate these ego stroking threads.
I hope this becomes a regular thing.

3 1 2 1 3
Don't call us, we'll call you if we need anything.

>that readability

It's intended. To let OP have a fun time when he will be explaining what the fuck is going on in "his" code.

Nice try Pajeet. Doesn't work with 3 1 2 1 3.

Even if he were to copy if he would immediately fail for using a O(n^3) algorithm Rajesh.

It clearly splits into [3 1 2] and [2 1 3]
I did say to find the trios

Don't call us, we'll call you.

>water can flow out of of bounds as well
int water = infinity

wut?
[3, 1, 2, 1, 3]
5

Where does it say "should be optimal solution"?

me n my recursion can do this

def _find_volume_one_way(histogram):
"""Find pools where the left border is less than the right border of a pool."""
total_volume = 0
current_pool_height = next(histogram)
current_pool_volume = 0
for height in histogram:
if height == 0:
current_pool_volume = 0
elif height < current_pool_height:
current_pool_volume += current_pool_height - height
else:
# we've reached the end of a pool, add its volume to the total volume and reset
# everything in preparation for the next pool
total_volume += current_pool_volume
current_pool_height = height
current_pool_volume = 0
return total_volume


def find_volume(histogram):
"""Find the total volume of water that a histogram can hold."""
# _find_volume_one_way(histogram) only detects pools where the left border is less than the
# right border. Instead of making that function more complex, we just run it once on the
# original histogram, and once on the reversed version. this works because a greater left
# border and lesser right border will switch places if we reverse the histogram, allowing
# _find_volume_one_way(histogram) to detect the pool
return _find_volume_one_way(iter(histogram)) + _find_volume_one_way(reversed(histogram))


print(find_volume((2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0)))

>>> find_volume((3, 1, 2, 1, 3))
10

Nice try Pajeet.

Itt: the recruiters dont get algorithms either

def _find_volume_one_way(histogram):
"""Find pools where the left border is less than the right border of a pool."""
total_volume = 0
current_pool_height = next(histogram)
current_pool_volume = 0
for height in histogram:
if height == 0:
current_pool_volume = 0
elif height < current_pool_height:
current_pool_volume += current_pool_height - height
else:
# we've reached the end of a pool, add its volume to the total volume and reset
# everything in preparation for the next pool
if height == current_pool_height:
# to avoid counting twice pools where the left boundary is equal to the right
# boundary because this function will detect such pools in both regular
# and reversed histograms
total_volume += 0.5 * current_pool_volume
else:
total_volume += current_pool_volume
current_pool_height = height
current_pool_volume = 0
return total_volume


def find_volume(histogram):
"""Find the total volume of water that a histogram can hold."""
# _find_volume_one_way(histogram) only detects pools where the left border is less than the
# right border. Instead of making that function more complex, we just run it once on the
# original histogram, and once on the reversed version. this works because a greater left
# border and lesser right border will switch places if we reverse the histogram, allowing
# _find_volume_one_way(histogram) to detect the pool
return _find_volume_one_way(iter(histogram)) + _find_volume_one_way(reversed(histogram))


print(find_volume((2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0)))
print(find_volume((3, 1, 2, 1, 3)))

rainfall xs = sum (zipWith (-) mins xs)
where mins = zipWith min maxl maxr
maxl = scanl1 max xs
maxr = scanr1 max xs

>>> find_volume((2, 1, 0, 2))
1


Does not work if a value is 0. Apply yourself.

>Apply yourself
>implying I didn't just pasta from stackoverflow.com/a/24415547
>Does not work if a value is 0
rainfall [1,0,1,3,2,4,5,4,1,2,0]
8
[/code
Got a better counterexample?

*Main> rainfall [2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0]
14

It doesn't even get the example in the OP right.
Embarrassing. You will need to refund us for wasting the interviewer's time.

>implying I'm even trying

Attached: came-here-to-laugh-at-you.jpg (500x375, 15K)

I don't even know what a histogram is :^)

I have no idea what a histogram is or does sorry.

leetcode.com/articles/trapping-rain-water/
"but with zeros"

This thread is a great example of why you should write tests for your crappy code before calling it done

>help op's homework: the thread

>A fun problem, can't think of any real world application for it though
Estimating rainwater pooling given an array of heigh data.
Always assume that all puzzles have some practical application tied to it, no matter how contrived they may seem at first.

Attached: flood-extent-map-south-websm.jpg (1500x1061, 353K)

Hey I'm the guy that posted the fizzbuzz. Might be doing an inverse fizzbuzz thread soon when I finish it

are we assuming that cases like pic related would retain water?

Attached: garph.jpg (640x400, 11K)

learn to read

Fugly+slow brute-force O(n^2) one, based on the original with an added "until you hit a zero" for the max L/R scans.
def rainfall(xs: Seq[Int]) = {
def max0l(xs: Seq[Int], from: Int) = (xs.take(from).reverse.takeWhile{_!=0} :+ 0).max
def max0r(xs: Seq[Int], from: Int) = (xs.drop(from).takeWhile{_!=0} :+ 0).max
val maxl = xs.indices.map{max0l(xs,_)}
val maxr = xs.indices.map{max0r(xs,_)}
val mins = (maxl, maxr).zipped map {_ min _}
(for ((x,i)

Who the fuck writes ones like that? My fucking eyes thought that was a 7 or a 9

O(n) time, O(n) space version - basically a "but reset max on 0" version of :
def rainfall(xs: Seq[Int]) = {
val maxl = xs.scanLeft (0){(max, x) => if (x==0) 0 else x max max}.tail
val maxr = xs.scanRight(0){(x, max) => if (x==0) 0 else x max max}.init
val mins = (maxl, maxr).zipped map {_ min _}
(mins, xs).zipped.map{_-_}.sum
}

Too lazy to do anything but a smoke test though:
@ rainfall(Seq(2,1,3,3,2,1,0,4,3,1,2,6,4,5,0))
res1: Int = 8

(input => {
input.push(0)
let water = 0
let startIndex = -1
let startHeight = 0
let prevHeight = 0
let increasing = false
for (let [i, height] of input.entries()) {
let leak = height === 0 && prevHeight > height && increasing
if ((height > 1 && height >= startHeight) || leak) {
if (startIndex > -1) {
for (let j = i - (leak ? 2 : 1); j > startIndex; j--) {
water += Math.max(0, (leak ? prevHeight : startHeight) - input[j])
}
}
startIndex = i - (leak ? 1 : 0)
startHeight = (leak ? prevHeight : height)
increasing = false
} else if (height > prevHeight) {
increasing = true
}
if (height === 0) {
startIndex = -1
startHeight = 0
prevHeight = 0
increasing = false
}
prevHeight = height
}
return water
})([2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0])

I have no idea what language you are using but that won't even work on the most basic of inputs such as 1 2 1

Too simple, so I didn't even bother writing it in a proper language.
hist = c(2,1,3,3,2,1,0,4,3,1,2,6,4,5,0)

histofill = function(hist){
len = length(hist)
water = 0
diff = 0
start = 0
for(i in 2:len){
if(hist[i-1] > hist[i] && start == 0){
start = i-1
}
if(start > 0){
if(hist[i] == 0){ #flow out
start = 0
diff = 0
} else if(hist[i] > hist[start]){ #end of climb
water = water + diff
start = 0
diff = 0
} else if(hist[i] > hist[i-1] && hist[i] < hist[start]){ #local minimum
local_diff = hist[i] - hist[i-1]
water = water + local_diff
diff = diff - local_diff
diff = diff + hist[start]-hist[i]
} else { #count space
diff = diff + hist[start]-hist[i]
}
}
}
return(water)
}

histofill(hist)

>Too simple, so I didn't even bother writing it in a proper language so people can't run it on basic test cases and immediately tell that it's wrong

@ rainfall(Seq(1,2,1))
res1: Int = 0

Have I misread the problem statement?

What language

You should be able to find it easily via e.g. Google and a few of the keywords in the code I posted.

>I didn't even bother writing a (tested-to-be-)correct solution
ftfy

Nevermind. Scala's scan methods are just retarded.

Not having scanl1/scanr1 is occasionally annoying, yes.
What annoys me more is the lack of zipWith.

Tweaked for the current problem:
rainfall xs = sum (zipWith (-) mins xs)
where mins = zipWith min maxl maxr
maxl = scanl1 (\mx x -> if(x==0) then 0 else max mx x) xs
maxr = scanr1 (\x mx -> if(x==0) then 0 else max mx x) xs

rainfall [2,1,3,3,2,1,0,4,3,1,2,6,4,5,0]
8

ded tred

Inspired by , with the base code (without the water leaking out of zeros condition) taken from geeksforgeeks.


def findWater(arr):
n = len(arr)

# left[i] contains height of tallest bar to the
# left of i'th bar including itself
left = [0]*n

# Right [i] contains height of tallest bar to
# the right of ith bar including itself
right = [0]*n

# Initialize result
water = 0

# Fill left array
left[0] = arr[0]
for i in range(1, n):
if arr[i] == 0:
left[i] = 0
else:
left[i] = max(left[i-1], arr[i])

# Fill right array
right[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
if arr[i] == 0:
left[i] = 0
else:
right[i] = max(right[i+1], arr[i])

# Calculate the accumulated water element by element
# consider the amount of water on i'th bar, the
# amount of water accumulated on this particular
# bar will be equal to min(left[i], right[i]) - arr[i] .
for i in range(n):
water += min(left[i], right[i]) - arr[i]

return water

Do your own homework faggot

ok I am learning js right now so this would be good practice to program in js
I'll commit my first try soon

>making clickbait on Sup Forums
actually consider suicide

var heights = [2,1,3,3,2,1,0,4,3,1,2,6,4,5,0]

function calcRain(heights){
let section = [];
let rainsquares = 0;

for(let i=0;i=section[0]&§ion.length>1){
for(let x=1; x

too much for you?

Is "axis" a synonym of "bar"?

system.out.println("hello world")

lol that's easy
function calculateWater([2,1,3,3,2,1,0,4,3,1,2,6,4,5,0]){
return 8;
}

>knows the physics of water
>still doesn't realize the world is flat

son im disappoint

Wait, how does that account for water flowing out at 0?

They considered it and introduced something arguably better:
> Instead of zipWith, there's now zipped
issues.scala-lang.org/browse/SI-1512

Yup, that's what I used in and .
I guess I'm just whining about the syntax, but Odersky makes a good point.
Thankfully he's a pragmatist.

giving the instructions makes the problem trivial. just giving the picture is realer

post code then

def foo(arr):
total = 0
left = 0
while (left < len(arr)):
while (left < len(arr) and arr[left]==0):
left += 1

right = left + 1
sub = 0
while (right < len(arr) and arr[left] > arr[right]):
#reverse direction
if (arr[right] == 0 or right+1 == len(arr)):
sub = 0
tmpright = right
tmpleft = right - 1
while (tmpleft != left):
if (arr[tmpright] > arr[tmpleft]):
sub += arr[tmpright] - arr[tmpleft]
else:
tmpright = tmpleft
tmpleft -= 1
break
else:
sub += arr[left] - arr[right]
right += 1
total += sub
left = right
return total

arr = [2, 1, 3, 3, 2, 1, 0, 4, 3, 1, 2, 6, 4, 5, 0]
print(foo(arr))


just starting with python pls be gentle

>pls be gentle
is ok bby, gon use extra lube
>3-deep nested loop
is this O(n^3)?

literally no idea what this does. Consider variable names that are more descriptive

why isn't there water at the zero height point?

>is this O(n^3)?
I don't think so. it scans n elements at most twice. So it should be O(n)

see and especially

I tested it and the time to calculate roughly doubled as I doubled the input size e.g. n = 50000 -> n = 100000, so yeah it's O(n)