Let's say I have a keycode doorlock which accepts 4 digit passcodes. In order to enter, you must type the 4 digits of the passcode in a row, but there is no "Enter", and it doesn't reset after 4 digits. Thus, if you entered "11112222", the lock wouldn't just unlock if the passcode was "1111" or "2222", but also if it was "1112", "1122", and "1222". Given this, what is the most efficient series of digits to enter to go through all possible passcodes?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Try the De Bruijn sequence $B(10,4)$. It takes at most 40003 key presses to go through all combinations. On the wiki page, there is a python code to generate $B(k,n)$, the De Bruijn sequence for alphabet $k$ and subsequences of length $n$. $\endgroup$– achille huiCommented Nov 29, 2016 at 6:12
-
$\begingroup$ @achillehui Just a minor correction, there would be 40000 key presses to go through all possible codes sequentially. The De Bruijn sequence only has length 10003. :) $\endgroup$– NicoCommented Nov 29, 2016 at 6:15
-
$\begingroup$ @Nico opps, you are right. I fail to count correctly. $\endgroup$– achille huiCommented Nov 29, 2016 at 6:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There is a strong connection between your question and De Bruijn Sequences. The wikipedia link even gives examples and python code for finding these sequences.
The core difference between what you're asking is that De Bruijn sequences are cyclic (subsequences can go "off the end and pick back up at the beginning"). But if you find such a sequence of length $n$ which is minimal, and you are looking at subsequences of length $4$, you could get a non-cyclic sequence of length $n+3$.
