6
\$\begingroup\$

The goal is to find the longest peak in a sequence of numbers. A peak is defined to be a strictly increasing elements until a tip is found and then a strictly decreasing elements.

e.g. (1): 3, 2, 1, 2, 3, 4, 3, 0, 10, 0, 1, 2, 2, 1, 0

1, 2, 3, 4, 3, 0 is a peak; 0, 10, 0 is a peak; 0, 1, 2, 2, 1, 0 is NOT a peak (there is no tip);

e.g. (2): 1, 3, 2 is a peak

e.g. (3): 1, 2, 3 is NOT a peak

I'm trying to do so without backtracking - i.e. without finding a peak and then going outwards from it both back and front.

Here's a code I came up with

def longestPeak(array):
    longest = peakStart = peakEnd = 0
    peakArrived = False
    for i in range(1, len(array) - 1):
        # Check for peak
        if array[i-1] < array[i] and array[i] > array[i+1]:
            peakArrived = True
            if len(array) == 3:  # special case
                return 3
        # Check for end
        if array[i] <= array[i+1] and array[i] < array[i-1]:
            peakEnd = i
        elif array[i+1] < array[i] and i+2 == len(array):
            peakEnd = i+1
        # Check for longest
        if peakArrived and peakEnd > peakStart and peakEnd - peakStart + 1 > longest:
            longest = peakEnd - peakStart + 1
            peakArrived = False
        # Check for start
        if array[i] < array[i+1] and array[i] <= array[i-1]:
            peakStart = i
        elif array[i] > array[i-1] and i == 1:
            peakStart = 0

    return longest
\$\endgroup\$
1
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Feel free to post a new question instead. \$\endgroup\$
    – Mast
    May 6, 2020 at 17:32

3 Answers 3

5
\$\begingroup\$

Are you sure that solution is correct? By your description of the problem, I would have expected the result for an input [1, 6, 4, 7, 6, 6, 5] to be 3, but your solution produces 5.

Your solution is interesting -- that drew me to this question. I find that code looking at adjacent elements when iterating and accumulating an optimal value is a code smell in algorithms. It typically makes a solution significantly more difficult to read and debug. Usually, you should only look at as few values in each iteration as possible -- and I believe it's sufficient to look only at the current value whilst keeping the previous handy.

        if array[i-1] < array[i] and array[i] > array[i+1]:

This confers the additional benefit of removing the random access requirement for the input; that is, removing the __getitem__ dependency (array[i] is actioned as type( array ).__getitem__( array, i )). Whilst you've indicated that the input should be an array by the parameter name, one of Python's strengths is its duck-typing. There's no fundamental reason why the algorithm could not, or should not, apply more generically to any Iterable[int]. My solutions below will additionally work with input (contrived, I grant you) ( x for x in ( 0, 1, 0 ) ). If your minimum Python version requirement is sufficiently high, I would personally add a type hint to the argument, but that's usually deemed overkill.

            if len(array) == 3:  # special case
                return 3

A special case that isn't an edge-value of a data-type (e.g. 0 for an unsigned integer) is an immediate code smell.

    for i in range(1, len(array) - 1):

Skipping the end (and usually the start) of a sequence in an accumulation/optimisation problem is a smell. Avoid if possible.

The problem can be modeled by a state-machine. On each iteration of the array elements, you begin in one of four states: starting, floor, climbing, descending. You begin in the starting state and once the first element is seen immediately transition to floor. The floor represents a state in which you're neither climbing nor descending. This occurs when you've reached some plateau and haven't climbed out of it. The climbing state is self-descriptive. You begin descending once you have passed a peak having made a climb. The longest seen peak can only end whilst in a descending state. You seemed in your solution to try and defer the recalculations of the longest seen peak until you've left the peak. This isn't necessary -- if you descend further downwards, you can always carry on increasing the value of the longest seen peak.

Here is a descriptive algorithm:

import enum

class TrekState( enum.Enum ):
    Begin   = 0
    Floor   = 1
    Climb   = 2
    Descend = 3

class Trek:
    def __init__( self ):
        self.state = TrekState.Begin
        self.counter = 0
        self.longest = 0

    def advance( self, i ):
        # update new state of our trek
        if self.state == TrekState.Begin:
            self.state = TrekState.Floor
            self.counter = 1
        else:
            previous = self.previous

            if self.state == TrekState.Floor:
                if previous < i:
                    self.state = TrekState.Climb
                    self.counter += 1
            elif self.state == TrekState.Climb:
                if previous < i:
                    self.counter += 1
                elif previous > i:
                    self.state = TrekState.Descend
                    self.counter += 1
                else: # previous == i
                    self.state = TrekState.Floor
                    self.counter = 1
            elif self.state == TrekState.Descend:
                if previous < i:
                    self.state = TrekState.Climb
                    self.counter = 2
                elif previous > i:
                    self.counter += 1
                else: # previous == i
                    self.state = TrekState.Floor
                    self.counter = 1 

        # update longest and previous
        if self.state == TrekState.Descend:
            self.longest = max( self.counter, self.longest )
        self.previous = i 

def updatedLongestPeak( seq ):
    trek = Trek()
    for i in seq:
        trek.advance( i ) 
    return trek.longest

. A more concise version of the above, replacing object constructs with a more unstructured style, and some manual optimisations:

def verboseLongestPeak( seq ):
    state = counter = longest = 0

    for i in seq:
        counter += 1
        if state == 0:
            state = 1
        elif state == 1:
            if previous < i:
                state = counter = 2
        elif state == 2:
            if previous > i:
                state = 3
            elif previous == i:
                state = 1
        elif state == 3:
            if previous < i:
                state = counter = 2
            elif previous == i:
                state = 1

        if state == 3:
            longest = max( counter, longest )
        previous = i

    return longest

. If you were to go for a solution of the latter's style, it would be essential to provide comments on the meaning of each state value.

Neither solution is verified to be correct.

\$\endgroup\$
2
  • \$\begingroup\$ I tested your code and it seems to work on most test cases. You're right I had a bug - I fixed it though... So will update the code. States is a very clear way to represent the problem. \$\endgroup\$ May 6, 2020 at 17:11
  • \$\begingroup\$ Great answer! I did not want to answer for a fear of inadequateness. You absolutely proved that hunch right. Good insights on those subtler code smells, a lesson on state machines (very readable at that) and showcasing enum.Enum, by which I was recently profoundly confused (what could that be good for?...). Really enjoyed it and learned a lot, thanks. \$\endgroup\$
    – Alex Povel
    May 6, 2020 at 18:55
1
\$\begingroup\$

Here's a fix for the code bug, and also removal of the special case handling:

def longestPeak(array):
    longest = peakStart = peakEnd = 0
    peakArrived = False
    for i in range(1, len(array) - 1):
        # Check for peak
        if array[i-1] < array[i] and array[i] > array[i+1]:
            peakArrived = True
        # Check for end
        if array[i] <= array[i+1] and array[i] < array[i-1]:
            peakEnd = i
        elif array[i+1] < array[i] and i+2 == len(array):
            peakEnd = i+1
        # Check for longest
        if peakArrived and peakEnd > peakStart:
            if peakEnd - peakStart + 1 > longest:
                longest = peakEnd - peakStart + 1
            peakArrived = False
        # Check for start
        if array[i] < array[i+1] and array[i] <= array[i-1]:
            peakStart = i
        elif array[i] > array[i-1] and i == 1:
            peakStart = 0

    return longest
\$\endgroup\$
1
\$\begingroup\$

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 -'s.

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:

  1. Find a mountain.
  2. 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.

Implementation

Consuming an iterable while a condition holds calls for itertools.dropwhile, but we need to record the number of items dropped, so we implement drop_while.

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:
        if condition(i):
            num_dropped += 1
        else:
            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)

        while True:
            # 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

            else:
                # If the iterator is empty, stop.
                if skipped_len == 0 and plusses == 0 and minuses == 0:
                    break

                yield 0

        # to avoid failing on inputs without mountains
        yield 0

    return max(peak_lengths(nums))
\$\endgroup\$
3
  • 1
    \$\begingroup\$ your solution fails for inputs of lists of length 0 or 1. it also exhibits some of the same problems as OP's (skipping first element and failing to work with generic iterables). nums[1:] may look harmless, but it produces a copy of (almost) the entirety of the list. i usually consider micro-optimisations a waste of time in Python, but degrading performance from O(1) space to O(n) space for no gain is grossly inefficient. there is some good insight to be found here, but i don't like the solution as it currently stands. \$\endgroup\$ May 7, 2020 at 22:04
  • 1
    \$\begingroup\$ @two_pc_turkey_breast_mince Thank you very much. If there are no mountains in the list, the original code fails, due to max getting an empty input. Thanks for the nums[1:] comment. The same is achievable using tee and islice. Code should be good to go. Works on iterables too. \$\endgroup\$ May 7, 2020 at 22:37
  • 1
    \$\begingroup\$ thanks, differential testing is always comforting :)! \$\endgroup\$ May 7, 2020 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.