Author |
Topic: Hacking an answering machine II (Read 3673 times) |
|
dudiobugtron
Uberpuzzler
Posts: 735
|
 |
Hacking an answering machine II
« on: May 26th, 2014, 4:06pm » |
 Quote  Modify
|
This is a follow-up riddle to the old Answering Machine Hacking riddle.
Original Riddle:
Quote: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? |
|
Thread: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1028915367
New riddle:
----------------------
Hacking an answering machine II
Consider an answering machine with remote inquiry facility, as in the previous riddle. However, you know this answering machine is less sophisticated, and so pass codes can't have repeated digits. Each digit in the passcode must be unique.
eg: 1234 is allowed,
but 1232 is not. (it has more than one '2'.)
Being a smart hacker, you realise this means you can refine your search even further. Instead of 10000 different possible codes, there are only 5040. What is the shortest series of digits you have to send to the answering machine in order to break the code now?
----------------------
Bonus questions to consider:
The general case has strings of length n, with k different digits available. (k is at least n, of course).
1) Can you come up with a formula for the minimum svore in the general case? What values of k and n does it work for?
2) What happens if n = k? What is the minimum score in that case?
'Hint' for the bonus questions: I do not know the answer to all of the bonus questions! Not sure if that counts as a hint or not, but I thought it might affect the way some people think about it.
|
| « Last Edit: May 26th, 2014, 4:53pm by dudiobugtron » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Hacking an answering machine II
« Reply #1 on: May 30th, 2014, 3:32am » |
Quote Modify
|
Say we have a graph with every vertex labeled with 3 distinct digits and edges that have four distinct digits where the first three equal the starting vertex, and the last three equal the end vertex.
Because of symmetry, there is the same number of incoming and outgoing edges for each vertex (either prepend or append a digit not on the vertex to get either an incoming or outgoing edge). So the degree of each vertex is even, therefore, given the graph is connected, there is an Euler tour. This means we can walk through all the edges, one after the other; and therefore we can do it using no more than 5040+3 digits.
|
| « Last Edit: May 30th, 2014, 3:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hacking an answering machine II
« Reply #2 on: May 30th, 2014, 3:52am » |
Quote Modify
|
I wonder if there is a way to generate such a sequence with O(1) memory.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Hacking an answering machine II
« Reply #3 on: May 30th, 2014, 6:11am » |
Quote Modify
|
on May 30th, 2014, 3:52am, Grimbal wrote:| I wonder if there is a way to generate such a sequence with O(1) memory. |
|
No - you won't have enough memory to store n digits (required to track current state)
If you limit the number of digits, then you can brute-force it by having the full sequences pre-loaded in (large) finite memory...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hacking an answering machine II
« Reply #4 on: May 30th, 2014, 9:08am » |
Quote Modify
|
OK, what I meant, is O(log(#codes)) memory.
Or if the base is fixed (base 10), O(#digits).
It is easy to do with O(#codes). You keep a flag for each combination you tried, as well as the path. Maybe you have to review and change the path to visit a region you missed.
I was curious whether there is a simple generator that will generate such a sequence directly.
"I was", because I found http://en.wikipedia.org/wiki/De_Bruijn_sequence
PS: it seems to use something like O(#digits * base). Close enough.
PS: actually it is wrong, I didn't see there is a condition for all digits to be different.
|
| « Last Edit: Jun 4th, 2014, 1:53am by Grimbal » |
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Hacking an answering machine II
« Reply #5 on: May 30th, 2014, 2:36pm » |
Quote Modify
|
on May 30th, 2014, 3:32am, towr wrote:Say we have a graph with every vertex labeled with 3 distinct digits and edges that have four distinct digits where the first three equal the starting vertex, and the last three equal the end vertex.
Because of symmetry, there is the same number of incoming and outgoing edges for each vertex (either prepend or append a digit not on the vertex to get either an incoming or outgoing edge). So the degree of each vertex is even, therefore, given the graph is connected, there is an Euler tour. This means we can walk through all the edges, one after the other; and therefore we can do it using no more than 5040+3 digits. |
|
Just one small quibble with this otherwise excellent proof - the graph needs to be 'strongly connected' to guarantee and euler circuit. While the graph is obviously connected, it isn't necesarily the case that it's obvious that all of the vertices are in the same strongly connected component.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hacking an answering machine II
« Reply #6 on: May 31st, 2014, 12:55pm » |
Quote Modify
|
True.
Well, we can show there is a path from any vertex to any other. You can just take 3 digits that are used in neither vertex and use those to create a path connecting them; to go from ABC to XYZ, you can use the path ABC -> BCk -> Ckl -> klm -> lmX -> mXY -> XYZ
(There may be a shorter path, of course.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Hacking an answering machine II
« Reply #7 on: May 31st, 2014, 1:54pm » |
Quote Modify
|
on May 31st, 2014, 12:55pm, towr wrote:True.
Well, we can show there is a path from any vertex to any other. You can just take 3 digits that are used in neither vertex and use those to create a path connecting them; to go from ABC to XYZ, you can use the path ABC -> BCk -> Ckl -> klm -> lmX -> mXY -> XYZ
(There may be a shorter path, of course.) |
|
I'm convinced. Puzzle solved! 
---------------------------
Re: the bonus questions; this proof also works for that, as long as k at least as large as 3(n-1). So that part is solved as well.
What happens though if you don't have n-1 digits that aren't in either vertex to choose from? eg: what if k = 5, and n = 4?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hacking an answering machine II
« Reply #8 on: Jun 1st, 2014, 1:08pm » |
Quote Modify
|
I think it's enough if there's one extra digit. Because you can substitute it in anywhere
Let's start with code (edge) ABCD, an extra digit E
option 1: ABCD -> BCDE -> CDEB -> DEBC -> EBCD
option 2: ABCD -> BCDA -> CDAE -> DAEC -> AECD
option 3: ABCD -> BCDA -> CDAB -> DABE -> ABED
option 4: ABCD -> BCDA -> CDAB -> DABC -> ABCE
So we can substitute one digit for another, and repeat this to transform any code to another, as long as we have one more digit than there is in a code.
This may not be the simplest path to take from one code to another, but it suffices there is one.
So that leaves the case where n=k.
At the very least we can handle groups of cyclic permutations in one go. And there's probably a cheaper way to transition to the next cyclic group than to restart from scratch.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Hacking an answering machine II
« Reply #9 on: Jun 3rd, 2014, 12:32am » |
Quote Modify
|
on Jun 1st, 2014, 1:08pm, towr wrote:So that leaves the case where n=k.
At the very least we can handle groups of cyclic permutations in one go. And there's probably a cheaper way to transition to the next cyclic group than to restart from scratch. |
|
I agree it seems intuitively correct. And many groups will have easy transitions too. But some will probably require 'starting over'. I think, however, that it isn't obvious that you can't get a better result overall by moving some permutations out of their groups to a different place, to make those annoying transitions easier.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hacking an answering machine II
« Reply #10 on: Jun 3rd, 2014, 11:23pm » |
Quote Modify
|
I don't know if it's optimal, but you can get a solution for n+1 from a solution for n
n=k=1: a
{transform x => xby for every x}
n=k=2: aba
{transform xy => xycxy for every xy}
n=k=3: abcabacba
{transform xyz => xyzdxyz for every xyz}
n=k=4: abcdabcadbcabdcabacdbacbdacbadcba
etc.
If nothing else, it gives an upper limit. But I suspect it may be the best you can do.
|
| « Last Edit: Jun 3rd, 2014, 11:25pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Hacking an answering machine II
« Reply #11 on: Jun 4th, 2014, 1:16pm » |
Quote Modify
|
Your algorithm does appear to have generated the optimal results for n = k = 1, ..., 4. And it's really nifty!
Do you think there is a way to predict the size of the 'overlaps' for n+1, if you already have a solution for n?
|
| « Last Edit: Jun 4th, 2014, 1:17pm by dudiobugtron » |
IP Logged |
|
|
|
wakiza33
Junior Member
industrial Engineer // Berkeley Alumnus
Posts: 54
|
|
Re: Hacking an answering machine II
« Reply #12 on: Sep 23rd, 2014, 11:14am » |
Quote Modify
|
on May 31st, 2014, 1:54pm, dudiobugtron wrote:
I'm convinced. Puzzle solved!
---------------------------
Re: the bonus questions; this proof also works for that, as long as k at least as large as 3(n-1). So that part is solved as well.
What happens though if you don't have n-1 digits that aren't in either vertex to choose from? eg: what if k = 5, and n = 4? |
|
Well done.
|
|
IP Logged |
Binder Jetting Engineer
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print