The cold store keyring

A fish market cold store has numbered chambers, each locked, each holding a handful of brass tags for other chambers. Only chamber 0 stands open at the start of the shift.

The problem

The chambers are numbered 0 to n - 1. Hanging inside chamber i is a list of tags, and a tag stamped j opens chamber j. Chamber 0 is unlocked; every other chamber stays shut until you are holding a tag for it.

You may walk into any chamber you have opened, take every tag hanging in it, and use those tags to open more chambers, in any order and as often as you like. A chamber may hold a tag for itself, or for a chamber already open — those tags are simply redundant. A tag may also appear in several chambers.

Decide whether the whole store can be opened. Return True if every chamber can be reached and False if at least one stays shut.

Input. chambers — a list of n lists of integers. chambers[i] is the tags found inside chamber i.

Output. True if all n chambers can be opened starting from chamber 0, otherwise False.

Example.

chambers = [[1], [2], [3], []]   ->  True

Chamber 0 gives the tag for 1, which gives 2, which gives 3. The last chamber holds nothing, which is fine — every chamber has been opened.

A second example, where the tags form a closed loop you can never enter:

chambers = [[1, 3], [3, 0, 1], [2], [0]]   ->  False

From 0 you reach 1 and 3, and those two only lead back to 0 and to each other. The only tag for chamber 2 hangs inside chamber 2, so it is never opened, and the answer is False even though every chamber has a tag somewhere in the store.

Constraints.

• 1 <= n <= 10^5
• 0 <= chambers[i][j] < n
• the total number of tags across all chambers is at most 10^5
• a chamber may hold duplicate tags, or a tag for itself

Hints

Approach

Brute force

Simulate a shift. Keep a bag of tags, repeatedly sweep the bag looking for one that opens a shut chamber, empty that chamber into the bag, and start the sweep again. Each sweep costs O(n) and can open one chamber, so the simulation runs to O(n²) — 10¹⁰ steps at the stated bound.

The insight

Opening a chamber is monotone — nothing you do can lock one again — so the set of openable chambers is exactly the set reachable from node 0, and one traversal computes it.

Because a chamber never closes, the order of collection is irrelevant: any chamber openable by some sequence of moves is openable by the traversal, since the traversal only ever waits for a predecessor that is itself openable. The precondition the pattern needs is that edges are never removed; that is what lets a single visited flag replace the whole keyring.

Algorithm

1. Mark chamber 0 open and push it on a stack. Keep a running count of 1.
2. Pop a chamber and look at each tag hanging in it.
3. If the tagged chamber is not yet open, mark it, add one to the count, and push it.
4. Repeat until the stack is empty.
5. Return whether the count equals n.

Complexity

Time O(n + t), t the total number of tags — each chamber is pushed once and each tag is inspected once. Space O(n) for the flags and the stack.

Solution

"""The cold store keyring — reachability from chamber 0 by depth-first search."""


def solve(chambers):
    total = len(chambers)
    opened = [False] * total
    opened[0] = True                       # chamber 0 is unlocked to begin with
    stack = [0]
    count = 1
    while stack:
        # Invariant: every chamber marked opened is reachable from 0 using only
        # tags found in chambers already opened.
        current = stack.pop()
        for tag in chambers[current]:
            if not opened[tag]:
                opened[tag] = True
                count += 1
                stack.append(tag)
    return count == total

TESTS = [
    (([[1], [2], [3], []],), True),
    (([[1, 3], [3, 0, 1], [2], [0]],), False),
    (([[]],), True),
    (([[], [0]],), False),
    (([[1, 2], [3], [3], []],), True),
    (([[2, 0], [], [1], [0]],), False),
]

Pitfalls

• Recursing instead of using a stack. A store laid out as one long chain, [[1], [2], [3], ...], recurses n deep, and Python stops near 1,000. Write the traversal with an explicit stack.
• Marking a chamber open when you pop it rather than when you push it. A chamber reachable from two others is then pushed twice and counted twice, and a store like [[1, 2], [3], [3], []] reports 5 opened out of 4 — the check count == n silently fails.
• Concluding True because every chamber number appears on some tag. In the second example every chamber is tagged somewhere, yet chamber 2 is unreachable. Being tagged is not the same as being reachable from 0.

Variants

• Conservation precedence — reachability again, but asked once per pair rather than once from a fixed start.
• BFS and DFS — the traversal skeleton and why the visited mark belongs on the push.