wu :: forums « wu :: forums - Hacking an answering machine II » Welcome, Guest. Please Login or Register. Dec 2nd, 2021, 5:35pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, towr, SMQ, ThudnBlunder, Eigenray, Icarus, william wu)    Hacking an answering machine II « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
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?

New riddle:
----------------------

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: 13729
 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: 7517
 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: 2844
 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: 7517
 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: 13729
 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: 13729
 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

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: 13729
 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}
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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »