All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Answer Machine Hacking (Posted on 2004-05-24) Difficulty: 4 of 5
Consider an answering machine with remote inquiry facility, where you can call the answering machine and enter a 4 digit passcode into your telephone keypad, so you can listen to the messages from anywhere you like. Many of these machines will let you in if you enter the correct consecutive sequence of digits, regardless of what preceded that sequence.

Example: Passcode 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.
if you feed the machine 94129838701234, you're in.

To brute-force hack the machine, you could try all numbers 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?

No Solution Yet Submitted by SilverKnight    
Rating: 4.4286 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips re(2): de Bruijn sequence Comment 11 of 11 |
(In reply to re: de Bruijn sequence by Kenny)

Kenny, while your idea is right on the mark, your solution of 10000 digits is missing a few combinations.  The theoretical minimum of 10003 is correct.

What you are forgetting is that a de Bruijn sequence is circular. In the string you provided, you would never get into the answering machine if the passcode was 9000, 9900, or 9990 - these only result when the string repeats from the beginning.  You would need to tack the first 3 elements, 000, onto the end of this string to make it complete, giving a total of 10003 digits.


  Posted by tomarken on 2006-03-22 15:48:01
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information