Optimal consistency for brute force decides keyboard code lock

Question

Possible duplicate:
Need help building an efficient, comprehensive search algorithm

Imagine that you must open a locked door by entering the correct 4-digit code on the keypad. After each key press, the lock evaluates the sequence of the last 4 digits entered, i.e. By entering 123456 you rated 3 codes: 1234 , 2345 and 3456 .

• What is the shortest key sequence for evaluating all 10^4 different combinations?
• Is there a way to move the whole space simple enough for a person?

I thought about this from time to time, since my friend had to impose such a castle so as not to spend the night on the street in the winter.

---

My weak attempts to wrap my head around me

With a code of length L=4 digits and an "alphabet" of digits of size D=10 length of the optimal sequence cannot be less than D^L + L - 1 . When simulating a smaller size than [L,D] = [4,10] , I got optimal results by a semi-auditory search of space. However, I do not know if a solution exists for an arbitrary pair [L,D] and cannot remember the solution if I ever had to use it.

Lessons learned so far

When you plan to spend the night in a friends house in another city, you will not necessarily arrive at 1 am if this person goes to the party and does not hear her cell phone.

Answer 1

The link provided by Eugene should respond to both of your quests. This answer is a bit offtopic, but you are asking for solutions for people.

In the real world, you probably should rely more on Social Engineering or heuristics , and then on mathematics. I talk about real life:

I went to the apartment and I found out that my mobile phone is dead. You can now contact the person making the visit. I was about to return when I saw that the door had a 0 - 9 keyboard and AB . I made a few assumptions:

• The code is 5 digits long. The length is pretty standard depending on the region in which you are located. I based this assumption on the buildings that I had access to (legally: D).
• The code starts with numbers, then A or B (based on my own building).
• The keyboard was not new. Conclusion The numbers used in the code were slightly damaged. I knew with certainty which numbers were not in the code, and three of the four numbers in the code (given my previous assumptions)
• By the number of damaged keys, I assumed that the code does not contain duplicate keys (7 were damaged, it was clear that A used, B not used)

In the end, I had 3 numbers that were in the code for sure, 2 candidates for the last number, and I was sure that A was at the end. The key was slightly damaged compared to others.

I just needed to list the permutations, starting with a candidate who seemed more damaged, giving me 4! + 4! = 48 4! + 4! = 48 4! + 4! = 48 attempts. Believe me, on the 5th attempt, the door was open. If I can give my 2 cents, the old put a key and open the door is still the most reliable method of restricting access to the building.

Answer 2

I think you want 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 appears as a sequence of consecutive characters exactly once."