Applied J: burglarly

[Dan Bron]

For convenience's sake, some cars allow you to unlock their doors with a numeric code rather than a key.  The code is entered on a buttonpad on the door.  Your mission, should you choose to accept it, is to become an efficient burglar of such cars.  I'll start you off with some hints.  Most cars have two glaring security flaws:
 
     (A)  Unlike, for example, a computer keyboard or cell phone, there is
          no "enter" or "send" key.  If you press the right 4 buttons in the
          right sequence, the car door unlocks.  Importantly, the lock
          ignores everything before and after the right sequence is pressed.

     (B)  You get as many chances as you want (you can press as many incorrect
          buttons as you like, with no ill consequences).

Let's examine a concrete example.  The following hold for most such locks:

    (C)  The unlock code consists of 4 button-presses.

    (D)  Though it appears there are 10 buttons, there are really
         only 5; each button merely carries two labels.  So there's no
         difference between (eg) pressing "1" or "2":

         [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]

So, if the buttons are labeled A B C D E respectively, and the unlock code is BCBC, then ABCBCC will open the door, as will DDDDDBCBCDDDDD, etc.  

Theoretically, there is some minimal length sequence which contains all possible codes (sub-sequences of 4 button pushes).  Your job is to construct a J program to find this sequence (given the set of all buttons and the length of the unlock code).

Put another way, write a dyadic J verb "burgle" whose output satisfies the following criteria: with the five buttons A B C D E  and the unlock code  key  (with  4=#key  )  then your sequence is defined by  sequence =: 4 burgle 'ABCDE'  and  key e. 4 ]\ sequence  with  #sequence  minimized.  Remember your dyad must be general enough to unlock a door with any number of buttons (given as the list   y  ) and an unlock sequence of any length (given as the  integer  x  ).

-Dan

PS:  I stole this idea from  http://www.everything2.com/index.pl?node_id=1520430  where the correct answer is given (for the specific case of  4=x  and  5=#y  )  in addition to pointers to the theory underlying its derivation.  Try to solve the puzzle first before visiting the link.

PPS:  Here's a picture of a car buttonpad:

     http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE7U88UruSI/S760/keyless_entry.jpg


----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Devon McCormick]

Dan - I solved a similar problem a number of years ago: the codes for
answering machines are often only 2-digits and they ignore incorrect parts
of the sequence before and after the correct one.  I recall that I came up
with a 101-digit "universal" answering machine code.  Back in the days when
the audio modem was prevalent, it was easy to program this to be sent over a
phone line as well, so you could crack it in one try.

Regards,

Devon

On 6/24/08, Dan Bron <j@...> wrote:

>
> For convenience's sake, some cars allow you to unlock their doors with a
> numeric code rather than a key.  The code is entered on a buttonpad on the
> door.  Your mission, should you choose to accept it, is to become an
> efficient burglar of such cars.  I'll start you off with some hints.  Most
> cars have two glaring security flaws:
>
>      (A)  Unlike, for example, a computer keyboard or cell phone, there is
>           no "enter" or "send" key.  If you press the right 4 buttons in
> the
>           right sequence, the car door unlocks.  Importantly, the lock
>           ignores everything before and after the right sequence is
> pressed.
>
>      (B)  You get as many chances as you want (you can press as many
> incorrect
>           buttons as you like, with no ill consequences).
>
> Let's examine a concrete example.  The following hold for most such locks:
>
>     (C)  The unlock code consists of 4 button-presses.
>
>     (D)  Though it appears there are 10 buttons, there are really
>          only 5; each button merely carries two labels.  So there's no
>          difference between (eg) pressing "1" or "2":
>
>          [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]
>
> So, if the buttons are labeled A B C D E respectively, and the unlock code
> is BCBC, then ABCBCC will open the door, as will DDDDDBCBCDDDDD, etc.
>
> Theoretically, there is some minimal length sequence which contains all
> possible codes (sub-sequences of 4 button pushes).  Your job is to construct
> a J program to find this sequence (given the set of all buttons and the
> length of the unlock code).
>
> Put another way, write a dyadic J verb "burgle" whose output satisfies the
> following criteria: with the five buttons A B C D E  and the unlock
> code  key  (with  4=#key  )  then your sequence is defined by  sequence =: 4
> burgle 'ABCDE'  and  key e. 4 ]\
> sequence  with  #sequence  minimized.  Remember your dyad must be general
> enough to unlock a door with any number of buttons (given as the list   y  )
> and an unlock sequence of any length (given as the  integer  x  ).
>
> -Dan
>
> PS:  I stole this idea from
> http://www.everything2.com/index.pl?node_id=1520430  where the correct
> answer is given (for the specific case of  4=x  and  5=#y  )  in addition to
> pointers to the theory underlying its derivation.  Try to solve the puzzle
> first before visiting the link.
>
> PPS:  Here's a picture of a car buttonpad:
>
>
> http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE7U88UruSI/S760/keyless_entry.jpg
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>

--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Henry Rich]

Linear Feedback Shift Registers are worth looking at.

Henry Rich

> -----Original Message-----
> From: programming-bounces@...
> [mailto:programming-bounces@...] On Behalf Of Dan Bron
> Sent: Tuesday, June 24, 2008 11:48 AM
> To: Programming forum
> Subject: [Jprogramming] Applied J: burglarly
>
> For convenience's sake, some cars allow you to unlock their
> doors with a numeric code rather than a key.  The code is
> entered on a buttonpad on the door.  Your mission, should you
> choose to accept it, is to become an efficient burglar of
> such cars.  I'll start you off with some hints.  Most cars
> have two glaring security flaws:
>  
>      (A)  Unlike, for example, a computer keyboard or cell
> phone, there is
>           no "enter" or "send" key.  If you press the right 4
> buttons in the
>           right sequence, the car door unlocks.  Importantly, the lock
>           ignores everything before and after the right
> sequence is pressed.
>
>      (B)  You get as many chances as you want (you can press
> as many incorrect
>           buttons as you like, with no ill consequences).
>
> Let's examine a concrete example.  The following hold for
> most such locks:
>
>     (C)  The unlock code consists of 4 button-presses.
>
>     (D)  Though it appears there are 10 buttons, there are really
>          only 5; each button merely carries two labels.  So
> there's no
>          difference between (eg) pressing "1" or "2":
>
>          [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]
>
> So, if the buttons are labeled A B C D E respectively, and
> the unlock code is BCBC, then ABCBCC will open the door, as
> will DDDDDBCBCDDDDD, etc.  
>
> Theoretically, there is some minimal length sequence which
> contains all possible codes (sub-sequences of 4 button
> pushes).  Your job is to construct a J program to find this
> sequence (given the set of all buttons and the length of the
> unlock code).
>
> Put another way, write a dyadic J verb "burgle" whose output
> satisfies the following criteria: with the five buttons A B C
> D E  and the unlock code  key  (with  4=#key  )  then your
> sequence is defined by  sequence =: 4 burgle 'ABCDE'  and  
> key e. 4 ]\ sequence  with  #sequence  minimized.  Remember
> your dyad must be general enough to unlock a door with any
> number of buttons (given as the list   y  ) and an unlock
> sequence of any length (given as the  integer  x  ).
>
> -Dan
>
> PS:  I stole this idea from  
> http://www.everything2.com/index.pl?node_id=1520430  where
> the correct answer is given (for the specific case of  4=x  
> and  5=#y  )  in addition to pointers to the theory
> underlying its derivation.  Try to solve the puzzle first
> before visiting the link.
>
> PPS:  Here's a picture of a car buttonpad:
>
>      
> http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE

7U88UruSI/S760/keyless_entry.jpg
>
>
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Oleg Kobchenko]

One simple way, not optimal, but not terribly bad, I think,
for burglars anyway ...

NB. 4 burg 5
burg=: 4 : 0
  B=. x#y
  L=. ''
  for_i. i.y^x do.
    p=. B#:i
    if. -.p +./@E. L do. L=. L,p end.
  end.
  L
)

   4 %~# 4 burg 5
166
   $ ((4#5)#:i.5^4) (+/@E."1 _) 4 burg 5
625
   0 e. ((4#5)#:i.5^4) (+/@E."1 _) 4 burg 5
0


--- On Tue, 6/24/08, Devon McCormick <devonmcc@...> wrote:
> Dan - I solved a similar problem a number of years ago ...
> that I came up with a 101-digit "universal" answering machine

   #2 burg 10
110
   $ ((2#10)#:i.10^2) (+/@E."1 _) 2 burg 10
100
   0 e. ((2#10)#:i.10^2) (+/@E."1 _) 2 burg 10
0



--- On Tue, 6/24/08, Dan Bron <j@...> wrote:

> For convenience's sake, some cars allow you to unlock
> their doors with a numeric code rather than a key.  The
> code is entered on a buttonpad on the door.  Your mission,
> should you choose to accept it, is to become an efficient
> burglar of such cars.  I'll start you off with some
> hints.  Most cars have two glaring security flaws:
>  
>      (A)  Unlike, for example, a computer keyboard or cell
> phone, there is
>           no "enter" or "send" key.  If
> you press the right 4 buttons in the
>           right sequence, the car door unlocks.
> Importantly, the lock
>           ignores everything before and after the right
> sequence is pressed.
>
>      (B)  You get as many chances as you want (you can
> press as many incorrect
>           buttons as you like, with no ill consequences).
>
> Let's examine a concrete example.  The following hold
> for most such locks:
>
>     (C)  The unlock code consists of 4 button-presses.
>
>     (D)  Though it appears there are 10 buttons, there are
> really
>          only 5; each button merely carries two labels.  So
> there's no
>          difference between (eg) pressing "1" or
> "2":
>
>          [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]
>
> So, if the buttons are labeled A B C D E respectively, and
> the unlock code is BCBC, then ABCBCC will open the door, as
> will DDDDDBCBCDDDDD, etc.  
>
> Theoretically, there is some minimal length sequence which
> contains all possible codes (sub-sequences of 4 button
> pushes).  Your job is to construct a J program to find this
> sequence (given the set of all buttons and the length of the
> unlock code).
>
> Put another way, write a dyadic J verb "burgle"
> whose output satisfies the following criteria: with the
> five buttons A B C D E  and the unlock code  key  (with
> 4=#key  )  then your sequence is defined by  sequence =: 4
> burgle 'ABCDE'  and  key e. 4 ]\ sequence  with
>  #sequence  minimized.  Remember your dyad must be general
> enough to unlock a door with any number of buttons (given
> as the list   y  ) and an unlock sequence of any length
> (given as the  integer  x  ).
>
> -Dan
>
> PS:  I stole this idea from
> http://www.everything2.com/index.pl?node_id=1520430  where
> the correct answer is given (for the specific case of  4=x
> and  5=#y  )  in addition to pointers to the theory
> underlying its derivation.  Try to solve the puzzle first
> before visiting the link.
>
> PPS:  Here's a picture of a car buttonpad:
>
>    
> http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE7U88UruSI/S760/keyless_entry.jpg
>
>
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm

     
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Raul Miller-4]

On 6/24/08, Oleg Kobchenko <olegykj@...> wrote:
> One simple way, not optimal, but not terribly bad, I think,
> for burglars anyway ...

If I add a lot of complexity, I can get a slightly shorter
list:

brgl=:4 :0
  U=. ~. x {."1 (A.&i.~ !) y
  L=. {.U
  while. 0 e. b=.U +./@E."1 L do.
    R=. U #~ -.b
    for_n. i.-x do.
      suf=. (-n){.L
      sel=. suf -:"1 n {."1 R
      if. 1 e. sel do.
        L=.L,n}.({.I.sel){R
        break.
      end.
    end.
  end.
  L
)

   $ 4 brgl 5
152

And, if I mix things up slightly, changing that first line to
  U=. (/: ?.~@#)~. x {."1 (A.&i.~ !) y

I can get an even shorter result:
   $ 4 brgl 5
129

--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Henry Rich]

Well, this problem certainly taught me something.

NB. Generate Lyndon words (aperiodic minimal necklaces)
NB. Adverb.
NB. m is the number of symbols in the alphabet
NB. y is the maximum length of the Lyndon words
NB. Result is list of boxes, each containing one Lyndon word.  The
NB. words are in lexicographic order
lyndon =: 1 : 0
NB. The monad initializes.  Combine the m and y values, and start
NB. with a complete list of 1-symbol lyndon words
(,. i. m) ;@:(<@((m,y) lyndon)"1) $0
:
NB. For the dyad, x is a lyndon word, and y is a suffix
NB. which makes a prenecklace but is not part of a lyndon word
NB. m is a list of (number of symbols),(max length)
'a k' =. m  NB. size of alphabet, max length
NB. If we have hit the length limit, don't do any more recursion.
if. k > x +&# y do.
NB. Find the starting symbol: we repeat the lyndon prefix as a possible
NB. prenecklace; higher values are legit lyndon words
  ss =. (#y) { x,y
  subwords =. x m lyndon y , ss
  if. a > st =. >:ss do.
    subwords =. subwords , ((x ,"1 y ,"1 0 st}. i. a)) ;@:(<@(m lyndon)"1) $0
  end.
else. subwords =. 0$a:
end.
NB. Make the return.  We return everything produced by lower levels (in order).
NB. If we were called with a valid Lyndon word, return that as the first word,
NB. since it will be the smallest lexicographic value
((0=#y)#<x) , subwords
)

NB. Generate de Bruijn sequence
NB. x is number of symbols in the alphabet
NB. y is the length of the groups
NB. The sequence is cyclic, and the length is x^y
NB. 2 debruijn 3   to generate the 8-symbol debruijn sequence for
NB. groups of 3 bits
NB. The debruijn sequence can be created by concatenating all the Lyndon
NB. words whose length divides x evenly, in lexicographic order
debruijn =: 4 : 0
; y (] #~ 0 = (|~ #@>)) x lyndon y
)
 
NB. Solve the problem originally posed
   burgle =: ] {~ <:@[ (] , {.) (debruijn~ #)

NB. Sample output
   # ~. 4 ]\ 4 burgle 'ABCDE'
AAAABAAACAAADAAAEAABBAABCAABDAABEAACBAACCAACDAACEAADBAADCAADDAAD...
   # ~. 4 ]\ 4 burgle 'ABCDE'
625


de Bruijn was Donald Knuth's beloved mentor.

Henry Rich

> -----Original Message-----
> From: programming-bounces@...
> [mailto:programming-bounces@...] On Behalf Of Dan Bron
> Sent: Tuesday, June 24, 2008 11:48 AM
> To: Programming forum
> Subject: [Jprogramming] Applied J: burglarly
>
> For convenience's sake, some cars allow you to unlock their
> doors with a numeric code rather than a key.  The code is
> entered on a buttonpad on the door.  Your mission, should you
> choose to accept it, is to become an efficient burglar of
> such cars.  I'll start you off with some hints.  Most cars
> have two glaring security flaws:
>  
>      (A)  Unlike, for example, a computer keyboard or cell
> phone, there is
>           no "enter" or "send" key.  If you press the right 4
> buttons in the
>           right sequence, the car door unlocks.  Importantly, the lock
>           ignores everything before and after the right
> sequence is pressed.
>
>      (B)  You get as many chances as you want (you can press
> as many incorrect
>           buttons as you like, with no ill consequences).
>
> Let's examine a concrete example.  The following hold for
> most such locks:
>
>     (C)  The unlock code consists of 4 button-presses.
>
>     (D)  Though it appears there are 10 buttons, there are really
>          only 5; each button merely carries two labels.  So
> there's no
>          difference between (eg) pressing "1" or "2":
>
>          [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]
>
> So, if the buttons are labeled A B C D E respectively, and
> the unlock code is BCBC, then ABCBCC will open the door, as
> will DDDDDBCBCDDDDD, etc.  
>
> Theoretically, there is some minimal length sequence which
> contains all possible codes (sub-sequences of 4 button
> pushes).  Your job is to construct a J program to find this
> sequence (given the set of all buttons and the length of the
> unlock code).
>
> Put another way, write a dyadic J verb "burgle" whose output
> satisfies the following criteria: with the five buttons A B C
> D E  and the unlock code  key  (with  4=#key  )  then your
> sequence is defined by  sequence =: 4 burgle 'ABCDE'  and  
> key e. 4 ]\ sequence  with  #sequence  minimized.  Remember
> your dyad must be general enough to unlock a door with any
> number of buttons (given as the list   y  ) and an unlock
> sequence of any length (given as the  integer  x  ).
>
> -Dan
>
> PS:  I stole this idea from  
> http://www.everything2.com/index.pl?node_id=1520430  where
> the correct answer is given (for the specific case of  4=x  
> and  5=#y  )  in addition to pointers to the theory
> underlying its derivation.  Try to solve the puzzle first
> before visiting the link.
>
> PPS:  Here's a picture of a car buttonpad:
>
>      
> http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE
> 7U88UruSI/S760/keyless_entry.jpg
>
>
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Raul Miller-4]

Here's the shortest sequence I've found, for four letter combinations
of 'abcde':

abceadceabdecbadebcaedcbaecdbacdeabcdaecbdaebdcebdacebadcbedca
becadecabdcaebcdebacedbaedbcadbeadbcedabedacbdeacbeacdbecdabc

That should be 123 characters, once it's "unwrapped".

I used the code I posted earlier but using ? instead of ?. and
ran it several times.  Slightly over 1% of my results have
length 123.

--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Henry Rich]

We must be solving different problems.  There are 5^4=625 different
combinations for 4 pushes of 5 buttons; so the shortest possible
answer is 629 characters.

Maybe you're assuming the buttons can't be repeated?

Henry Rich

> -----Original Message-----
> From: programming-bounces@...
> [mailto:programming-bounces@...] On Behalf Of Raul Miller
> Sent: Wednesday, June 25, 2008 5:42 PM
> To: Programming forum
> Subject: Re: [Jprogramming] Applied J: burglarly
>
> Here's the shortest sequence I've found, for four letter combinations
> of 'abcde':
>
> abceadceabdecbadebcaedcbaecdbacdeabcdaecbdaebdcebdacebadcbedca
> becadecabdcaebcdebacedbaedbcadbeadbcedabedacbdeacbeacdbecdabc
>
> That should be 123 characters, once it's "unwrapped".
>
> I used the code I posted earlier but using ? instead of ?. and
> ran it several times.  Slightly over 1% of my results have
> length 123.
>
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Robert P. Rumble]

At 11:48 AM 6/24/2008 -0400, you wrote:
[snip]

>PS:  I stole this idea from
http://www.everything2.com/index.pl?node_id=1520430   where the correct
answer is given (for the specific case of  4=x  and  5=#y  )  in addition
to pointers to the theory underlying its derivation.  Try to solve the
puzzle first before visiting the link.
>
[snip]


Actually, the solution in
http://www.everything2.com/index.pl?node_id=1520430 was for the specific
case x (unlock length) = 5, not 4.
Robert P. Rumble
rrumble1@...
[phone]
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Raul Miller-4]

On 6/25/08, Henry Rich <HenryHRich@...> wrote:
> Maybe you're assuming the buttons can't be repeated?

I did assume that the buttons can't be repeated.

--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Dan Bron]

Robert P. Rumble wrote:
> Actually, the solution ... was for
> the specific case x (unlock length) = 5, not 4.  

Oops.  Yes, you're right.  Thanks.

-Dan

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Devon McCormick]

Oleg - when I saw the length of "2 burg 10", I thought maybe I had
mis-remembered the length of my long-ago solution.

However upon inspection, I see that your solution has unnecessary entries:

   #2 burg 10
110
   2 burg 10
 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9
2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 3 3 4 3 5 3 6 3 7 3 8 3 9 4 4 4 5 4 6 4 7
4 8 4 9 5 5 5 6 5 7 5 8 5 9 6 6 6 7 6 8 6 9 7 7 7 8 7 9 8 8 8 9 9 0
NB. Removing dupes by hand:
#0 0   1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 1    2 1 3 1 4 1 5 1 6 1 7 1 8 1
9 2 2    3 2 4 2 5 2 6 2 7 2 8 2 9 3 3     4 3 5 3 6 3 7 3 8 3 9 4 4     5 4
6 4 7 4 8 4 9 5 5    6 5 7 5 8 5 9 6 6    7 6 8 6 9 7 7      8 7 9 8 8 9 9 0
101

Regards,

Devon

On 6/24/08, Oleg Kobchenko <olegykj@...> wrote:

>
> One simple way, not optimal, but not terribly bad, I think,
> for burglars anyway ...
>
> NB. 4 burg 5
> burg=: 4 : 0
>   B=. x#y
>   L=. ''
>   for_i. i.y^x do.
>     p=. B#:i
>     if. -.p +./@E. L do. L=. L,p end.
>   end.
>   L
> )
>
> ...
> --- On Tue, 6/24/08, Devon McCormick <devonmcc@...> wrote:
> > Dan - I solved a similar problem a number of years ago ...
>
> > that I came up with a 101-digit "universal" answering machine
>
>
>    #2 burg 10
> 110
> htm
>

...


--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Mark D. Niemiec]

"Henry Rich" <HenryHRich@...> wrote:
> We must be solving different problems.  There are 5^4=625 different
> combinations for 4 pushes of 5 buttons; so the shortest possible
> answer is 629 characters.

If there were a break (say, pressing Enter) between each group of buttons,
625 presses should get all combinations. However, since there is no break,
sequences can overlap, greatly reducing the number of presses. Since
each button can be used in up to 4 sequences, this places a lower bound
of 160 presses (4+>.625/4) on the solution.

If repeats are not allowed, this reduces the number of allowable codes
to 320, and imposes a lower bound of 84 on the solution.

   $ ((*./@:(2&(~:/\))&>)#]) ,{4$<'abcde'
320

-- Mark D. Niemiec <mniemiec@...>

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[Oleg Kobchenko]

Here's a complete simple but brute force sequencer.

However, I cannot figure out how to construct it using LFSR.
Any ideas?

  http://en.wikipedia.org/wiki/Linear_feedback_shift_register


NB. brute force De Bruijn sequencer
burg2=: 3 : 0
  (#y) t y
:
  S=. (x #&<: #y),0             NB. seed
  while. 1 do.
    L=. ((-x-1){.S) ,"1 0 i.#y  NB. tail + alphabet
    E=. L +./@E."1 S            NB. which already occurs
    I=. E i. 0                  NB. first unique
    if. I=#y do. break. end.
    S=. S,I                     NB. append unique
  end.
  S{y
)

Note 'Test'
   #4 burg2 'ABCDE'
628
   #~.4]\4 burg2 'ABCDE'
625
   #5 burg2 'ABCDE'       NB. sequence length 4+5^5
3129
   #~.5]\5 burg2 'ABCDE'  NB. unique codes 5^5
3125
   #2 burg2 '0123456789'  NB. Devon's example
101
)

--- On Wed, 6/25/08, Henry Rich <HenryHRich@...> wrote:

Well, this problem certainly taught me something.

NB. Generate Lyndon words (aperiodic minimal necklaces)
NB. Adverb.
NB. m is the number of symbols in the alphabet
NB. y is the maximum length of the Lyndon words
NB. Result is list of boxes, each containing one Lyndon word.  The
NB. words are in lexicographic order
lyndon =: 1 : 0
NB. The monad initializes.  Combine the m and y values, and start
NB. with a complete list of 1-symbol lyndon words
(,. i. m) ;@:(<@((m,y) lyndon)"1) $0
:
NB. For the dyad, x is a lyndon word, and y is a suffix
NB. which makes a prenecklace but is not part of a lyndon word
NB. m is a list of (number of symbols),(max length)
'a k' =. m  NB. size of alphabet, max length
NB. If we have hit the length limit, don't do any more recursion.
if. k > x +&# y do.
NB. Find the starting symbol: we repeat the lyndon prefix as a possible
NB. prenecklace; higher values are legit lyndon words
  ss =. (#y) { x,y
  subwords =. x m lyndon y , ss
  if. a > st =. >:ss do.
    subwords =. subwords , ((x ,"1 y ,"1 0 st}. i. a)) ;@:(<@(m lyndon)"1) $0
  end.
else. subwords =. 0$a:
end.
NB. Make the return.  We return everything produced by lower levels (in order).
NB. If we were called with a valid Lyndon word, return that as the first word,
NB. since it will be the smallest lexicographic value
((0=#y)#<x) , subwords
)

NB. Generate de Bruijn sequence
NB. x is number of symbols in the alphabet
NB. y is the length of the groups
NB. The sequence is cyclic, and the length is x^y
NB. 2 debruijn 3   to generate the 8-symbol debruijn sequence for
NB. groups of 3 bits
NB. The debruijn sequence can be created by concatenating all the Lyndon
NB. words whose length divides x evenly, in lexicographic order
debruijn =: 4 : 0
; y (] #~ 0 = (|~ #@>)) x lyndon y
)

NB. Solve the problem originally posed
   burgle =: ] {~ <:@[ (] , {.) (debruijn~ #)

NB. Sample output
   # ~. 4 ]\ 4 burgle 'ABCDE'
AAAABAAACAAADAAAEAABBAABCAABDAABEAACBAACCAACDAACEAADBAADCAADDAAD...
   # ~. 4 ]\ 4 burgle 'ABCDE'
625


de Bruijn was Donald Knuth's beloved mentor.

Henry Rich

> -----Original Message-----
> From: programming-bounces@...
> [mailto:programming-bounces@...] On Behalf Of Dan Bron
> Sent: Tuesday, June 24, 2008 11:48 AM
> To: Programming forum
> Subject: [Jprogramming] Applied J: burglarly
>
> For convenience's sake, some cars allow you to unlock their
> doors with a numeric code rather than a key.  The code is
> entered on a buttonpad on the door.  Your mission, should you
> choose to accept it, is to become an efficient burglar of
> such cars.  I'll start you off with some hints.  Most cars
> have two glaring security flaws:
>  
>      (A)  Unlike, for example, a computer keyboard or cell
> phone, there is
>           no "enter" or "send" key.  If you press the right 4
> buttons in the
>           right sequence, the car door unlocks.  Importantly, the lock
>           ignores everything before and after the right
> sequence is pressed.
>
>      (B)  You get as many chances as you want (you can press
> as many incorrect
>           buttons as you like, with no ill consequences).
>
> Let's examine a concrete example.  The following hold for
> most such locks:
>
>     (C)  The unlock code consists of 4 button-presses.
>
>     (D)  Though it appears there are 10 buttons, there are really
>          only 5; each button merely carries two labels.  So
> there's no
>          difference between (eg) pressing "1" or "2":
>
>          [1 | 2]  [3 | 4]  [5 | 6]  [7 | 8]  [9 | 0]
>
> So, if the buttons are labeled A B C D E respectively, and
> the unlock code is BCBC, then ABCBCC will open the door, as
> will DDDDDBCBCDDDDD, etc.
>
> Theoretically, there is some minimal length sequence which
> contains all possible codes (sub-sequences of 4 button
> pushes).  Your job is to construct a J program to find this
> sequence (given the set of all buttons and the length of the
> unlock code).
>
> Put another way, write a dyadic J verb "burgle" whose output
> satisfies the following criteria: with the five buttons A B C
> D E  and the unlock code  key  (with  4=#key  )  then your
> sequence is defined by  sequence =: 4 burgle 'ABCDE'  and
> key e. 4 ]\ sequence  with  #sequence  minimized.  Remember
> your dyad must be general enough to unlock a door with any
> number of buttons (given as the list   y  ) and an unlock
> sequence of any length (given as the  integer  x  ).
>
> -Dan
>
> PS:  I stole this idea from
> http://www.everything2.com/index.pl?node_id=1520430  where
> the correct answer is given (for the specific case of  4=x
> and  5=#y  )  in addition to pointers to the theory
> underlying its derivation.  Try to solve the puzzle first
> before visiting the link.
>
> PPS:  Here's a picture of a car buttonpad:
>
>    
> http://bp3.blogger.com/_AKM4HWd7eMo/RwaWHOmXQmI/AAAAAAAAAAc/WE
> 7U88UruSI/S760/keyless_entry.jpg

     
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

[eesuk]

On Fri, Jun 27, 2008 at 4:00 AM, Oleg Kobchenko <olegykj@...> wrote:

> However, I cannot figure out how to construct it using LFSR.
> Any ideas?
>

AFAIK,  with N alphabet , LFSR-like generator could generate (5&p:
N^L) sequences length of L.
Thus full sequences could be genreated using LFSR-like generator when
N is prime.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm