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