Cracking the Safe

Cracking the Safe looks like a brute-force nightmare — try every password until one works — but it is secretly a graph problem. The trick is to see that overlapping passwords share digits, and to find the one string that packs all of them together: a De Bruijn sequence, built by an Eulerian walk.

The slow way first

The naive idea: list all k^n passwords and concatenate them. For n = 2, k = 2 that is 00 + 01 + 10 + 11 = "00011011", length 8. It works, but it wastes digits — it never reuses the overlap between one password and the next.

The question to ask: can the end of one password be the start of the next? The password 00 ends in 0, which is exactly where 01 starts. If we overlap them, 001 already contains both 00 and 01 using only 3 digits instead of 4. Chasing that overlap all the way gives the optimal length k^n + (n − 1).

The idea: walk a prefix graph

Make every (n − 1)-digit prefix a node. For n = 2 the prefixes are single digits: "0" and "1". Appending a digit d to a prefix is a directed edge that lands on the new prefix (drop the oldest digit, keep the last n − 1). Each edge corresponds to exactly one length-n substring.

If we can walk a path that crosses every edge exactly once (an Eulerian trail), the digits we append along the way spell a string containing every password. A greedy Hierholzer DFS — always take any unused edge, backtrack when stuck — finds it.

The key insight: covering every length-n substring is the same as using every edge of this prefix graph, and a De Bruijn sequence is exactly its Eulerian trail.

Walk through it

Step through the animation. We seed the string with "0" and stand on prefix "0". From each prefix we greedily try the smallest digit whose substring has not been used: 00, then 01, then 11, then 10. Each accepted digit gets appended to the password. After four edges every substring is covered and the string reads "00110".

Pseudocode

start = "0" repeated (n - 1) times      # any (n-1)-length prefix
seen = empty set                        # substrings already used (= edges taken)
password = empty list
 
dfs(node):                              # node is the current prefix
    for d in 0 .. k-1:                  # try each digit, smallest first
        substring = node + d
        if substring not in seen:
            mark substring as seen
            dfs(last n-1 chars of substring)   # walk the edge
            append d to password               # record on the way back
 
dfs(start)
answer = password joined together + start

The Python solution

def crack_safe(n, k):
    start = "0" * (n - 1)
    seen = set()
    password = []
 
    def dfs(node):
        for d in map(str, range(k)):
            nxt = node + d
            if nxt not in seen:
                seen.add(nxt)
                dfs(nxt[1:])
                password.append(d)
 
    dfs(start)
    return "".join(password) + start

• start is the seed prefix of n − 1 zeros; for n = 2 that is just "0".
• seen is the set of length-n substrings we have already used — equivalently, the edges crossed.
• dfs(node) stands on a prefix and tries each digit d in order (range(k) keeps it greedy/smallest).
• nxt = node + d is the substring this edge represents; if it is new, we take the edge: mark it seen and recurse into nxt[1:], the new (n − 1)-prefix.
• password.append(d) runs on the way back up (post-order). This Hierholzer detail guarantees the appended digits compose a valid Eulerian trail even when the DFS has to backtrack.
• The final + start re-attaches the seed prefix so the very first password also appears.

Complexity

There are k^n substrings, so there are k^n edges and the DFS touches each once. The output string has length k^n + (n − 1) — provably the shortest possible. The seen set also holds k^n entries, giving O(k^n) space.

When this pattern shows up

Practice