# Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode.

For instance, if I enter the stream $012345$, I am trying each of the combinations $0123$, $1234$, and $2345$.

Clearly, a 40000-length string $000000010002...9999$ is guaranteed to crack the safe.

Can we try each of the 10000 combinations using a shorter string? What's the shortest string we can devise to try every combination?

## 1 Answer

The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those sequences would cross the join. So, for a linear sequence, you need to repeat the first three items at the end, giving $10\,003$, improving on the obvious solution of length $40\,000$.

(Thanks to PålGD for pointing out the issue with cyclicity.)

• When you say the sequence has length $10^4$. Shouldn't that be $10^4 + 3$? i.e. $n + k^n -1$ for $k=10$ and $n=4$?, i.e. entering the first n-digit sequence (combination), and then entering one digit for each of the remaining $k^n-1$ combinations. – Amelio Vazquez-Reina May 4 '20 at 4:11