I agree with the reviewers before me. Yet I feel like there has to be a more readable solution, one without so many cases. For the sake of simplicity of description, I assume the input is a list, but the code works for any iterable.
Compressing the input
All the information about the input list needed for this problem is contained in a list of the differences of the consecutive terms of the input. I.e. We only need the height differences. In fact, we only need the sign of these:
-, o, +.
Then a peak is a (non-zero) number of
+'s followed by a (non-zero) number of
Sublists starting with
+ will be called mountains. These are potential peaks.
The proposed algorithm
We can use an algorithm which is the repetition of the following two steps:
- Find a mountain.
- Climb the mountain, while recording its length.
Finding a mountain amounts to consuming the input until we find a '+'.
By climbing the mountain we mean that we'll move up as far as we can, then we'll move down as far as we can. I.e. consume as many
+ as possible, then consume as many
- as possible.
At the end of a climbing step if we've moved up at least once, and down at least once, then we've just climbed a peak of length
plusses + minuses + 1. Otherwise we passed no peak.
So we repeat these two steps while there are still signs left for us to consume.
Consuming an iterable while a condition holds calls for
itertools.dropwhile, but we need to record the number of items dropped, so we implement
from itertools import chain, tee, islice
from operator import sub
from typing import Callable, Iterator, Iterable, TypeVar, Tuple
T = TypeVar('T')
def drop_while(condition: Callable[[T], bool], iterator: Iterator[T]) -> Tuple[Iterator[T], int]:
""" A variation of dropwhile that
consumes its input iterator while condition holds,
then it returns the remainder of the iterator and the number of elements consumed
num_dropped = 0
for i in iterator:
num_dropped += 1
return chain([i], iterator), num_dropped
return iterator, num_dropped
Once we have this function, everything falls into place easily.
def max_peak_length(nums: Iterable[int]) -> int:
""" Returns the maximal peak length from an iterable.
max_peak_length([6,6,1,8,3,2,1])) == 5
def peak_lengths(nums: Iterable[int]) -> Iterator[int]:
""" Returns the length of the peaks of an iterable as an iterator.
First we calculate the differences between successive heights,
then we go through them repeating the following two actions in order:
- find the first mountain start, i.e. positive height difference
- climb a mountain
- count the number of consecutive '+' elements, then
- count the number of consecutive '-' elements
- we traversed a peak if both of these are positive
The peaks' length is their sum +1
# Iterator of height differences. Only their sign will be used.
it1, it2 = tee(nums)
it = map(sub, islice(it1, 1, None), it2)
# Skip to the first +.
it, skipped_len = drop_while(lambda x: x <= 0, it)
# Skip through and count consecutive +'s then -'s.
it, plusses = drop_while(lambda x: x > 0, it)
it, minuses = drop_while(lambda x: x < 0, it)
# If we traversed a true peak.
if plusses > 0 and minuses > 0:
yield plusses + minuses + 1
# If the iterator is empty, stop.
if skipped_len == 0 and plusses == 0 and minuses == 0:
# to avoid failing on inputs without mountains