The roofline run

A night courier crosses a street of terraced roofs by leaping parapet to parapet, and momentum is the whole game.

The problem

The parapets along one side of a street stand at known whole-metre distances from the courier's starting roof, strictly increasing. The courier starts at metre 0 and wants to finish on the farthest parapet.

The first leap is a standing jump of exactly 1 metre. After that, if the last leap covered k metres, the next covers k - 1, k or k + 1. Every leap goes forward and must land on a parapet; anything else is a fall.

Input. parapets — a list of integers, the distance of each parapet from the start, strictly increasing, with parapets[0] == 0.

Output. True if some sequence of legal leaps lands on the last parapet, otherwise False.

Example.

parapets = [0, 1, 3, 4, 6, 9, 13]   ->  True

Leap 1 to metre 1, then 2 to metre 3, then 3, 3 and 4 to land on 6, 9 and 13.

A second example, where a gap arrives before the speed to cross it:

parapets = [0, 1, 2, 4, 8, 13]   ->  False

Metre 4 is reached with a leap of 2, so the next leap covers 1, 2 or 3 metres — metres 5, 6 or 7, none of which has a parapet.

Constraints.

• 1 <= len(parapets) <= 2000
• 0 <= parapets[i] < 2^31
• parapets[0] == 0, and the distances are strictly increasing

Hints

Approach

Brute force

Recurse: from the current parapet with last leap k, try k - 1, k and k + 1, and follow whichever land on a parapet. Three branches per level and up to n levels is 3ⁿ routes — at n = 40, a twenty-digit number — because the same (parapet, leap) pair is re-explored from every route that reaches it.

The insight

The future from a parapet depends only on where you stand and how long the last leap was, so (parapet, leap) is the state, and a pair explored once never needs exploring again.

Nothing earlier in the route matters, because the rule looks exactly one leap back. That is the precondition dynamic programming needs, and it fixes the order of work: leaps are strictly forward, so in increasing distance order a parapet's set of arriving leaps is complete before its turn.

Algorithm

1. Put every distance in a set, so "is there a parapet at metre d?" is O(1).
2. Keep a set arrivals[d] per parapet. Seed arrivals[0] = {0}, so the ordinary k + 1 rule makes the first real leap exactly 1.
3. Walk the parapets in increasing order. For each k in arrivals[d] and each nxt in k - 1, k, k + 1 with nxt > 0: if d + nxt is a parapet, add nxt to arrivals[d + nxt].
4. Answer whether arrivals[last] is non-empty.

Complexity

Time O(n²) — at most n distinct leap lengths per parapet, three O(1) lookups each. Space O(n²), the sets.

Solution

"""The roofline run — reachability over (parapet, length of the last leap)."""


def solve(parapets):
    """True if a runner starting on the first parapet can land on the last.

    parapets is strictly increasing and starts at 0. The first leap is exactly
    1 metre; every later leap is the previous leap's length, one metre less,
    or one metre more, and it must land on a parapet.
    """
    if not parapets:
        return False
    last = parapets[-1]
    where = set(parapets)                  # O(1) "is there a parapet at d?"

    # arrivals[d] = every leap length that has ever landed a runner at metre d.
    # Position alone is not the state: two runners on the same parapet who got
    # there with different leaps have different futures.
    arrivals = {d: set() for d in parapets}
    arrivals[0].add(0)                     # a leap of 0 makes the first leap 1

    for d in parapets:                     # invariant: everything before d is final
        for leap in arrivals[d]:
            for nxt in (leap - 1, leap, leap + 1):
                if nxt <= 0:               # a standing still or backward leap is not a leap
                    continue
                if d + nxt in where:
                    arrivals[d + nxt].add(nxt)

    return bool(arrivals[last])

TESTS = [
    (([0, 1, 3, 4, 6, 9, 13],), True),
    (([0, 1, 2, 4, 8, 13],), False),
    (([0, 1, 3, 5, 6, 8, 11, 15],), True),
    (([0],), True),                        # already standing on the last parapet
    (([0, 1],), True),
    (([0, 2],), False),                    # the first leap is exactly 1, no exceptions
    (([0, 1, 3, 6, 10, 15, 21, 28],), True),   # a leap that grows every time
    (([0, 1, 2, 3, 4, 5, 6, 7],), True),       # a leap that never grows
    (([0, 1, 3, 5, 8, 12, 13],), False),       # 12 is reached only with leap 4; 13 needs 1
    (([],), False),
]

Pitfalls

• Recording only whether a parapet is reachable. A boolean per parapet passes [0, 1, 3, 5, 8, 12, 13], because 12 is reached — but only with a leap of 4, and 13 is 1 metre on. The answer is False.
• Letting k - 1 reach 0. From a leap of 1, the candidate 0 lands on the same parapet and regenerates 1 from there — a runner who can restart anywhere. Skip any nxt <= 0.
• Finding the landing parapet by scanning forward. A linear search for d + nxt makes the run O(n³). Build the set first.

Variants

• Crossing the pontoons — the same forward walk with steps of one or two and a cost to minimise; position alone is the state.
• Terrace climbs — counts routes instead of asking whether one exists.