Longest Peak without backtracking

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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))