Optimal sequence to brute force solve a keypad code lock [duplicate]

Question

Possible Duplicate:
Need help in building efficient exhaustive search algorithm

Imagine that you must open a locked door by inputting the correct 4-digit code on a keypad. After every keypress the lock evaluates the sequence of the last 4 digits inputted, i.e. by entering 123456 you have evaluated 3 codes: 1234, 2345 and 3456.

• What is the shortest sequence of keypresses to evaluate all 10^4 different combinations?
• Is there a method for traversing the entire space easy enough for a human to follow?

I have pondered this from time to time since a friend of mine had to brute force such a lock, to not having to spend the night outdoors in wintertime.

---

My feeble attempts at wrapping my head around it

With a code of length L=4 digits and an "alphabet" of digits of size D=10 the length of the optimal sequence cannot be shorter than D^L + L - 1. In simulations of smaller size than [L,D] = [4,10] I have obtained optimal results by semi-randomly searching the space. However I do not know if a solution exists for an arbitrary [L,D] pair and would not be able to remember the solution if I ever had to use it.

Lessons learned so far

When planning to spend the night at a friends house in another town, be sure to not arrive at 1 am if that person is going out to party and won't hear her cell phone.

Answer 1

I think you want a http://en.wikipedia.org/wiki/De_Bruijn_sequence - "a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once."

Answer 2

The link Evgeny provided should answer both of your quests. This answer is a bit offtopic, but you ask for a solution for humans.

In the real world you should probably rely more on Social engineering or heuristics, and after that on mathematics. I give a case on real life:

I went to visit an apartment and I found out that my cellphone was dead. Now way of contacting the person doing the visit. I was about to go back when I saw that the door used a keypad 0 - 9 and A B. I made several assumptions:

1. The code is 5 digits long. The length is pretty standard depending on the region you are in. I based this assumption on buildings I had access before (legally :D).
2. The code starts with numbers, then either A or B (based on my own building).
3. The keypad was not brand new. Conclusion, the numbers used in the code were a bit damaged. I knew with certainty which numbers were not in the code, and three of the four number in the code (given my previous assumptions)
4. By the amount of keys damaged I assumed the code didn't contain repeated keys (7 were damaged, it was clear A was used, B not used )

At the end I had 3 numbers which were in the code for sure, 2 candidates for the last number and I was sure A was at the end. On key was just slightly damaged compared to the others.

I just had to enumerate permutations starting with the candidate which seemed the more damaged, which give me 4! + 4! = 48 tries. Believe me, at the 5th try the door was opened. If I can give my 2 cents, the old put a key and open the door is still the most reliable method to restrict access to a building.