Cracking the Safe

Problem Summary

A safe is protected by a password that is a sequence of n digits, where each digit ranges from 0 to k - 1. The safe checks the most recent n digits entered each time a new digit is typed. Return any string of minimum length that will unlock the safe at some point during entry. In other words, find the shortest string that contains every possible n-digit combination over the k-symbol alphabet as a contiguous substring. The value of n is at most 4, k is at most 10, and the total number of possible passwords (k^n) is at most 4096.

Techniques

String
Depth-First Search
Graph Theory
Eulerian Circuit

Solution

function hierholzer(node: string, k: number, visited: Set<string>, path: string[]) {
    for (let i = 0; i < k; i++) {
        const edge = node + i;

        if (!visited.has(edge)) {
            visited.add(edge);
            hierholzer(edge.slice(1), k, visited, path);
            path.push(i.toString());
        }
    }
}

function crackSafe(n: number, k: number): string {
    const visited = new Set<string>();
    const path: string[] = [];
    const startNode = "0".repeat(n - 1);

    hierholzer(startNode, k, visited, path);

    return startNode + path.reverse().join("");
}