wu :: forums
« wu :: forums - Hacking an answering machine II »

Welcome, Guest. Please Login or Register.
Oct 10th, 2024, 4:39am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: towr, Grimbal, SMQ, william wu, Icarus, ThudnBlunder, Eigenray)
   Hacking an answering machine II
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Hacking an answering machine II  (Read 3663 times)
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Hacking an answering machine II  
« on: May 26th, 2014, 4:06pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Hacking an answering machine II  
« Reply #1 on: May 30th, 2014, 3:32am »
Quote Quote Modify 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: male
Posts: 7527
Re: Hacking an answering machine II  
« Reply #2 on: May 30th, 2014, 3:52am »
Quote Quote Modify Modify

I wonder if there is a way to generate such a sequence with O(1) memory.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2873
Re: Hacking an answering machine II  
« Reply #3 on: May 30th, 2014, 6:11am »
Quote Quote Modify 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: male
Posts: 7527
Re: Hacking an answering machine II  
« Reply #4 on: May 30th, 2014, 9:08am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: Hacking an answering machine II  
« Reply #6 on: May 31st, 2014, 12:55pm »
Quote Quote Modify 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 Quote Modify 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! Smiley
 
---------------------------
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: male
Posts: 13730
Re: Hacking an answering machine II  
« Reply #8 on: Jun 1st, 2014, 1:08pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: Hacking an answering machine II  
« Reply #10 on: Jun 3rd, 2014, 11:23pm »
Quote Quote Modify 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 Quote Modify 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

   
WWW

Posts: 54
Re: Hacking an answering machine II  
« Reply #12 on: Sep 23rd, 2014, 11:14am »
Quote Quote Modify Modify

on May 31st, 2014, 1:54pm, dudiobugtron wrote:

 
I'm convinced.  Puzzle solved! Smiley
 
---------------------------
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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board