4
$\begingroup$

I have a digicode to enter my home. Let's say the combination is 4432.

This morning, I got it wrong, so I retyped it, and the door opened. But the final code I entered was 4424432. That made me realize that the door opens for any sequence of number containing 4432, in fact any sequence that matches [0-9]*4432[0-9]*. And I asked myself the question: what is the optimal way of cracking it, if you don't know the code ?

digicode

To simplify, let's assume a couple of things:

  • The combination is a sequence of 4 digits.
  • All combinations are equiprobable.

If you could submit one code at a time. For example, if you have to press 4 buttons then press "submit", the approach would be a simple bruteforce. You try out all the 10000 solutions one by one: 0000, 0001, 0002 etc...

But given the fact that 2 combinations somewhat overlap, you can optimise your search, and I'm interested about what is the best optimisation you can do.

  • 2
    [De Bruijn sequence?](http://en.wikipedia.org/wiki/De_Bruijn_sequence)2012-08-14

1 Answers 1

5

This Q&A discusses this precise problem and a solution involving interesting ideas from graph theory.

If you need a precise sequence of things to type, here you go - from a link posted to the above Q&A.

It's odd, though, that you mention 0-9, while the pad shows the letters A & B. Is something amiss?

  • 0
    The pad is just for illustrating, I skip letters A & B to make the problem simpler. +1 for the nice link2011-11-07