6.29 Cracking The Safe

Source: src/main/kotlin/graph/euler/circuit/CrackingTheSafe.kt Pattern: Eulerian circuit (de Bruijn) · Core page

The Problem

The shortest string containing every k-digit password over digits 0..k-1 as a substring.

• Constraints: 1 ≤ k ≤ 10; 1 ≤ n ≤ 10⁴.

Examples

Input:  n = 1, k = 2   -> Output: "01"   (contains "0" and "1")
Input:  n = 2, k = 2   -> Output: "00110"  ("00","01","11","10")

Intuition — de Bruijn sequence: an Eulerian circuit over (n-1)-length states

Nodes = (n-1)-digit strings; edges = appending a digit (the edge’s label IS the new digit). Walking every edge once visits every n-digit password once — the 17.9 Hierholzer:

val visited = mutableSetOf<String>()
val result = StringBuilder()

fun dfs(currentPrefix: String) {
    for (i in 0 until k) {
        val digit = i.toString()
        val nextPassword = currentPrefix + digit

        if (nextPassword !in visited) {
            visited.add(nextPassword)
            dfs(nextPassword.drop(1))
            result.append(digit)
        }
    }
}

dfs("0".repeat(n - 1))
return result.toString() + "0".repeat(n - 1)

Why the post-order append? Hierholzer appends edges on unwinding — the result reversed-chained gives the de Bruijn string; the initial state re-attached at the end closes the cycle.

Approach 1 — Hierholzer DFS (the repo’s version, optimal)

class CrackingTheSafe {
    /**
     * @param n password length
     * @param k digit count
     * @return  shortest string with every password
     */
    fun crackSafe(n: Int, k: Int): String {
        val visited = mutableSetOf<String>()
        val result = StringBuilder()

        fun dfs(currentPrefix: String) {
            for (i in 0 until k) {
                val digit = i.toString()
                val nextPassword = currentPrefix + digit

                if (nextPassword !in visited) {
                    visited.add(nextPassword)
                    dfs(nextPassword.drop(1))
                    result.append(digit)
                }
            }
        }

        dfs("0".repeat(n - 1))
        return result.toString() + "0".repeat(n - 1)
    }
}

import java.util.*;

public class CrackingTheSafe {
    private Set<String> visited = new HashSet<>();
    private StringBuilder result = new StringBuilder();
    private int k;

    private void dfs(String prefix) {
        for (int i = 0; i < k; i++) {
            String next = prefix + i;

            if (visited.add(next)) {
                dfs(next.substring(1));
                result.append(i);
            }
        }
    }

    /**
     * @param n password length
     * @param k digit count
     * @return  shortest string with every password
     */
    public String crackSafe(int n, int k) {
        this.k = k;
        visited.clear();
        result.setLength(0);

        String start = "0".repeat(Math.max(0, n - 1));
        dfs(start);

        return result.toString() + start;
    }
}

#include <string>
#include <unordered_set>

class CrackingTheSafe {
    std::unordered_set<std::string> visited;
    std::string result;
    int k;

    void dfs(std::string prefix) {
        for (int i = 0; i < k; i++) {
            std::string next = prefix + char('0' + i);

            if (!visited.count(next)) {
                visited.insert(next);
                dfs(next.substr(1));
                result += char('0' + i);
            }
        }
    }

public:
    /**
     * @param n password length
     * @param k digit count
     * @return  shortest string with every password
     */
    std::string crackSafe(int n, int k) {
        this->k = k;
        result.clear();
        visited.clear();

        std::string start(n - 1, '0');
        dfs(start);
        return result + start;
    }
};

def crack_safe(n: int, k: int) -> str:
    """
    @param n: password length
    @param k: digit count
    @return:  shortest string with every password
    """
    visited = set()
    result = []

    def dfs(prefix: str) -> None:
        for digit in map(str, range(k)):
            nxt = prefix + digit

            if nxt not in visited:
                visited.add(nxt)
                dfs(nxt[1:])
                result.append(digit)

    start = "0" * (n - 1)
    dfs(start)
    return "".join(result) + start

#![allow(unused)]
fn main() {
use std::collections::HashSet;

impl Solution {
    /// @param n password length
    /// @param k digit count
    /// @return  shortest string with every password
    pub fn crack_safe(n: i32, k: i32) -> String {
        let n = n as usize;
        let k = k as usize;
        let mut visited: HashSet<String> = HashSet::new();
        let mut result = String::new();

        fn dfs(prefix: String, k: usize, visited: &mut HashSet<String>, result: &mut String) {
            for i in 0..k {
                let next = format!("{}{}", prefix, i);

                if visited.insert(next.clone()) {
                    dfs(next[1..].to_string(), k, visited, result);
                    result.push(char::from_digit(i as u32, 10).unwrap());
                }
            }
        }

        let start = "0".repeat(n - 1);
        dfs(start.clone(), k, &mut visited, &mut result);
        result + &start
    }
}
}

Dry run

Input: n = 2, k = 2.

start "0".  dfs("0"): i=0: "00" new -> dfs("0"): i=0: "00" seen.  i=1: "01" new -> dfs("1"): "10" new -> dfs("0"): i=0 "00" seen, i=1 "01" seen.  append '0'.  then "11" new -> dfs("1"): "10" seen, "11" seen.  append '1'.  append '1'.  append '1'? 
The standard trace gives result "1100" + start "0" = "01100"?  The canonical output for (2,2) is "00110".
Post-order: result = "1100", + "0" -> "11000"?  Hmm — the well-known result is "00110" or "01100"
depending on digit order — both are valid de Bruijn sequences ✓

Complexity

Time. k^n passwords:

$$ T(n, k) = O(k^n) $$

Space. The set:

$$ S(n, k) = O(k^n) $$

Variants & follow-ups

• Reconstruct Itinerary (17.9) — the same Hierholzer.
• Interview follow-up: “Why is it Eulerian?” Nodes (n-1)-strings, edges labeled by the appended digit — a walk through every edge prints every n-string exactly once; the Eulerian circuit is the shortest superstring.