Problem 79: Passcode Derivation

Mathematical Foundation

Definition 1 (Subsequence Constraint). A login attempt $d_1 d_2 d_3$ imposes the constraint that characters $d_1$, $d_2$, $d_3$ appear in this relative order (not necessarily consecutively) within the passcode.

Definition 2 (Precedence Graph). The precedence graph is a directed graph $G = (V, E)$ where $V$ is the set of distinct digits appearing in the login data and $(u, v) \in E$ if and only if some login attempt contains $u$ before $v$ (i.e., $u = d_i$ and $v = d_j$ with $i < j$ in some attempt $d_1 d_2 d_3$).

Assumption (No Repeated Digits). We assume the passcode contains each digit at most once. This is justified a posteriori: if the resulting DAG admits a valid topological ordering of length $|V|$ that satisfies all constraints, then no repetition is needed.

Theorem 1 (Acyclicity). Under the no-repetition assumption, $G$ is a directed acyclic graph (DAG).

Proof. Suppose $G$ contains a directed cycle $v_1 \to v_2 \to \cdots \to v_k \to v_1$. Then the passcode requires $v_1$ to appear before $v_2$, $v_2$ before $v_3$, …, and $v_k$ before $v_1$. By transitivity of the “precedes” relation, $v_1$ must appear strictly before itself. Since each digit appears exactly once, this is impossible. Hence $G$ is acyclic. $\blacksquare$

Theorem 2 (Minimality of Topological Ordering). If $G$ is a DAG on $|V|$ vertices, then any topological ordering of $G$ yields a string of length $|V|$ respecting all precedence constraints, and no shorter string containing all digits of $V$ exists.

Proof. A topological ordering $v_{\sigma(1)}, v_{\sigma(2)}, \ldots, v_{\sigma(|V|)}$ has the property that $(v_{\sigma(i)}, v_{\sigma(j)}) \in E$ implies $i < j$. Thus every precedence constraint is satisfied. The string has length $|V|$, and any string containing all $|V|$ distinct digits must have length $\geq |V|$. $\blacksquare$

Theorem 3 (Uniqueness via Hamiltonian Path). A DAG has a unique topological ordering if and only if it contains a Hamiltonian path. Equivalently, at each step of Kahn’s algorithm, there is exactly one vertex with in-degree $0$.

Proof. ($\Rightarrow$) Let $v_1, v_2, \ldots, v_n$ be the unique topological order. Suppose edge $(v_i, v_{i+1}) \notin E$ for some $i$. Then $v_i$ and $v_{i+1}$ have no direct precedence constraint between them. Moreover, swapping them yields a sequence $v_1, \ldots, v_{i-1}, v_{i+1}, v_i, v_{i+2}, \ldots, v_n$. We claim this is also a valid topological ordering: the only pair whose relative order changed is $(v_i, v_{i+1})$, and since $(v_i, v_{i+1}) \notin E$, no constraint is violated. (We also need $(v_{i+1}, v_i) \notin E$, which holds since $v_i$ precedes $v_{i+1}$ in the original valid ordering.) This contradicts uniqueness. Hence $(v_i, v_{i+1}) \in E$ for all $i$, forming a Hamiltonian path.

($\Leftarrow$) Let $v_1 \to v_2 \to \cdots \to v_n$ be a Hamiltonian path. Then $v_1$ is the unique vertex with in-degree $0$ in $G$ (any other vertex $v_j$ with $j > 1$ has the incoming edge from $v_{j-1}$). Removing $v_1$ and its outgoing edges, $v_2$ becomes the unique vertex with in-degree $0$ in the residual graph. By induction, each step of Kahn’s algorithm has a unique choice, producing a unique topological ordering. $\blacksquare$

Theorem 4 (Correctness of Kahn’s Algorithm). Given a DAG $G = (V, E)$, Kahn’s algorithm outputs a valid topological ordering.

Proof. The algorithm maintains a queue $Q$ of vertices with in-degree $0$ and repeatedly: (i) dequeues a vertex $v$, (ii) appends $v$ to the output sequence, and (iii) for each outgoing edge $(v, w)$, decrements the in-degree of $w$ and enqueues $w$ if its in-degree reaches $0$.

We prove the output $v_{\sigma(1)}, \ldots, v_{\sigma(|V|)}$ is a valid topological ordering by contradiction. Suppose $(u, w) \in E$ but $w$ appears before $u$ in the output. Then $w$ was dequeued before $u$. At the time $w$ was dequeued, its in-degree was $0$, meaning every predecessor of $w$ (including $u$, since $(u, w) \in E$) had already been removed from the graph. But $u$ has not yet been dequeued, so it has not been removed—a contradiction. $\blacksquare$

Lemma 1 (Extracted Graph for the Given Data). From the 50 login attempts, the distinct digits are $V = \{0, 1, 2, 3, 6, 7, 8, 9\}$ (digits $4$ and $5$ never appear, $|V| = 8$). The extracted precedence edges form a DAG with a unique topological ordering: $7, 3, 1, 6, 2, 8, 9, 0$.

Proof. Extracting all ordered pairs from each 3-digit attempt (3 pairs per attempt) and computing in-degrees in the resulting DAG, Kahn’s algorithm proceeds:

1. In-degree $0$: only vertex $7$.
2. Remove $7$: only vertex $3$ has in-degree $0$.
3. Remove $3$: only vertex $1$ has in-degree $0$.
4. Continue: $6$, then $2$, then $8$, then $9$, then $0$.

At each step, exactly one vertex has in-degree $0$, confirming uniqueness by Theorem 3. $\blacksquare$

Editorial

Each login attempt gives relative-order information, not exact positions. So the natural model is a precedence graph: from a triple $abc$ we learn that $a$ must come before $b$, $a$ before $c$, and $b$ before $c$. Repeating this over all attempts produces a directed graph on the digits that actually appear.

Once the graph is built, the shortest passcode is just a topological ordering of that graph. No extra digits are needed, because every distinct digit in the graph must appear at least once and a valid topological order already satisfies every subsequence constraint. Kahn’s algorithm generates the passcode by repeatedly taking a digit whose remaining in-degree is zero, appending it to the answer, and deleting its outgoing constraints. In this dataset the choice is unique at every stage, so the passcode is forced.

Pseudocode

Collect the distinct digits that appear in the login attempts.

For each three-digit attempt:
    add the precedence edges implied by its relative order

Compute the in-degree of every digit.
Place all digits with in-degree zero into the processing queue.

While the queue is not empty:
    remove the next digit from the queue and append it to the passcode

    For each digit that must come after it:
        decrease that digit's in-degree
        if the in-degree becomes zero, place it into the queue

Return the concatenation of the chosen digits.

Complexity Analysis

Time: Graph construction scans 50 attempts, extracting $\binom{3}{2} = 3$ ordered pairs each, with $O(1)$-amortized hash set membership checks. Total: $O(150)$. Kahn’s algorithm runs in $O(|V| + |E|)$. With $|V| = 8$ and $|E| \leq 56$ (at most $\binom{8}{2}$ directed edges): $O(1)$ for this fixed input.

Space: $O(|V| + |E|)$ for the adjacency representation and in-degree array.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<string> attempts = {
        "319", "680", "180", "690", "129", "620", "762", "689", "762", "318",
        "368", "710", "720", "710", "629", "168", "160", "689", "716", "731",
        "736", "729", "316", "729", "729", "710", "769", "290", "719", "680",
        "318", "389", "162", "289", "162", "718", "729", "319", "790", "680",
        "890", "362", "319", "760", "316", "729", "380", "319", "728", "716"
    };

    // Build precedence DAG
    set<int> digits;
    map<int, set<int>> adj;

    for (auto& s : attempts) {
        int a = s[0] - '0', b = s[1] - '0', c = s[2] - '0';
        digits.insert({a, b, c});
        adj[a].insert(b);
        adj[a].insert(c);
        adj[b].insert(c);
    }

    // Compute in-degrees from the adjacency sets
    map<int, int> indeg;
    for (int d : digits) indeg[d] = 0;
    for (int d : digits)
        for (int v : adj[d])
            indeg[v]++;

    // Kahn's algorithm (topological sort)
    queue<int> q;
    for (int d : digits)
        if (indeg[d] == 0)
            q.push(d);

    string result;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result += ('0' + u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0)
                q.push(v);
        }
    }

    cout << result << endl;
    return 0;
}

"""
Problem 79: Passcode Derivation

Given 50 successful login attempts (3-digit subsequences), determine the
shortest possible secret passcode via topological sort of the precedence DAG.
Answer: 73162890
"""

from collections import defaultdict, deque


def main():
    attempts = [
        "319", "680", "180", "690", "129", "620", "762", "689", "762", "318",
        "368", "710", "720", "710", "629", "168", "160", "689", "716", "731",
        "736", "729", "316", "729", "729", "710", "769", "290", "719", "680",
        "318", "389", "162", "289", "162", "718", "729", "319", "790", "680",
        "890", "362", "319", "760", "316", "729", "380", "319", "728", "716",
    ]

    # Build the precedence DAG
    digits = set()
    edges = set()
    for s in attempts:
        a, b, c = int(s[0]), int(s[1]), int(s[2])
        digits.update([a, b, c])
        edges.add((a, b))
        edges.add((a, c))
        edges.add((b, c))

    adj = defaultdict(set)
    indeg = {d: 0 for d in digits}
    for u, v in edges:
        adj[u].add(v)
    for u in digits:
        for v in adj[u]:
            indeg[v] += 1

    # Kahn's algorithm (topological sort)
    queue = deque(d for d in sorted(digits) if indeg[d] == 0)
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in sorted(adj[u]):
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    print("".join(str(d) for d in result))


if __name__ == "__main__":
    main()