Python Challenge - Capturing Rainwater, Capturing Rainwater

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 (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 (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 (like) to up-vote the contribution!

Need broader help or resources? Head to #get-help and #community:tips-and-resources. If you are wanting feedback or inspiration for a project, check out #project.

Looking for motivation to keep learning? Join our wider discussions in #community

Learn more about how to use this guide.

Found a bug? Report it online, or post in #community:Codecademy-Bug-Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

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))
1 Like
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))
1 Like
def capturing_rainwater(heights): return sum(max(0, min(max([0, *heights[i+1:]]), max([0, *heights[:i]])) - n) for i, n in enumerate(heights)) test_array = [4, 2, 1, 3, 0, 1, 2] print(capturing_rainwater(test_array))
6 Likes

Most interesting challenge so far.

  • Check every row.
  • Remove the outer ‘lower values’.
  • Count the number of zeros.
  • 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.

1 Like
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.

2 Likes
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…

def capturing_rainwater(heights): # Write your code here total_water = [] for i, h in enumerate(heights): left_walls = heights[:i] right_walls = heights[i+1:] if left_walls: left_bound = max(left_walls) else: left_bound = None if right_walls: right_bound = max(right_walls) else: right_bound = None if left_bound and right_bound: water_at_index = min((left_bound, right_bound)) - h else: water_at_index = None if water_at_index and water_at_index > 0: total_water.append(water_at_index) return sum(total_water) test_array = [4, 2, 1, 3, 0, 1, 2] test_2 = [4, 8, 7, -2, 4, -3, 3, 2, 8, 0] print(capturing_rainwater(test_array))
1 Like


very messy but it works

def capturing_rainwater(heights):
  total_water = 0
  left_pointer = 0
  right_pointer = len(heights) - 1
  left_bound = 0
  right_bound = 0

  # Write your code here
  while(left_pointer < right_pointer):
    if heights[left_pointer] <= heights[right_pointer]:
      left_bound = max(left_bound, heights[left_pointer])
      total_water += left_bound - heights[left_pointer]
      left_pointer += 1
    else:
      right_bound = max(right_bound, heights[right_pointer])
      total_water += right_bound - heights[right_pointer]
      right_pointer -= 1
    
  return total_water

test_array = [4, 2, 1, 3, 0, 1, 2]
print(capturing_rainwater(test_array))

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

Checking 2 max values, summing up everything between them and remove them, then do this as recusion until it’s done.

import heapq def capturing_rainwater(heights): result = 0 while len(heights) > 1: maxElements = heapq.nlargest(2, heights) indexMaxElements = [heights.index(maxElements[0]), heights.index(maxElements[1])] if abs(indexMaxElements[0] - indexMaxElements[1]) == 1: heights.pop(indexMaxElements[0]) else: indicesBetweenMaxes = indexMaxElements[1] + 1 if indexMaxElements[0]-indexMaxElements[1] > 0 else indexMaxElements[0] + 1 for i in range(abs(indexMaxElements[1] - indexMaxElements[0]) - 1): result += maxElements[1] - heights[indicesBetweenMaxes] heights.pop(indicesBetweenMaxes) heights.pop(indicesBetweenMaxes) return result test_array = [4, 2, 1, 3, 0, 1, 2] print(capturing_rainwater(test_array))