This community-built FAQ covers the “Capturing Rainwater” code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.
Top Discussions on the Python challenge Capturing Rainwater
There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
You can also find further discussion and get answers to your questions over in #get-help.
Agree with a comment or answer? Like () to up-vote the contribution!
def capturing_rainwater(heights):
waterTotal = 0
prevHeights = []
if heights:
maxHeight = heights[0]
else:
return 0
# Subtract preceding heights from current height (or max height if at a local maximum block to allow for local water levels) and remove negative and 0 values, the sum of this array results in the amount of water contained to the left by the current block
for i in heights.copy():
subArr = [i-a for a in prevHeights] if i < maxHeight else [maxHeight-a for a in prevHeights]
filterSub = [x for x in subArr if x > 0]
print(i, filterSub, subArr, prevHeights)
waterTotal += sum(filterSub)
# Increase heights of blocks that have already been counted as having some water above them up to this water level to avoid double counting
prevHeights = [i if x < i else x for x in prevHeights]
prevHeights.append(i)
# If at a local maximum block calculate the water for this local section (right of local maximum)
if i > maxHeight:
return waterTotal + capturing_rainwater(heights)
# Remove from unprocessed heights to allow for recersion
heights.pop(0)
return waterTotal
test_array = [4, 2, 1, 3, 0, 1, 2]
# test_array = [2,1,3,1,2]
# test_array = [3, 2, 1, 6, 5, 6, 2, 4]
print(capturing_rainwater(test_array))
def capturing_rainwater(heights):
# Write your code here
total = 0
for i in range(1,len(heights)-1):
left = []
#print(" ",i)
for it in reversed(range(i+1)):
if max(heights[i],heights[it])!= heights[i]:
left.append(max(heights[i],heights[it]))
right = []
for it in range(i,len(heights)):
if max(heights[i],heights[it])!=heights[i]:
right.append(max(heights[i],heights[it]))
if right == []:
right = [-1]
left = [-1]
if left == []:
left = [-1]
right = [-1]
right = max(right)
left = max(left)
#print(min(right,left))
#print(heights[i])
if right != -1 and left != -1:
total += min(right,left)-heights[i]
#print(total)
#print()
#print(left)
#print(right)
return total
test_array = [4, 2, 1, 3, 0, 1, 2]
print(capturing_rainwater(test_array))
Move one level up. Repeat this until you reach the upper value.
def capturing_rainwater(heights):
if len(heights) == 0: # When heights is []
return 0
else:
print(heights)
# Remove outer lower values:
if len(heights) > 2:
while heights[0] <= heights[1] and len(heights) > 2:
heights.pop(0)
while heights[-1] <= heights[-2] and len(heights) > 2:
heights.pop()
new_array = []
for x in heights:
new_array.append(x)
zeros = 0
for i in range(max(heights)):
# remove outer zeros:
while new_array[0] == 0:
new_array.pop(0)
while new_array[-1] == 0:
new_array.pop()
zeros += new_array.count(0) # count zeros between 'walls'
for j in range(len(new_array)): # voor elk item in regel:
# each value minus 1 (as if you go one level up)
if new_array[j] > 0:
new_array[j] = new_array[j] - 1
return zeros
test_array = [4, 2, 1, 3, 0, 1, 2]
print(capturing_rainwater(test_array))
Anyone know how to learn what inputs are being tested when you click Test Code? I got 4/5 tests passed, so I suspect there’s some edge case I didn’t handle, but I’m not sure what it is. I did discover that one of the five tests has an empty list as an input.
def capturing_rainwater(heights):
num_wells = len(heights) # the number of wells/bars
if num_wells <= 2: # ignore the edge cases
return 0
def big_left(i): # find the tallest bar to the left of index i
return max([heights[j]-heights[i] for j in range(0,i+1)])
def big_right(i): # find the tallest bar to the right of index i
return max([heights[j]-heights[i] for j in range(i,num_wells)])
count = 0
for i in range(1, num_wells - 1):
x = big_left(i)
y = big_right(i)
z = min(x,y) # the amount of water is the min of x and y
count += z
return count
test_array = [4, 2, 1, 3, 0, 1, 2]
print(capturing_rainwater(test_array))
I thought this was solution was easy to follow. The solution from @steffan153 was awesome, but hurt my brain. Logically, the number of water units above a given bar is the minimum of the tallest bars to the left and the right. Once you realize that, a solution is simple. Steffan showed how to simplify the code to its bare bones.
def capturing_rainwater(heights):
if len(heights) <= 2: return 0
return sum([min(max([heights[i]-heights[n] for i in range(0,n+1)]), max([heights[i]-heights[n] for i in range(n,len(heights))])) for n in range(1,len(heights)-1)])
I was toying with this problem again and did it in 2 lines. Not very readable, but kind of silly.
Edited to add: it only needs one line. The If isn’t necessary…
I did mine by finding an interval that could hold water (by finding the index of a maximum or the index of a relative maximum with a value above a specified number) and then finding the volume of water contained in such an interval. Repeat until reach the end of the list/array.
My code does not seem efficient … its longer than the other answers given.
I tried to avoid creating new lists or traversing the list unnecessarily.
My solution
def capturing_rainwater(heights):
length = len(heights)
# function to find next index
# of maximum of remaining entries in list or
# next relative maximum (peak) above a given hieght (level)
def get_next_max_index(starting_index = 0, level = None):
max_so_far = 0
index_of_max_so_far = starting_index
for i in range(starting_index, length):
h = heights[i]
if (h >= max_so_far):
index_of_max_so_far = i
max_so_far = h
if (level is not None):
if (h > level):
previous_height = h
for j in range(i + 1, length):
current_height = heights[j]
if current_height >= previous_height:
# increasing so maybe haven't gotten to peak yet
index_of_max_so_far = j
else: # current_height < previous_height:
# decreasing so passed peak already
break
previous_height = current_height
return index_of_max_so_far
return index_of_max_so_far
def get_volume_between(a, b): # a,b are indices
if (a > b):
(a, b) = (b, a)
elif (a == b):
return 0
if (a < 0 or b < 0):
return 0
if (a >= length or b >= length):
return 0
level = min(heights[a], heights[b]) # water level
volume_so_far = 0
for i in range(a + 1, b):
h = heights[i]
if (h >= 0 and h < level):
depth = level - h
volume_so_far += depth
return volume_so_far
# will find the volume, one interval at a time
left_index = -1
right_index = 0
volume = 0
level = 0 # water level so far (if before index of max)
while right_index < length:
right_index = get_next_max_index(left_index + 1, level) # find right end of interval
if right_index >= 0 and right_index < length:
level = heights[right_index]
volume += get_volume_between(left_index, right_index)
left_index = right_index # to move to next interval
return volume
I am facing an issue where the Test says “Tests failed to run due to an error: “list index out of range”. Check your code and try again.”. Anyone can debug it or tell me where the issue is? Because I can’t see it and I never came across it. I tried changing the heights list so many times in hope I do come across it.
def capturing_rainwater(heights):
units = 0 # The units of water gathered
left_max_height = []
l_max_height = heights[0] # Initial max height from left
# Starting from left - right max height array
for i in range(0, len(heights)): # The idea is compare the prev max height
if heights[i] > l_max_height: # with the current height
l_max_height = heights[i]
left_max_height.append(l_max_height) # Append to list
right_max_height = [] # Max height arrays from left and from right
r_max_height = heights[len(heights)-1] # Initial max height from right
# Starting from left - left max height array
for j in range(len(heights)-1, -1, -1):
if heights[j] > r_max_height:
r_max_height = heights[j]
right_max_height.append(r_max_height) # Create a max height from right
right_max_height.reverse() # Reverse list starting from right
# The minimum between the two maximum heights decides what
# can be gathered by the columns
for k in range(0, len(heights)-1):
units += min(left_max_height[k], right_max_height[k]) - heights[k]
return units
test_array = [0, 10, 5, 30, 10, 40]
print(capturing_rainwater(test_array))
Probably the hardest python challenge here that i managed to solve. Couldn’t do it without adding max iteration to prevent while loop from looping forever.
def capturing_rainwater(heights):
listy = list(heights)
if len(listy) <= 2:
return 0
sumy = 0
listx = []
maxiter = 0
while maxiter < 100000:
listx = listy
# remove all minimum
for i in range(0,len(listy)-1):
if listy[i] == listy[i+1]:
continue
if listy[i] > listy[i+1]:
listy = listy[i:]
break
listy.reverse()
for i in range(0,len(listy)-1):
if listy[i] == listy[i+1]:
continue
if listy[i] > listy[i+1]:
listy = listy[i:]
break
listy.reverse()
a = min(listy)
for k in range(0, len(listy)):
if a == listy[0] or a == listy[-1]:
break
if listy[k] == a:
sumy += 1
listy[k] += 1
if listy == listx:
break
maxiter += 1
return sumy
test_array = [1,2]
print(capturing_rainwater(test_array))
Definitely one of the most satisfying challenges I’ve completed in general. Seemed a lot harder than the others in my opinion. I love to see all of the different ways that everyone has came to the answer!
I used the index of the first and last numbers to skip over them and then I used a couple of loops and lots of indexing to basically go through each height (aka number) and check if the one before it was taller and then to check if the one in front of it was taller as well and then figure out which one was taller and match it. I took the difference of the height that I matched and added it to rainwater. If the height directly in front was not the tallest height in front then it proceeds to the next height in front to check that one instead. I did this process for all heights except for the 2 on the outside.
def capturing_rainwater(heights):
rainwater = 0
for index in range(len(heights)):
if index == 0:
continue
if index == len(heights) - 1:
continue
if heights[index - 1] > heights[index]:
for x in range(index + 1, len(heights)):
if heights[x] > heights[index] and heights[x] <= heights[index - 1]:
if heights[x] == heights[-1]:
rainwater += heights[x] - heights[index]
heights[index] = heights[x]
elif heights[x + 1] > heights[x]:
rainwater += heights[x + 1] - heights[index]
heights[index] = heights[x + 1]
else:
rainwater += heights[x] - heights[index]
heights[index] = heights[x]
elif heights[x] > heights[index] and heights[x] >= heights[index - 1]:
rainwater += heights[index - 1] - heights[index]
heights[index] = heights[index - 1]
return rainwater
test_array = [4, 2, 1, 3, 0, 1, 2]
print(capturing_rainwater(test_array))
) below.
) to up-vote the contribution!