Adding one digit (0-9) to the sequence/string creates new 4 digits number

Question

I'm trying to find an algorithm which "breaks the safe" by typing the keys 0-9. The code is 4 digits long. The safe will be open where it identifies the code as substring of the typing. meaning, if the code is "3456" so the next typing will open the safe: "123456". (It just means that the safe is not restarting every 4 keys input).

Is there an algorithm which every time it add one digit to the sequence, it creates new 4 digits number (new combinations of the last 4 digits of the sequence\string)?

thanks, km.

Editing (I post it years ago): The question is how to make sure that every time I set an input (one digit) to the safe, I generate a new 4 digit code that was not generated before. For example, if the safe gets binary code with 3 digits long then this should be my input sequence:

0001011100 

Because for every input I get a new code (3 digit long) that was not generated before:

000 -> 000
1 -> 001
0 -> 010
1 -> 101
1 -> 011
1 -> 111
0 -> 110
0 -> 100

Answer 1

I found a reduction to your problem:

Lets define directed graph G = (V,E) in the following way:

V = {all possible combinations of the code}.

E = {< u,v > | v can be obtained from u by adding 1 digit (at the end), and delete the first digit}.

|V| = 10^4.

Din and Dout of every vertex equal to 10 => |E| = 10^5.

You need to prove that there is Hamilton cycle in G - if you do, you can prove the existence of a solution.

EDIT1:

The algorithm:

1. Construct directed graph G as mentioned above.

2. Calculate Hamilton cycle - {v1,v2,..,vn-1,v1}.

3. Press every number in v1.

4. X <- v1.

5. while the safe isn't open:

   5.1 X <- next vertex in the Hamilton path after X.

   5.2 press the last digit in X.

We can see that because we use Hamilton cycle, we never repeat the same substring. (The last 4 presses).

EDIT2:

Of course Hamilton path is sufficient.