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: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] 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
