Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Flood Area by colinmcnicholl
from typing import List
UPSLOPE = '/'
DOWNSLOPE = '\\'
def flood_area(diagram: str) -> List[int]:
"""Input: A cross-section diagram (a string), e.g. '\\//', 'a valley'.
Area calculation: On start of climb out of valley each upslope that
does not reach either
1) the altitude at which the valley started (at index
on the left) adds 1 (0.5 units + 0.5 units for the matching downslope
to the left), or
2) a turning point (change to downslope) - hence a 'sub-valley'.
For an upslope that reaches the top of the valley (or a turning point) the
expression 'idx - stack[-1][0]' represents the 'span' of the 'base'
(inverted) of the valley. 1 * this quantity - 1 equates to the area
of the 'base' level of the valley. 1 is subtracted because the extreme
left and right ends of this 'base' level are each 0.5 units of area
and not of unit area.
No increment to area required for 'flat' regions because these result in
the index and hence 'span' of the base of the valley increasing so the
effect of a 1 unit addition to area is captured in the calculation
described above.
Output: A list of integers, each integer representing tha area of the
flood. If there is no flood, return [].
"""
max_altitude = cur_altitude = cur_area = 0
idx = -1
stack = [(idx, cur_altitude, cur_area)]
for idx, slope in enumerate(diagram):
cur_area = 0
if slope == UPSLOPE:
cur_altitude += 1
if cur_altitude <= max_altitude: # Climbing out of valley.
while stack and stack[-1][1] < cur_altitude:
_, _, area = stack.pop()
cur_area += area
else: # Climbing mountain.
max_altitude = cur_altitude
if stack and stack[-1][1] == cur_altitude: # Top of valley.
cur_area += idx - stack[-1][0] - 1
elif slope == DOWNSLOPE: # Descending from mountain or into valley.
cur_altitude -= 1
stack.append((idx, cur_altitude, cur_area))
return [area for _, _, area in stack if area]
if __name__ == '__main__':
print("Example:")
print(flood_area(r'\\//'))
assert flood_area(r'\\//') == [4], 'valley'
assert flood_area(r'/\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/') == [4, 2, 1, 19, 9], 'mountains'
assert flood_area(r'_/-\_') == [], 'hill'
print("Coding complete? Click 'Check' to earn cool rewards!")
March 23, 2019
