Skip to content

Instantly share code, notes, and snippets.

@SunnyDisposish
Created March 26, 2020 06:37
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save SunnyDisposish/f38828c6e03f960967e1f35d7d796169 to your computer and use it in GitHub Desktop.
def max_to_left(elevations):
max_so_far = float(inf) * -1
maxes_to_left = []
for h in elevations:
if h > max_so_far:
max_so_far = h
maxes_to_left.append(max_so_far)
return maxes_to_left
def max_to_right(elevations):
max_so_far = float(inf) * -1
maxes_to_right = []
for h in reversed(elevations):
if h > max_so_far:
max_so_far = h
maxes_to_right.append(max_so_far)
return maxes_to_right
def depth(elevations, max_to_right, max_to_left):
depths = []
for h, i in enumerate(elevations):
depth_here = max(0, min(max_to_right[i], max_to_left[i])-h)
depths.append(depth_here)
return depths
class Lake(object):
def __init__(self, lake_array, start, end):
self.lake_array = lake_array,
self.start = start
self.end = end
self.volume = sum(lake_array)
def find_lake_boundaries(depths):
starts = []
ends = []
for (left, i), (right, j) in zip(enumerate(depths[:-1]), enumerate(depths[1:])):
if (left == 0 or i == 0) and right != 0:
starts.append(j)
if left != 0 and (right == 0 or right == len(depths)):
ends.append(j)
return zip(starts, ends)
def make_lakes(depths):
boundaries = find_lake_boundaries(depths)
lakes = []
for start, end in boundaries:
lakes.append(Lake(depths[start:end], start, end))
return lakes
def best_lake(elevations):
depths = depths(elevations, maxes_to_left(elevations), max_to_right(elevations))
lakes = make_lakes(depths)
best_lake = max(lake.volume for lake in lakes)
return (best_lake.start, best_lake.end)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment