Author 
Topic: Hacking an answering machine II (Read 3138 times) 

dudiobugtron
Uberpuzzler
Posts: 676


Hacking an answering machine II
« on: May 26^{th}, 2014, 4:06pm » 
Quote Modify

This is a followup 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 bruteforce 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/cgibin/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 26^{th}, 2014, 4:53pm by dudiobugtron » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13595


Re: Hacking an answering machine II
« Reply #1 on: May 30^{th}, 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 30^{th}, 2014, 3:36am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7361


Re: Hacking an answering machine II
« Reply #2 on: May 30^{th}, 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: 2812


Re: Hacking an answering machine II
« Reply #3 on: May 30^{th}, 2014, 6:11am » 
Quote Modify

on May 30^{th}, 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 bruteforce it by having the full sequences preloaded in (large) finite memory...


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7361


Re: Hacking an answering machine II
« Reply #4 on: May 30^{th}, 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 4^{th}, 2014, 1:53am by Grimbal » 
IP Logged 



dudiobugtron
Uberpuzzler
Posts: 676


Re: Hacking an answering machine II
« Reply #5 on: May 30^{th}, 2014, 2:36pm » 
Quote Modify

on May 30^{th}, 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: 13595


Re: Hacking an answering machine II
« Reply #6 on: May 31^{st}, 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: 676


Re: Hacking an answering machine II
« Reply #7 on: May 31^{st}, 2014, 1:54pm » 
Quote Modify

on May 31^{st}, 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(n1). So that part is solved as well. What happens though if you don't have n1 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: 13595


Re: Hacking an answering machine II
« Reply #8 on: Jun 1^{st}, 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: 676


Re: Hacking an answering machine II
« Reply #9 on: Jun 3^{rd}, 2014, 12:32am » 
Quote Modify

on Jun 1^{st}, 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: 13595


Re: Hacking an answering machine II
« Reply #10 on: Jun 3^{rd}, 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 3^{rd}, 2014, 11:25pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



dudiobugtron
Uberpuzzler
Posts: 676


Re: Hacking an answering machine II
« Reply #11 on: Jun 4^{th}, 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 4^{th}, 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 23^{rd}, 2014, 11:14am » 
Quote Modify

on May 31^{st}, 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(n1). So that part is solved as well. What happens though if you don't have n1 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



