Break-even on the market run

A trader wants every route that ends the week on exactly the target. A bad Tuesday does not end a route, so the running total is free to overshoot and come back.

The problem

A market trader books a van route as a tree. The week starts at the home market, and from every market at most two onward markets are booked, on the north road and the south road. Each market has an expected takings figure in pounds, positive on a good day and negative on a wet one where the pitch fee is not covered.

A run starts at the home market and ends at a market with no onward booking at all. Find every run whose takings add up to exactly target.

Input. route — the route sheet read level by level: the home market, then the two it books, then theirs, None where a road is not booked. target — the takings the trader wants to hit.

Output. A list of runs, each the takings along it, home market first. Runs may come back in any order.

Example.

              70
            /    \
         -40      60
         /  \    /   \
        90   50 -10   80
                        \
                        -90

route  = [70, -40, 60, 90, 50, -10, 80,
          None, None, None, None, None, None, None, -90]
target = 120

  ->  [[70, -40, 90], [70, 60, -10], [70, 60, 80, -90]]

Three runs hit 120. The third is over target at 70 + 60 + 80 = 210 before the last market loses 90.

A second example, on the same route:

target = 210   ->   []

The takings do reach 210, at the market taking 80 — but that market still has the south road booked, so it is not the end of a run. Nothing ends on 210.

Constraints.

• 0 <= markets <= 5000
• -1000 <= takings <= 1000
• -10^6 <= target <= 10^6

Hints

Approach

Brute force

List the markets with no onward booking, then for each one search the route sheet from home again to work out how you got there and what the takings were. Each search walks the tree, and half the markets on a fully booked route are ends, so that is 2500 walks of 5000 markets: 12.5 million visits where one walk covers 5000.

The insight

Carry the trail and the shortfall down with the recursion and record only where both roads are unbooked — one walk answers the whole question.

Each market is entered once, and at that moment the trail already holds exactly the takings from home to here, because the caller pushed its own figure before descending. Popping once both roads have been tried restores the trail for the sibling road, so the same list is correct everywhere without ever being rebuilt. What this does not buy is a shortcut: takings can be negative, so a running total above target says nothing about what the rest of the run will do.

Algorithm

1. Build the route from the level-by-level sheet.
2. Keep an empty trail and an empty list of runs.
3. At a market, push its takings onto trail and subtract them from the remaining target.
4. If both roads are unbooked and the remainder is 0, copy trail into runs.
5. Otherwise visit the north road, then the south road.
6. Pop the takings off trail before returning.

Complexity

Time O(n·h) — each of the n markets is visited once, and recording a matching run copies up to h figures. Space O(h) for the trail and the frames, plus the answer itself.

Solution

"""Break-even on the market run — collect every full run reaching a target total,
carrying one trail and undoing it on the way back."""

import sys
from collections import deque

sys.setrecursionlimit(20000)   # a route with no choices is n frames deep


class Market:
    """One stall day. `takings` is profit in pounds, negative on a bad day."""

    def __init__(self, takings):
        self.takings = takings
        self.north = None
        self.south = None


def book(route):
    """Level-order route sheet, None where an onward market is not booked."""
    if not route or route[0] is None:
        return None
    home = Market(route[0])
    queue, i = deque([home]), 1
    while queue and i < len(route):
        stop = queue.popleft()
        if i < len(route) and route[i] is not None:
            stop.north = Market(route[i])
            queue.append(stop.north)
        i += 1
        if i < len(route) and route[i] is not None:
            stop.south = Market(route[i])
            queue.append(stop.south)
        i += 1
    return home


def solve(route, target):
    runs, trail = [], []

    def drive(stop, left):
        # invariant: trail holds the takings from the home market down to stop,
        # and left is target minus their total before stop is counted.
        if stop is None:
            return
        trail.append(stop.takings)
        left -= stop.takings
        if stop.north is None and stop.south is None and left == 0:
            runs.append(list(trail))   # copy: trail keeps changing underneath
        else:
            drive(stop.north, left)
            drive(stop.south, left)
        trail.pop()                    # undo before the caller tries its other road

    drive(book(route), target)
    return runs


CIRCUIT = [70, -40, 60, 90, 50, -10, 80,
           None, None, None, None, None, None, None, -90]
SPUR = [20, 20, None, 20]

TESTS = [
    ((CIRCUIT, 120), [[70, -40, 90], [70, 60, -10], [70, 60, 80, -90]]),
    ((CIRCUIT, 210), []),
    ((CIRCUIT, 80), [[70, -40, 50]]),
    ((SPUR, 60), [[20, 20, 20]]),
    ((SPUR, 40), []),
    (([50], 50), [[50]]),
    (([50], 0), []),
    (([], 0), []),
]

Pitfalls

• Abandoning a branch once the running total passes the target. The third run above is at 210 against a target of 120 and still becomes an answer. That prune is only legal when every figure is non-negative, and here they are not.
• Appending trail rather than list(trail). Every run in the answer is then the same list object, and the trail is empty by the end, so the result is [[], [], []].
• Testing if market.north is None for the end of a run. The market taking 80 has no north road but does have a south road, so that test reports [70, 60, 80] at target 210 — the case the second example rules out.
• Forgetting the pop. The trail keeps the north road's markets while the south road is walked, and every run after the first comes back too long.

Variants

• Bringing the grid back — the same tree walked across in rows rather than downwards, and no trail to keep.
• Structure and paths — the split between what a call returns and what it records on the way past.