Acme has released a brand new safe, secured with electronic 10-button keypad with the digits 0 through 9, with an X-length combination required to unlock. However, due to laziness, the keypad's programmer decides that, instead of requiring a new attempt each time, the safe will only consider the last $x$ button presses.
So, with $x=2$, if I were to press $1234$, the safe would evaluate whether $12$, $23$, and $34$ were valid combinations, while a traditional keypad safe would only evaluate $12$ and $34$.
For all values $x$, the worst case would be to try all combinations in serial, resulting in $10^x$ combinations of $x$ button presses, or $x \times 10^x$ presses. With $x=4$, we'd end up pressing this keypad up to $40,000$ times!
What is the best-case number of button presses to attempt all possible combinations for a combination of length $x$, and what is the list of button presses for $x=2$?
Answer
The way to do it is
a De Bruijn sequence. Basically, it's a sequence $B(k,n)$ that contains all sequences of length $n$ made of $k$ different characters.
The number of keypresses for the length $x$ is
$10^x + (x - 1)$. A De Bruijn sequence is cyclic (end connects back to start) with length $k^n$, so we just need to add the starting $x - 1$ keypresses to the end.
The keypresses for $x = 2$ are
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990, as generated by the algorithm on Wikipedia.
No comments:
Post a Comment