The Gateway to Computer Science Excellence
+1 vote
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?
in Algorithm Challenges by Veteran (425k points) | 232 views
9^3+1 ???

since it accepts a serial input.

First all combination of 3 digit number +1 for next entered number  for min  i.e. 10^3+1

how it works? we have to give all combinations of 4 digits rt?
yes I think 9^4 should be the answer. because consecutive number could be anything. Not any other clue getting for thinking
Answer is close. But important thing is to say how to generate such a sequence.
Let correct key is 0000.

Total number of inputs are 10^4 i.e. sample space.Out of these many inputs we have to eliminate those strings (set of inputs) in which 0000 is substring .
$10^4$ strings in sample space. Each takes 4 characters, and so a brute force approach will take $4 \times 10^4 = 40,000$ input characters. But we can optimize like, after 0000, by input 1, we checked 0001 also in just 5 total characters. So, how to proceed?
Dont know i am correct or not but here is my approach :


Remember last 3 digit only. And keep updating last digit with a number greater than previous number. Keep counting upto 9999 which is largest four digit number and finally add length of password into it.  9999 + 4 (length is 4)
why 9 - it should be 10 rt? $10^4+ 3$ is correct. But now how to generate such a string of length 10003? That's the actual question :P
yes @digvijay's approach might be correct

because there are 0000,0001.........9999 are all combination of lock . right?

no other combination is possible

So, 10000 combination.
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??

1 Answer

+1 vote
Best answer

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).An 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 1st 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' 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".


by Active (3.5k points)
selected by
Good :) Would be good if someone code this and generates the sequence.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,596 answers
102,073 users