The shared starter

A bakery keeps every jar it has ever split off its sourdough. Two jars are misbehaving, and the baker needs to know how far back the fault could have entered.

The problem

The bakery's lineage board records one original jar and every split since. When a jar is split, its culture goes into at most two new jars, both recorded hanging under it. Codes are stamped on the lid when a jar comes back from the wash, so they say nothing about the lineage: a jar split off 31 may be stamped 47, and the jar beside it 22.

Two jars are proving badly. The baker wants the most recent jar both of them came from, so everything below it can be discarded and re-cultured from there. A jar counts as coming from itself, so if one of the two is already upstream of the other, that jar is the answer.

The board arrives in compact level-order form — the original jar, then each layer of splits left to right, None where a split produced only one jar. A gap records no splits of its own, and trailing gaps are trimmed.

Input. lineage — the board in compact level-order form. first_jar, second_jar — two codes, both on the board.

Output. The code of the most recent jar both came from.

Example.

lineage = [31, 47, 22, 8, 19, None, 5, None, None, 60, 14]
first_jar = 8, second_jar = 14   ->  47

Jar 31 was split into 47 and 22; 47 into 8 and 19; 19 into 60 and 14. Jar 8 and jar 14 both come from 47, and from nothing more recent.

A second example, one jar upstream of the other, and one pair whose codes mislead:

first_jar = 47, second_jar = 60   ->  47
first_jar = 60, second_jar = 14   ->  19

Jar 60 comes from 19, which comes from 47, so 47 itself is the answer to the first pair. In the second pair both codes are below 31, and 14 is below 47 while 60 is above it — deciding a direction by comparing codes would stop at 47 and miss 19 entirely.

Constraints.

• 1 <= jars <= 10^4
• 1 <= jar code <= 10^6, all distinct
• both codes appear on the board
• the board may be a single chain of splits, 10^4 jars deep

Hints

Approach

Brute force

For every jar on the board, check whether both codes appear somewhere below it and keep the deepest that passes. Each check walks a whole branch, so the cost is O(n²): 10^8 jar visits for 10^4 jars, most of them re-walking branches already scanned.

The insight

Each jar came from exactly one jar, so the trail back to the original is unique — write one trail down and climb the other until it lands on a jar already on it.

Uniqueness of the parent is the precondition, and a lineage board guarantees it. It makes the jars above any jar a single chain rather than a branching search, and both chains end at the original, so they must meet. The first meeting point found while climbing the second chain is the answer: it is on both chains, and every jar below it there was checked first and rejected.

Algorithm

1. Sweep the board once, recording for each jar code the code it was split from.
2. Climb from first_jar, adding each code to a set — starting with first_jar itself — until there is no parent.
3. Climb from second_jar the same way, checking each code against the set.
4. Return the first code that is in it. The original jar guarantees a hit.

Complexity

Time O(n) — one sweep to record parents, then two climbs of at most the height. Space O(n) for the parent record and the set of the first trail.

Solution

"""The shared starter — meet the two upward jar chains, lowest jar first."""

from collections import deque


def parent_of(lineage):
    """Map every jar code to the code of the jar it was split from."""
    parents = {}
    if not lineage or lineage[0] is None:
        return parents
    parents[lineage[0]] = None
    queue = deque([lineage[0]])
    i = 1
    while queue and i < len(lineage):
        # invariant: only real jars are queued, so a gap never claims split slots
        code = queue.popleft()
        for _ in range(2):
            if i >= len(lineage):
                break
            value = lineage[i]
            i += 1
            if value is not None:
                parents[value] = code
                queue.append(value)
    return parents


def solve(lineage, first_jar, second_jar):
    parents = parent_of(lineage)

    seen = set()
    jar = first_jar
    while jar is not None:          # a jar counts as its own ancestor, so start here
        seen.add(jar)
        jar = parents.get(jar)

    jar = second_jar
    while jar is not None:
        # invariant: every jar below this one on the second chain has been ruled out,
        # so the first jar found on both chains is the lowest shared one
        if jar in seen:
            return jar
        jar = parents.get(jar)
    return None


BOARD = [31, 47, 22, 8, 19, None, 5, None, None, 60, 14]

TESTS = [
    ((BOARD, 8, 14), 47),
    ((BOARD, 47, 60), 47),
    ((BOARD, 60, 5), 31),
    ((BOARD, 60, 14), 19),
    (([9], 9, 9), 9),
    (([4, 6, None, 11, None, 2], 2, 11), 11),
]

Pitfalls

• Descending by comparing codes. The board is not ordered: 47 hangs under 31 even though it is larger. For jars 60 and 14 a comparison-driven descent turns left at 31, then sees 60 above 47 and 14 below it, and answers 47 — but the true answer is 19.
• Starting the first climb at the parent. A jar counts as coming from itself. Skipping first_jar answers 31 for the pair 47 and 60, when 47 is the answer.
• Recursing down the board. The postorder version of this search is short, but a 10^4-jar chain passes Python's default recursion limit of 1000 and raises RecursionError. The two climbs use no stack frames at all.
• Queueing gaps while reading the board. A None records no splits, so treating it as a jar shifts every later code under the wrong parent and jars 60 and 14 hang off nothing.

Variants

• Call-out rounds — the same chains, measured for length rather than matched against each other.
• Structure and paths — the postorder shape that answers the same question in one pass, and when it is safe to use.