Open the lock

Question

You are given a number lock of 4 digits and it accepts a serial input. What should be the minimum length of an input string so that the lock is guaranteed to open assuming it opens if any of the consecutive 4 digits matches the code. Also how to get one such sequence?

Comments

No. of combinations is not the question- No. of characters is the question. 40,000 characters is needed for 10,000 combinations. How to optimize this to ensure just 10003 characters?

---

I might be not be correct, but here is what i think.

First we create an array of 10 integers initialized to 0. Then we take any random 4 digits. Then we increment the array[digit] by 1 for each digit entered. This will give an idea of what the next digit should be as we want the string to have the digits in equal frequency. That way the next digit that will be entered wont create a 4 digit combination that was already entered and we have enough options to select the next digit. We also need a 10^4 bit map to indicate which combinations were already entered. Then by remembering the last 3 digits entered we will know what all 1000th place, 100th place and 10th place digits we have. so while deciding what the next digit should be we can then check the available options using the bit map. Further we can check what all options are possible for the next combination if that digit is entered. The one that yields the maximum options should be chosen.

---

can it be FSM??

Answer 1

Actually this problem is popular application of De Bruijn graphs.

Some idea about De Bruijn graph:

Let each node of De Bruijn graph consists of triplet $(XYZ)$. A directed arc can exists between one triplet say $(XYZ)$ to other triplet $(YZW)$ e.g there is an arc from node $(345)$ to $(459)$ since last $2$ – digits of first node is common to first $2$ – digits of second node.

Similary there is no arc from say $(245)$ to $(478)$. This way we create directed edges between nodes of De Bruijn graphs.

Properties of De Bruijn graphs:  

1. Each De Bruijn graphs has equal no of incoming & outgoing edges which in turn equals to no of symbols used for constructing triplets(in our case we have total $10$ digits using which we can construct triplets, hence no. of incoming edges (i.e. in – degree) = no. of outgoing edges (i.e. out – degree) $= 10$.

2. Each De Bruijn graphs is Eulerian & Hamiltonian i.e Euler cycle & Hamiltonian cycle exists. So consider Euler cycle i.e. traversing each edge only once gives us minimum sequence. So we use this property to verify that sequence we got from this graph will always minimum so our solution will be always optimised.

Now lets solve our problem:

Since we have to find key which consists of is $4$ – digit, so we first create all triplet possible of the form $<XYZ>$. So total no. of such triplets $= 10*10*10 = 1000$.

Now we will start creating directed edge between nodes following the above condition we described in $1^{st}$ properties.

So for every two triplets of the form $<XYZ>$ & $<YZW>$, we create one edge which corresponds to sequence $XYZW$. So total no. of such sequence possible $= 10*10*10*10 = 10000$.

So upto this point we have successfully constructed De Bruijn graphs.

Now our solution is simple: Take any node say $<XYZ>$ and traverse to other node say $<YZW>$ this corresponds to sequence $XYZW$ i.e., for each encounter of edge in Euler path, we add one symbol to previous node. Here we added $W$ to $XYZ$. This way we traverse through Euler Path. Now since we have total $10000$ edges and for each edges, we are adding one character, so starting from any node say $<XYZ>$, we will have finally $3+10000 =10003$ characters in sequence.

And from the property of De Bruijn graphs, this sequence will be optimal.

In short, basically this algorithm work as follows:

Let correct key is $``\ 1234"$. We start with any triplet i.e., any node in graph say $012$. After that we read one more digit sequentially say we read $`2\textrm'$ i.e., traversing through edge which will take us to $``\ 122"$. So this traversal corresponds to $``\ 0122"$. Now we compare it with correct key, since no match, so we traverse further. Now say next char we read is $``\ 3"$, so it takes us to node $``\ 223"$ i.e., we reached at node $223$ from $122$. This gives us current sequence $``1223"$ & overall sequence $``\ 01223"$. We keep on traversing the graph till we get last $4$ – character of sequence as $``\ 1234"$. So in worst case we will get a sequence of length $``\ 10003"$.

Comments

Good :) Would be good if someone code this and generates the sequence.