Chop on the river gauge

A staff gauge in the river logs the water level every ten minutes. Wind chop shows up as readings that alternate up, down, up — and the survey wants the longest such stretch.

The problem

The gauge writes the water level, in centimetres, once every ten minutes. Call a stretch of the log choppy when its consecutive steps alternate in direction: up, down, up, down, or down, up, down, up. One reading on its own counts as choppy, and so does any pair of readings that differ.

Two equal readings in a row break the alternation. The surface was flat for that step, so no choppy stretch can contain both.

The stretch has to be contiguous — consecutive entries in the log, not a selection from it. Report how many readings the longest choppy stretch holds.

Input. levels — a list of integers, water level in centimetres, in log order.

Output. The number of readings in the longest choppy stretch, or 0 for an empty log.

Example.

levels = [30, 26, 31, 28, 33, 33, 21]  ->  5

30, 26, 31, 28, 33 steps down, up, down, up — five readings. The repeated 33 kills that run, and 33, 21 restarts at two.

Example, on logs that never alternate:

levels = [12, 12, 12]  ->  1
levels = [4, 5, 6, 7]  ->  2

A flat log has no usable step at all, so one reading is the best on offer. A log that only rises alternates for exactly one step, so no choppy stretch reaches three.

Constraints.

• 0 <= len(levels) <= 4 * 10^4
• 0 <= levels[i] <= 10^5
• readings are evenly spaced and given in log order

Hints

Approach

Brute force

Start at every index and walk forward while the direction keeps flipping. Each start can run to the end of the log, so the work is about n²/2 comparisons — 800 million on a log of 40,000 readings, for an answer that one pass can give.

The insight

A run's future depends on a single bit of its past — whether its last step went up or down — so two counters replace every re-walk.

The alternation rule looks only at the previous step. Given the longest choppy run ending at i - 1 that arrived rising, and the one that arrived falling, the run ending at i is forced: a rise at i can only follow a fall, so it is falling + 1; a fall can only follow a rise, so it is rising + 1. Nothing earlier in the log can change either value, which is what lets the scan throw the past away.

Algorithm

1. An empty log answers 0. Otherwise set best = rising = falling = 1.
2. For each i from 1, compare levels[i] with levels[i - 1].
3. Step up: rising becomes the old falling + 1, and falling resets to 1.
4. Step down: falling becomes the old rising + 1, and rising resets to 1.
5. Equal: both reset to 1.
6. Fold rising and falling into best after each reading, then return best.

Complexity

Time O(n) — one comparison and a constant update per reading. Space O(1) — three counters, whatever the log length.

Solution

"""Chop on the river gauge — two run lengths carried alongside the scan."""


def solve(levels):
    """Longest stretch of readings whose steps alternate up, down, up, down."""
    if not levels:
        return 0

    # rising  = longest choppy run ending here whose last step went up
    # falling = the same, but whose last step went down
    best = rising = falling = 1
    for i in range(1, len(levels)):
        if levels[i] > levels[i - 1]:
            rising, falling = falling + 1, 1
        elif levels[i] < levels[i - 1]:
            rising, falling = 1, rising + 1
        else:
            rising = falling = 1       # a flat step ends every run at this reading
        best = max(best, rising, falling)
    return best

TESTS = [
    (([30, 26, 31, 28, 33, 33, 21],), 5),
    (([12, 12, 12],), 1),
    (([5, 9],), 2),
    (([7, 3, 7, 3, 7],), 5),
    (([],), 0),
    (([41],), 1),
    (([4, 5, 6, 7],), 2),
]

Pitfalls

• Overwriting a counter before the other one reads it. On a falling step, setting rising = 1 first and then falling = rising + 1 always gives 2. On [7, 3, 7, 3, 7] that reports 2 instead of 5. Both counters must be assigned from the old pair.
• Folding equal readings into one of the directions. Comparing with >= treats a flat step as a rise, and [12, 12, 12] reports 3 instead of 1.
• Seeding best at 0. A single reading is a choppy stretch of length 1; only the empty log answers 0. Starting at 0 and updating only inside the loop returns 0 for [41].

Variants

• The seed tray ladder — the same "best run ending here" scan, but the run may skip entries, so the state is keyed by value instead of by direction.
• Linear DP — the general recipe behind these one-pass recurrences, and when two variables can stand in for the whole array.