wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Hacking an answering machine II
        
(Message started by: dudiobugtron on May 26th, 2014, 4:06pm)
Title: Hacking an answering machine II
Post by dudiobugtron on May 26th, 2014, 4:06pm
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_medium;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: [hide]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.[/hide]
Title: Re: Hacking an answering machine II
Post by towr on May 30th, 2014, 3:32am
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.
Title: Re: Hacking an answering machine II
Post by Grimbal on May 30th, 2014, 3:52am
I wonder if there is a way to generate such a sequence with O(1) memory.
Title: Re: Hacking an answering machine II
Post by rmsgrey on May 30th, 2014, 6:11am

on 05/30/14 at 03:52:18, 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...
Title: Re: Hacking an answering machine II
Post by Grimbal on May 30th, 2014, 9:08am
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.
Title: Re: Hacking an answering machine II
Post by dudiobugtron on May 30th, 2014, 2:36pm

on 05/30/14 at 03:32:42, 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.
Title: Re: Hacking an answering machine II
Post by towr on May 31st, 2014, 12:55pm
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.)
Title: Re: Hacking an answering machine II
Post by dudiobugtron on May 31st, 2014, 1:54pm

on 05/31/14 at 12:55:20, 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?
Title: Re: Hacking an answering machine II
Post by towr on Jun 1st, 2014, 1:08pm
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.
Title: Re: Hacking an answering machine II
Post by dudiobugtron on Jun 3rd, 2014, 12:32am

on 06/01/14 at 13:08:23, 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.
Title: Re: Hacking an answering machine II
Post by towr on Jun 3rd, 2014, 11:23pm
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.
Title: Re: Hacking an answering machine II
Post by dudiobugtron on Jun 4th, 2014, 1:16pm
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?
Title: Re: Hacking an answering machine II
Post by wakiza33 on Sep 23rd, 2014, 11:14am

on 05/31/14 at 13:54:43, 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.


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