calculate the water volume between peaks of a mountain range

find_water_volume.py

mountain_ranges = {
  (0,1,2,3,4): 0+0+0,
  (4,3,2,1,0): 0+0+0,
  (0,3,2,1,1): 0+0+0,
  (1,1,1,1,1): 0+0+0,
  (1,1,0,0,0): 0+0+0,
  (0,0,1,1,1): 0+0+0,
  (0,0,1,0,0): 0+0+0,
  (1,0,0,0,1): 1+1+1,
  (1,0,0,0,2): 1+1+1,
  (1,0,1,0,1): 1+0+1,
  (0,1,0,1,0): 0+1+0,
  (0,0,1,0,1): 0+0+1,
  (13,7,19,9,11): 6+0+2,
  (10,5,6,5,10): 5+4+5,
  (10,5,6,5,11): 5+4+5
}


# this could likely be made faster if we calc'd right_height outside of the for loop and
#  stored its index. then only called `right_height = max(heights[idx+1:])` again 
#  when idx > right_height_idx
def find_water_volume(heights):
  total = 0
  for idx in range(len(heights)):
    if idx == 0 or idx == len(heights)-1:
      continue
    land_height = heights[idx]
    left_height = max(heights[:idx])
    right_height = max(heights[idx+1:])
    water_height = max(min(left_height, right_height) - land_height, 0)
    total += water_height
  return total



for k,v in mountain_ranges.items():
  water_vol = find_water_volume(k)
  if water_vol == v:
    print(k, v, water_vol, "passed")
  else:
    print(k, v, water_vol, "failed")

more_better_find_water_volume.py

mountain_ranges = {
  (0,1,2,3,4): 0+0+0,
  (4,3,2,1,0): 0+0+0,
  (0,3,2,1,1): 0+0+0,
  (1,1,1,1,1): 0+0+0,
  (1,1,0,0,0): 0+0+0,
  (0,0,1,1,1): 0+0+0,
  (0,0,1,0,0): 0+0+0,
  (1,0,0,0,1): 1+1+1,
  (1,0,0,0,2): 1+1+1,
  (1,0,1,0,1): 1+0+1,
  (0,1,0,1,0): 0+1+0,
  (0,0,1,0,1): 0+0+1,
  (13,7,19,9,11): 6+0+2,
  (10,5,6,5,10): 5+4+5,
  (10,5,6,5,11): 5+4+5
}


def max_and_idx(heights):
  max_value = -1
  max_idx = -1
  for idx in range(len(heights)):
    if idx == 0:
      max_value = heights[idx]
      continue
    if heights[idx] >= max_value:
      max_value = heights[idx]
      max_idx = idx

  return (max_value, max_idx)



def find_water_volume(heights):
  total = 0
  left_max_value = 0
  right_max_value = 0
  right_max_idx = 0

  for idx in range(len(heights)):
    loops += 1
    land_height = heights[idx]

    if idx == 0:
      left_max_value = land_height
      (right_max_value, right_max_idx) = max_and_idx(heights[idx+1:])
      if right_max_idx == -1:
        break
      continue

    if idx == len(heights) - 1:
      break

    if land_height > left_max_value:
      left_max_value = land_height
      (right_max_value, right_max_idx) = max_and_idx(heights[idx+1:])
      if right_max_idx == -1:
        break
      continue

    water_height = max(min(left_max_value, right_max_value) - land_height, 0)
    total += water_height

  return total



for k,v in mountain_ranges.items():
  water_vol = find_water_volume(k)
  if water_vol == v:
    print(k, v, water_vol, "passed")
  else:
    print(k, v, water_vol, "failed")