Terrace climbs

A vineyard is cut into terraces up the hillside. A picker can step up one terrace or stride over two, and wants to know how many different climbs exist.

The problem

The vineyard road runs along the bottom of the slope, and the terraces above it are numbered 1, 2, 3 and so on up to terraces. A picker starts on the road and climbs to the top terrace. Each move is a single step to the next terrace up or a stride that skips one terrace and lands two above. Nobody ever climbs down.

Two climbs are different if the sequence of moves differs, even when they use the same number of steps and strides — walking up two singles then a stride is a different climb from a stride then two singles, because the picker's feet land on different terraces.

Count the distinct climbs from the road to the top terrace.

Input. terraces — an integer, the number of terraces above the road.

Output. The number of distinct climbs to the top terrace.

Example.

terraces = 4   ->  5

The five climbs are 1 1 1 1, 1 1 2, 1 2 1, 2 1 1 and 2 2, where each number is one move. Note that only three combinations of moves exist — four singles, two singles and a stride, or two strides — so counting combinations undercounts.

A second example, where the gap widens:

terraces = 6   ->  13

Four combinations of moves, but thirteen climbs, because the strides can sit at different points in the sequence.

Constraints.

• 1 <= terraces <= 60
• The answer fits in a 64-bit integer

Hints

Approach

Brute force

Walk every climb: from each terrace branch into a single and a stride, and count the walks that finish exactly on top. The recursion tree has roughly 2 to the power of terraces leaves — about 3.5 * 10^13 calls at 45 terraces, and it recomputes the same terrace millions of times.

The insight

Every climb to terrace t ends with either a single step from t - 1 or a stride from t - 2, so the count at t is the sum of the counts below it.

The two families are disjoint, because a climb has exactly one final move, and together they cover every climb, because there is no third kind of move. That makes the sum exact rather than an estimate. The count at a terrace depends on nothing but the terrace number — not on the route taken to reach it — which is what lets one number stand for all the climbs to that point.

The base cases carry the weight: there is exactly one way to be on the road having made no moves, and one way to reach terrace 1.

Algorithm

1. Hold two counts: below for the road and here for terrace 1, both 1.
2. Repeat terraces - 1 times: the next count is below + here.
3. Slide the pair up: below becomes here, here becomes the new count.
4. Return here.

Complexity

Time O(n) — one addition per terrace, 60 at the top of the range. Space O(1); two integers, because a terrace never reads more than two rows back.

Solution

"""Terrace climbs — a counting recurrence rolled into two variables."""


def solve(terraces):
    # Invariant: `below` counts the climbs ending on terrace t-1 and `here`
    # counts those ending on terrace t. Every climb to t+1 ends with a single
    # step from t or a stride from t-1, and those families are disjoint.
    below, here = 1, 1          # the road (no moves) and terrace 1
    for _ in range(terraces - 1):
        below, here = here, below + here
    return here

TESTS = [
    ((4,), 5),
    ((6,), 13),
    ((1,), 1),                  # one terrace: a single step, nothing else
    ((2,), 2),
    ((45,), 1836311903),
    ((60,), 2504730781961),     # top of the range, still a 64-bit value
]

Pitfalls

• Setting the road's count to 0. There is one way to stand on the road having climbed nothing. Zero there makes terrace 2 report 1 climb instead of 2 and halves everything above it.
• Counting how many singles and strides are used. For 4 terraces that gives 3, not 5. The question is about orderings of moves, so 1 2 1 and 2 1 1 are separate climbs.
• Recursing without a table. The plain two-way recursion is correct and unusable: 45 terraces takes hours, while the loop takes 45 additions.

Variants

• The fly cue sheet — the same "extend a finished arrangement" argument, but each step multiplies instead of adding.
• Sluice doses — the same one-index table, minimising a count instead of counting arrangements.