Tasting flight

A taproom wants a card showing every flight a customer could order. The board is not a list to scan; it is a row of yes-or-no decisions.

The problem

A cider taproom pours from a board of taps, each tap a different cider, chalked up left to right. A flight is any selection from that board: one pour, several, all of them, or none at all. The empty flight counts: ordering nothing is one of the options.

Print the card: every flight that could be ordered, each once. Two flights are the same when they hold the same ciders, so a flight is written in board order — ["dry", "oak"] and ["oak", "dry"] are one flight.

Input. pours — a list of distinct cider names, in board order.

Output. A list of flights, each a list of names in board order. The flights may come in any order, but each appears once.

Example.

pours = ["dry", "oak", "plum"]

->  [[], ["dry"], ["oak"], ["plum"],
     ["dry", "oak"], ["dry", "plum"], ["oak", "plum"],
     ["dry", "oak", "plum"]]

Eight flights for three taps: each tap is in or out, and 2 × 2 × 2 = 8.

A second example, at the edge of the board:

pours = []            ->  [[]]
pours = ["scrumpy"]   ->  [[], ["scrumpy"]]

An empty board still has one flight, the empty one: a list holding one empty list, not an empty list.

Constraints.

• 0 <= len(pours) <= 16
• names are distinct, 1 to 12 lowercase letters
• at sixteen taps the card runs to 65,536 flights

Hints

Approach

Brute force

Write out every ordered tasting sequence — a first cider, then a second from what is left — and discard the reorderings of sequences already on the card. That is about e · 16! ≈ 5.7 × 10¹³ sequences for 65,536 flights: close to a billion discards per line kept.

The insight

Each tap is one independent yes-or-no decision, so the flights are exactly the leaves of a binary tree of depth n — recurse on "take this pour or skip it" and record the path when the board runs out.

The precondition is that the decisions do not interact: a flight is a set, with no budget or ordering to couple the taps, so taking oak cannot change what plum may do. And because the tree fixes one decision per tap in board order, a flight and a root-to-leaf path are the same object — every flight is reached once, so nothing needs deduplicating.

Algorithm

1. Keep one shared list flight and an index i into the board.
2. If i has run past the last tap, append a copy of flight and return.
3. Recurse on i + 1 with flight untouched — the skip branch.
4. Append pours[i], recurse on i + 1, then pop it — the take branch, undone on the way back up.
5. Start at i = 0 with an empty flight.

Complexity

Time O(n · 2ⁿ) — 2ⁿ leaves, and copying a flight costs up to n. Space O(n) for the stack and the shared buffer, ignoring the output itself.

Solution

"""Tasting flight — every flight on the board by include or exclude recursion."""


def solve(pours):
    flights = []
    flight = []

    def decide(i):
        # invariant: `flight` holds a settled decision for every tap before i,
        # and the taps from i onward are still open.
        if i == len(pours):
            flights.append(list(flight))   # copy: `flight` keeps being edited
            return
        decide(i + 1)                      # skip tap i
        flight.append(pours[i])
        decide(i + 1)                      # take tap i
        flight.pop()                       # un-choose, restoring the invariant

    decide(0)
    return flights

TESTS = [
    ((["dry", "oak", "plum"],), [
        [], ["dry"], ["oak"], ["plum"],
        ["dry", "oak"], ["dry", "plum"], ["oak", "plum"],
        ["dry", "oak", "plum"],
    ]),
    (([],), [[]]),                          # the empty board still has one flight
    ((["scrumpy"],), [[], ["scrumpy"]]),
    ((["dry", "oak"],), [[], ["dry"], ["oak"], ["dry", "oak"]]),
    ((["stout", "dry", "oak", "plum"],), [
        [], ["plum"], ["oak"], ["oak", "plum"],
        ["dry"], ["dry", "plum"], ["dry", "oak"], ["dry", "oak", "plum"],
        ["stout"], ["stout", "plum"], ["stout", "oak"], ["stout", "oak", "plum"],
        ["stout", "dry"], ["stout", "dry", "plum"], ["stout", "dry", "oak"],
        ["stout", "dry", "oak", "plum"],
    ]),
]

Pitfalls

• Appending flight rather than list(flight). All 2ⁿ entries then alias one buffer, and the pops keep running after the leaf, so the three-tap board prints eight empty flights.
• Skipping the pop after the take branch. The buffer never shrinks, so a later skip branch inherits ciders it did not choose: you get ["dry", "oak", "plum"] where ["dry"] belongs, and no singleton ever appears.
• Returning [] for an empty board. The base case records the empty path; it does not decline to record. Code opening if not pours: return [] prints a card with no options on it.

Variants

• Pipette doses — the same tree, but a branch may repeat itself and a running total prunes it.
• The recursion framework — the five steps behind this recursion.