Algorithm challenge

[Troberg]

A few days ago, I had to do a "rescue intervention" (legal and needed). This required me to bypass a door code. Luckily, the keypad was worn and you could clearly see that only two numbers where used, so it was a quick thing to brute force the 14 possible combinations.

However, I noticed that the lock did not require four numbers, then pause, then the next four numbers. As long as you pressed the four numbers in correct order, regardless of what you had pressed before, it worked.

Now, the programmer in me hasn't been able to drop this. How do one generate a sequence that contains all possible combinations in as few keypresses as possible.

For the example above, a short sequence which works (assuming the numbers are 0 and 1), is:

10001110010110100

This sequence contains all the possible combinations in as few keypresses as possible.

However, that was done manually, with some trial and error to avoid repetitions or numbers which were not used in an optimal number of combinations. There are some traps which would cause it to be suboptimal, for instance, if I had started with 0001, I would have had to duplicate three zeros elsewhere to be able to get 1000, and they are not needed in any other combination.

Also, say that three numbers are used? Four? If the code is 5 or 6 digits long?

Can you come up some kind of generic algorithm that can generate a sequence that is the shortest possible sequence, given the following inputs:

* Used numbers (in the example above, 0 and 1)
* Length of code (in the example above, 4)

I can fairly easily do one which gives a sequence that works and is fairly short, but I can't guarantee it will be the shortest possible sequence.

Hint: the shortest sequence should be this long:

Possible_combinations + Length_of_code -1

There are several possible solutions in each case, but as long as one of them is found, it's good enough.

Do you dare to accept the challenge?

 

[Beja]

Do you dare to accept the challenge?

YES

If the code is combination of zeros and ones, then the solution will be to build a binary counter with the length of the code.
if the code length is 14 bits then you will need to use a 2-byte (16-bit) counter.. in other words:

code is: between 2 and 8, use 8-bit counter
code is between 9 and 16, use 2-byte counter
.
and so on.

I don't know how the lock is constructed, but if it has some kind of interface to MCU or serial port then the solution is pure software,
otherwise you will need to use binary counter chips like the 74LS93 (4-bit binary counter) and then cascade it with more chips if the code width is more than the output of the chip. You will also need to build a small PCB to accommodate the counters and the system clock.

 

[Troberg]

Basically, the lock is a keypad with 10 numbers. You press four numbers in the right order to open. However, say, for example, that the correct code is "3456", then it will unlock if you press "123456" as well, since "3456" is in that sequence.

So, I want a way to get the shortest possible sequence, given that we know (from the wear on the keypad) which numbers are used in the code, which contains all possible combinations.

Your solution will, if I understand it correctly, simply enumerate all possible solutions, which would require a lot of extra keypresses.

Another example (which I'm not completely going to solve, as it will be too big to do manually):

We know it's a 4 digit code, and we know that the numbers 2, 4 and 6 are used. So, the possible codes are all four digit codes which contain at least one each of 2, 4 & 6. Then, we need to construct a sequence, as short as possible, which, somewhere in it, has every one these possible codes.

It might, for example, start with 22462644..., which would contain the sequences 2246, 2462, 4626, 6264 and 2644. Of course, the full sequence would be much longer, but as short as possible while still containing all possible codes.

The actual number punching is left as a manual exercise (or, as a theoretical example for the challenge). We don't need to interface with the lock.

Clearer?

 

[Beja]

Sorry but I am not following.. how are you communicating with the keypad lock? how can you change the design?
As far as I am concerned, there are only two solutions:
1- Hardware solution, in which you need to redesign the electronics and limit the output of the register to 4 bytes only. .so if user pressed
5 buttons the 1st. value will be shifted out and lost, and the new 4 will be invalid and door wouldn't open. In other words, the output will
always hold the last 4 digits pressed. Yet another hardware solution is to let the user press as many buttons he he wishes, then compare the whole
output with the stored 4 bytes.

2- If there's a way to change the firmware of the keypad by way of serial port or something like that, then you capture the punched keys and when
user stopped (timer) then compare whatever he put with a stored value (the four bytes or digits).

 

[Troberg]

I'm communicating with the keypad by pushing buttons on the lock's keypad.

Since this is some work, I want to push as few buttons as possible, which is why I want to generate the shortest possible sequence which contains all possible codes, given that I know what numbers are used in the code.

The very practical situation I found myself in, which inspired this question, was that I was on one side of the codelocked door, and there was an emergency on the other side. I could see that only two buttons where worn, so I knew which two numbers where used in the four digit code. So, I simple went through all combinations of those two numbers in order, and unlocked the door.

However, a much shorter sequence would have worked as well, as long as, somewhere in it, all possible codes existed, which would have saved me time.

In case of this challenge, though, it's a purely theoretical exercise. No interfacing with the lock, just generate the shortest possible sequence that is guaranteed to open the door.

 

[Beja]

Oh, you depend on worn out keys?
(Apology in advance.. just wanted to add some good spirit to the atmosphere)

ok, take this suggestion:
If you are in China,
1- Forget the #4 key, since Chinese never use it because it is the death number
2- Use the numbers between 6 to 9, Chinese don't use lower numbers by choice.
3- Keep the number 6 and 8 in all combinations since these are the luck numbers in Chinese tradition and they never drop them by choice.

If you are in Europe don't put the numbers 1 and 3 next to each other with 1 on the left.

If you are in Germany then first go and study statistics for 2 years

If you are in Africa, build a shade next to the lock and wait for someone to open it.

If you are from the middle east build an army and conquer the North Pole because it is the reason for all these problems.

If you are from United States get a gun and blow up the lock.

 

[Troberg]

I'm sure they'll work, but it's outside the question.

I just want the shortest possible sequence of numbers that contain all possible codes, given that I know which numbers are used.

 

[Beja]

I just want the shortest possible sequence of numbers that contain all possible codes, given that I know which numbers are used.

Aha.. I think just now I understand your question.

One solution could be to take all the numbers from the smallest number to the largest, then run the normal iterations, neglecting
the unused number in each iteration. You can develop an algorithm to mask off the unused numbers.

 

[JordiCP]

Oh no!!!! I like these challenges too much!!!

My two cents:

K: the number of used keys (will call them A,B,C....)
L: the sequence length

NC: The number of possible combinations (not compressed) NC = K^L (power)

So, the "brute force" sequence (all combinations one after the other) would have L*(K^L) digits
A lower-bound is (k^L)+L-1 (if no sequences are repeated in the "compressed" string)


For the trivial case, L=2 we have

K=2, L=2 ---> NC= 2^2=4 --> minimum sequence length = 5 (AABBA)
K=3, L=2 ---> NC= 3^2=9 --> minimum sequence length = 10 (AABBA-CCBCA)
K=4, L=2 ---> NC= 4^2=16--> minimum sequence length = 17 (AABBACCBCA-DDCDBDA)
K=5, L=2 ---> NC= 5^2=25--> minimum sequence length = 26 (AABBACCBCADDBDCDA-EEDECEBEA)

So, it "seems" that for L=2, the minimum sequence length is (K^2)+1 --> which is the general lower bound
Also, for L=2, it is easy to generate the string recursively from (K,L) to (k+1,L)

If we could find the way to generate the string recursivelly from (K,L) to (K,L+1) then the algorithm would be done!


----------------EDIT----------------
Uhm! I see a difference which makes what I wrote above not to describe exactly what you were asking for

You say that if there are 2 keys, both of them are used at least once. That's why 0000 and 1111 are not valid (14 combinations instead of 16, which would be if you could can choose to use or not the allowed keys) .

So, for a general case with K keys and length=L this would mean that each key can appear repeatedly in the sequence at most L+1-K times

 

[Beja]

Not tested though.. see this:

1- Used keys: 4 5 7 9
2- number of used keys = 4
3= M(4) is the array to hold the normal sequence from 1 to 4

Map:
----------------------------------
1 | 2 | 3 | 4 |
4 | 5 | 7 | 9|

So the minimum number to iterate through is 4 (1 to 4) then before the end of each pass you map the array index number to the
corresponding number according to the map above. e.g. M(3) = 7

 

[Troberg]

I've done the math, and for four number codes, the number of possible codes is actually quite small:

1 known number: 1 (the ultimate simple case...)
2 known numbers: 14
3 known numbers: 18
4 known numbers: 24

This corresponds to sequence lengths 4, 17, 21 and 27.

So, for the 4 digit codes, one could simply generate the sequence by hand, using letters instead of numbers, and then simply make some string replacements to get the sequence.

If we increase to 5 digits, we get:

1 known: 1 (sequence length 5)
2 known: 30 (seq len 34)
3 known: 54 (seq len 58)
4 known: 96 (seq len 100)
5 known: 120 (seq len 124)

For 6 digits:

1 known: 1 (6)
2 known: 62 (67)
3 known: 162 (167)
4 known: 384 (389)
5 known: 600 (605)
6 known: 720 (725)

So, the method of manually pregenerating a sequence quickly becomes cumbersome, and some better method is needed. This is also the point where we need to remember that this, although based on a real example, is a theoretical exercise. Somewhere above 3 digits in a 6 digit code, it just becomes too much work to actually punch the buttons...

One can also note the importance of keeping the keypad clean and to get a keypad which will not show wear, especially if you have a 4 digit code. A 24 digit sequence guaranteed unlock is not very safe...

 

[udg]

Hi Troberg,

since you had experience with a real device, do you know if there's a "special combination" that plays the passepartout role in case one forgets his current password code?
The question arises because time ago someone told me a wall-mounted safe was open in no time using no electronic device. At that time I was thinking of substituting my main door lock with a keyless one..

Thank you

 

[Troberg]

I have no idea. I just needed to get past a code, checked what buttons were used and brute forced it. It's quite possible there is a "master code", but, in that case, it will be harder to find, as we don't know which digits it contains.

If you want a keyless door lock, I'd problably go with an RFID fob with a code. Or, if you live in northern Sweden, simply put a broom leaned against the door to show that you are not at home, and people will not enter.

 

[udg]

Or, if you live in northern Sweden, simply put a broom leaned against the door to show that you are not at home, and people will not enter.

Respectful people..if they only could teach that to all the others! Telling it with the words from L.Armstrong "what a wonderful world .. would it be".

 

[Troberg]

Respectful people..if they only could teach that to all the others! Telling it with the words from L.Armstrong "what a wonderful world .. would it be".

Personally, I think it's just too cold for them to bother to go outside in the first place...

 

[JordiCP]

You may want to take a look at this

https://en.wikipedia.org/wiki/De_Bruijn_sequence

 

[Troberg]

I've done some more on this, and found out that the estimated optimal length won't hold true when all numbers of the code are known. It will be somewhat longer, as you have no choice of which number to add next to the sequence, and will end up in 4 code loops (assuming a 4 digit code).

I've put together a small app, but it requires some more polish.