Crossing the pontoons

A river survey crosses on a line of moored pontoons. They sit at different deck heights, and every step up or down costs the surveyor effort.

The problem

The pontoons are moored in a line from the near bank to the far bank, and each has a deck height in centimetres above the water. The surveyor starts on the first pontoon and must finish on the last.

From a pontoon they can step to the next one or stride over one to the pontoon two along — no further, and never backwards. The effort of a step is the absolute difference between the two deck heights; the horizontal distance costs nothing. Find the least total effort to reach the last pontoon.

Input. decks — a non-empty list of integers, the deck height of each pontoon in order from the near bank.

Output. The smallest total effort to get from the first pontoon to the last.

Example.

decks = [30, 60, 40, 20]   ->  30

Striding from 30 straight over to 40 costs 10, then stepping down to 20 costs 20: 30 in total. Walking every pontoon costs 30 + 20 + 20 = 70.

A second example, where skipping a tall pontoon is free:

decks = [10, 90, 10]   ->  0

The middle pontoon rides high, and the stride from the first to the third joins two decks at the same height. Effort 0. A greedy "always take the cheaper next step" would climb to 90 and pay 160.

Constraints.

• 1 <= len(decks) <= 10^5
• 0 <= decks[i] <= 10^4

Hints

Approach

Brute force

Enumerate every sequence of 1-steps and 2-steps to the far bank. The number of such routes over n pontoons is the nth Fibonacci number — about 10²⁰ for n = 100, and the same prefixes are re-costed in every one of them.

The insight

The cheapest way to be standing on a pontoon depends only on the cheapest ways to stand on the previous two — everything before that is already paid for.

A route ending on pontoon i arrives from i-1 or i-2, and the cost of the part before the arrival is exactly the cheapest cost of standing where it arrived from. Nothing about how the surveyor reached i-1 changes the price of the last step, which is the property that makes the subproblems independent. So cost[i] = min(cost[i-1] + |decks[i] - decks[i-1]|, cost[i-2] + |decks[i] - decks[i-2]|), and since only two entries are ever read, the table rolls into two variables.

Algorithm

1. If there is one pontoon, the effort is 0.
2. Set two_back = 0 for the first pontoon, and one_back = |decks[1] - decks[0]| for the second.
3. For each later pontoon, cost the step from one_back and the stride from two_back, and keep the smaller.
4. Shift both variables forward and continue.
5. Return the value for the last pontoon.

Complexity

Time O(n) — two additions and one comparison per pontoon. Space O(1); the two rolling costs replace the whole table.

Solution

"""Crossing the pontoons — rolling minimum over the last two deck heights."""


def solve(decks):
    if len(decks) < 2:
        return 0
    # two_back / one_back: the least effort to be STANDING on the pontoon two
    # before / one before the current one. Nothing earlier can matter, because
    # the price of the next step depends only on where you stand now.
    two_back = 0
    one_back = abs(decks[1] - decks[0])
    for i in range(2, len(decks)):
        here = min(one_back + abs(decks[i] - decks[i - 1]),
                   two_back + abs(decks[i] - decks[i - 2]))
        two_back, one_back = one_back, here
    return one_back

TESTS = [
    (([30, 60, 40, 20],), 30),
    (([10, 90, 10],), 0),
    (([55],), 0),
    (([12, 5],), 7),
    (([40, 10, 70, 70, 60, 50],), 50),
    (([7, 7, 7, 7],), 0),
    ((list(range(0, 200, 2)),), 198),   # monotone climb: every route costs the same
]

Pitfalls

• Choosing the cheaper step rather than the cheaper route. On [10, 90, 10] a greedy walk takes the 1-step to the lower-looking neighbour it can see and pays 160 instead of 0.
• Reading decks[i-2] on the second pontoon. With the loop starting at index 1 that wraps to the end of the list in Python and silently returns a wrong number rather than raising. Seed the second pontoon before the loop.
• Returning 0 for a single pontoon by accident of the loop, but crashing on the empty case. Decide what one pontoon means and state it: the surveyor is already across, so the effort is 0.

Variants

• The hive scale — the same one-pass rolling state, reading one cell back and maximising instead of two and minimising.
• Linear DP — where the "reads a fixed number of cells behind it" rule that makes this O(n) is set out.