35. Derive Pipeline Stage Order

Problem

Fin's pipeline logs record, for each run, the sequence of stage codes (single letters) that ran, always in a validly-ordered sequence end to end. Given a list of such observed sequences, derive ONE total ordering of stage codes that is consistent with every pairwise ordering constraint implied by the logs, or determine that no consistent ordering exists.

This is the same structure as the classic "Alien Dictionary" problem (LeetCode 269), with stage codes in place of alphabet letters. For each CONSECUTIVE pair of sequences, find the first index where they differ — the character in the first sequence must come before the character in the second. Build a graph from all such edges across the whole list, then topologically sort the discovered characters. Any character that appears but is never involved in a constraint is appended, in first-seen order, after the constrained characters. Raise ValueError("invalid ordering") if the constraints form a cycle, or if a longer sequence is a strict prefix-extension of a shorter sequence that appears immediately before it (a prefix can never validly come after its own extension).

Source: src/35_derive_pipeline_stage_order.py

def derive_order(observed_sequences: list[str]) -> str:

>>> derive_order(["wrt", "wrf", "er", "ett", "rftt"])
'wertf'
>>> derive_order(["abc", "ab"])
Traceback (most recent call last):
    ...
ValueError: invalid ordering

Step-by-Step Approach

1. Collect every distinct character across all sequences as a node, preserving first-seen order for later use.
2. Walk consecutive pairs of sequences. For each pair, scan both strings in lockstep and find the first index where the characters differ — that gives a directed edge "char in seq A precedes char in seq B."
3. If no differing character is found before one sequence runs out, and the earlier sequence is strictly longer than the later one, that's an invalid ordering (a longer string can't validly precede a shorter prefix of itself) — raise immediately.
4. Build an adjacency list and in-degree count for every node touched by at least one edge (the "constrained" set).
5. Run Kahn's algorithm: seed a queue with constrained nodes that have in-degree 0, repeatedly pop a node, append it to the result, and decrement in-degree for its neighbors, enqueuing any that reach 0.
6. If the number of nodes emitted doesn't match the number of constrained nodes, there was a cycle — raise ValueError("invalid ordering").
7. Append any character that was never part of a constraint, in first-seen order, after the topologically sorted constrained characters, and join everything into the result string.

The key insight is that only consecutive sequences give useful information (any ordering constraint between sequence 1 and sequence 3 is already implied transitively through sequence 2), and that a topological sort finding a cycle is exactly the signal that the input data is self-contradictory.

Reference solution

from collections import deque


def derive_order(observed_sequences: list[str]) -> str:
    # classic Alien Dictionary (LC269): build edges from first differing char
    # between consecutive sequences, then Kahn's-algorithm topo sort,
    # O(C) time/space where C = total characters across all sequences
    nodes: dict[str, None] = {}
    for seq in observed_sequences:
        for ch in seq:
            # ordered set of distinct chars, first-seen order
            nodes.setdefault(ch, None)

    adjacency: dict[str, set[str]] = {c: set() for c in nodes}
    in_degree: dict[str, int] = {c: 0 for c in nodes}
    # consecutive pairs only
    for seq_a, seq_b in zip(observed_sequences, observed_sequences[1:]):
        matched = False
        # first differing char = an ordering edge
        for c_a, c_b in zip(seq_a, seq_b):
            if c_a != c_b:
                if c_b not in adjacency[c_a]:
                    adjacency[c_a].add(c_b)
                    in_degree[c_b] += 1
                matched = True
                break
        if not matched and len(seq_a) > len(seq_b):
            raise ValueError("invalid ordering")

    constrained = {c for c in nodes if adjacency[c] or in_degree[c] > 0}
    # Kahn's FIFO queue
    queue = deque(c for c in nodes if c in constrained and in_degree[c] == 0)
    order: list[str] = []
    while queue:
        # O(1) pop from front
        node = queue.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(constrained):
        raise ValueError("invalid ordering")

    unconstrained = [c for c in nodes if c not in constrained]
    return "".join(order) + "".join(unconstrained)

Key Functions & Tricks

• dict.setdefault(key, default) — insert-if-missing; builds an insertion-ordered set of distinct chars.
• zip(seqs, seqs[1:]) — iterates consecutive pairs without manual index arithmetic.
• zip(seq_a, seq_b) + break on mismatch — finds the first differing char position between two strings.
• collections.deque / .popleft() — O(1) FIFO queue for Kahn's algorithm (vs O(n) list.pop(0)).
• Kahn's algorithm — repeatedly emit in-degree-0 nodes; leftover nodes signal a cycle.
• Adjacent-word edges — first differing char between consecutive sorted sequences gives a direct ordering constraint (Alien Dictionary trick).

How to Recognize This Pattern