Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from stats.stackexchange.com Aug 14 '12 at 12:56

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

2  
De Bruijn sequence? –  Jyrki Lahtonen Aug 14 '12 at 13:01

1 Answer 1

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?

share|improve this answer
    
The pad is just for illustrating, I skip letters A & B to make the problem simpler. +1 for the nice link –  pinouchon Nov 7 '11 at 14:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.