Skip to content

Instantly share code, notes, and snippets.

@anthonykasza
Last active October 7, 2022 17:34
Show Gist options
  • Save anthonykasza/42b62a6bf0a2b45919ed19707a3ca71b to your computer and use it in GitHub Desktop.
Save anthonykasza/42b62a6bf0a2b45919ed19707a3ca71b to your computer and use it in GitHub Desktop.
calculate the water volume between peaks of a mountain range
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")
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment