logical deduction - Unlock an answering machine using minimum number of digits

You know of answering machines with a remote inquiry facility, where you can call the answering machine and enter a four digit passcode into your telephone keypad, so you can listen to your messages from anywhere you like.

Many of these machines are quite dumb in the way you can feed the codes. They let you in if they encounter the right combinations of digits, regardless of what you sent before.

For example — assuming that the code is 1234...

• if you feed the machine 1234, you're in!


• if you feed the machine 01234, you're in!



• if you feed the machine 0121234 you're in!

It just waits for the right four digits to come in, regardless of what happened before.

In order to hack the machine, could try all combinations from 0000 to 9999, sending 40000 sounds across the wire. But since you are a smart hacker, you see that there's room for optimization.

What is the shortest series of digits you have to send to the answering machine in order to break the code in any case?

In the comments, Hugh has pointed out a similar question with a different wording. All the answers in those questions rely on graph theory and de Bruijn Sequences. I would like an answer to this question which does not require any knowledge of graph theory or de Bruijn sequences.

Answer

This question asks to find a solution without the use of graph theory or de Bruijn Sequences. Since I was unaware of these theories when I was working on the answer I think this qualifies. Although the algorithm I used is probably the same without me realizing it. Anyway, here’s my thought process:

Obviously for a 4 digit code with 10 numbers there will be 10^4 = 10,000 combinations. After you’ve entered the first combination – requiring 4 digits, each additional digit can theoretically introduce a new combination. Since you need to try 9,999 more combinations then the smallest sequence will be 9,999+4 = 10,003.

To have a consistent algorithm, whenever I have a choice I will choose the lowest possible option that hasn’t already been tried or that doesn’t break the sequence. This means I’ll start with 0000. Now, since with each step I am adding one more digit to the end of the sequence, that means that each step I am just looking at the last three digits of the sequence. My algorithm will then be to break down the 10,000 combinations into 1000 three digit blocks with 10 choices in each block. Whenever I encounter a three digit block, for my next digit I just choose the smallest option in the block that hasn’t been used yet.

000 0 .. 900 0 .. 990 0 .. 999 0
000 1    900 1    990 1    999 1
000 2    900 2    990 2    999 2
.        .        .        .
.        .        .        .
000 9    900 9    990 9    999 9

So, since I started with 0000 then the first block I encounter is 000.

0000

I already used the 0, so that can be eliminated from the block. The next number will then be 0001. After I write that down I eliminate 0001 from the block. Now I look at the block 001

00001

The smallest number in that block is 0010, after I write that down I can eliminate it from the block. And so on.

This algorithm works pretty well. There are only 3 places where it will give you trouble. The first two problem spots are pretty early in the sequence, the third one is a bit further down the line, but if you’re looking for it it’s not hard to find.

The first problem is when I’ve eliminated the entire 000 block. I have to make sure now that I do not encounter a 000 block again until the end. This happens at this point:

000010002000300040005000600070008000900

Normally I would put 0 after this, because the lowest option in the 900 block is 9000, but in this case that will leave me with no way to progress, so I save 9000 until the end and move on to 9001.

The second problem is when I’ve used up the entire 900 block, except for the 9000 choice which I am saving until the end. This happens at this time:

00001000200030004000500060007000800090011001200130014001500160017001800190021002200230024002500260027002800290031003200330034003500360037003800390041004200430044004500460047004800490051005200530054005500560057005800590061006200630064006500660067006800690071007200730074007500760077007800790081008200830084008500860087008800890091009200930094009500960097009800990

Again, normally when I encounter a 990 block I would choose 9900 as that’s the lowest available, but in this case it will force me into a 900 block which only has one option left that terminates the sequence. So I leave 9900 until the end and move on to 9901.

I think you’ve seen the pattern now. Once I’ve used up the entire 990 block, except for 9900, now I have to be vigilant not to enter that block again until the end. This happens at this location:

...0997099809991111...

Instead of 9990 I will have to put 9991 here and save 9990 until the end. After navigating these 3 problem places there are no more issues in the sequence. At the end I just close with the numbers that I’ve saved: 9990, 9900, and 9000.

...9999000

This is the exact same sequence that the other answer provided.

And that’s how you do it without knowing anything about anything. I don’t know if this too complicated or too simple or too labor intensive, but it gets the job done.