Call-out rounds

A retained fire crew is called out by telephone, two calls per person. The station wants to know how long the last volunteer waits, and that is not a question about how many volunteers there are.

The problem

The duty officer holds a call-out card. It names the officer at the top and under every name at most two others — the two people that person rings. Everyone appears once, and every name except the officer's is rung by exactly one person.

The card is worked in rounds. Round 1 is the officer alone, round 2 the people the officer rings, round 3 everyone those two ring: a round holds the volunteers who learn of the call-out at the same moment. The station wants the number of rounds on the card — equivalently, the number of people on the longest chain of calls, counting the officer.

The card arrives in compact level-order form — the officer, then each round left to right, None where somebody has fewer than two people to ring. A gap rings nobody of its own, and trailing gaps are trimmed.

Input. cascade — the call-out card in compact level-order form.

Output. The number of rounds. An empty card is 0 rounds.

Example.

cascade = [4, 9, 6, None, 2, None, 7, None, 5]   ->  4

Crew 4 rings 9 and 6. Crew 9 rings only 2, crew 6 rings only 7, and crew 2 rings only 5. The longest chain is 4, 9, 2, 5 — four people, so four rounds. The chain through 6 stops after three.

A second example, two cards where the bigger one finishes sooner:

cascade = [4, 9, 6, 1, 3, 8, 7]   ->  3
cascade = [4, 9, None, 2, None, 1]   ->  4

Seven volunteers in three rounds, four volunteers in four. Rounds are set by the longest chain, not by the size of the crew — a card where everyone rings two people is done in far fewer rounds than a card that has turned into a chain.

Constraints.

• 0 <= volunteers <= 10^4
• 1 <= crew number <= 10^6, all distinct
• the card may be a single chain of calls, 10^4 rounds long

Hints

Approach

Brute force

List every chain from the officer down to a person who rings nobody, keeping each chain as it is built, then take the longest. A card can hold about 5000 chains of up to 10^4 names, so the lists alone run to millions of entries — correct, but it pays to write down chains it then throws away.

The insight

The rounds a person's part of the card needs is one plus the larger of the two below them, so a single visit per name settles it and no chain is ever written down.

The two people somebody rings head disjoint parts of the card, because every volunteer is rung by exactly one person. That is the precondition: it makes the longest chain through a person that person plus the longer of the two sides, with nothing outside able to lengthen it. Sweeping the card a round at a time counts the same quantity from the top — each drained queue is one round.

Algorithm

1. Rebuild the card, queueing only real volunteers so a gap never claims call slots.
2. If the card is empty, return 0.
3. Put the officer in a queue and set rounds to 0.
4. Record the queue's length — that is one whole round — pop exactly that many people, and append everyone they ring behind them.
5. Add 1 to rounds and repeat from step 4 until the queue is empty.
6. Return rounds.

Complexity

Time O(n) — every volunteer is queued once and popped once. Space O(w), the widest round: about 5000 for a card where everyone rings two people, and 1 for a chain. The recursive version costs O(h) stack frames instead, which is 10^4 in the worst case here.

Solution

"""Call-out rounds — count the bands of a phone cascade with one level sweep."""

from collections import deque


class Volunteer:
    """One name on the card: a crew number and the two people they ring."""

    __slots__ = ("crew", "first", "second")

    def __init__(self, crew):
        self.crew = crew
        self.first = None
        self.second = None


def build(level_order):
    """Rebuild the call card from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Volunteer(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real volunteers are queued, so a gap never claims call slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.first = Volunteer(value)
                queue.append(node.first)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.second = Volunteer(value)
                queue.append(node.second)
    return root


def solve(cascade):
    root = build(cascade)
    if root is None:
        return 0
    rounds = 0
    queue = deque([root])
    while queue:
        # invariant: the queue holds exactly the people reached in the last round
        for _ in range(len(queue)):     # size fixed before this round's calls are made
            node = queue.popleft()
            if node.first is not None:
                queue.append(node.first)
            if node.second is not None:
                queue.append(node.second)
        rounds += 1
    return rounds

TESTS = [
    (([4, 9, 6, None, 2, None, 7, None, 5],), 4),
    (([4, 9, 6, 1, 3, 8, 7],), 3),
    (([4, 9, None, 2, None, 1],), 4),
    (([],), 0),
    (([7],), 1),
    (([12, None, 30],), 2),
]

Pitfalls

• Counting names instead of chains. The seven-name card in the second example needs 3 rounds and the four-name card needs 4. len(cascade) is not the answer, and neither is the number of people who ring nobody.
• Counting calls rather than rounds. The chain 4, 9, 2, 5 contains three calls but four rounds, because round 1 is the officer alone. Returning the number of calls answers 3 for the first example.
• Recursing on a chain. One plus the larger side is a two-line recursion, but a 10^4-round card passes Python's default recursion limit of 1000 and raises RecursionError. The queue version holds one round at a time.

Variants

• Canopy walkway check — the same round-by-round sweep, keeping what is in each round instead of counting them.
• The shared starter — walks the same chains the other way, from a name back up to the top of the card.