Oh, I forgot to rename it. Thanks. --- On Fri, 6/27/08, Arie Groeneveld <[EMAIL PROTECTED]> wrote:
> Oleg, > > May be I miss something, but I don't understand the > monadic part. > > burg2 i.3 > |value error: t > | (#y) t y > > For me it works fine if I replace the monadic part with: > (#y) burg2 y > > > =@@i > > > Oleg Kobchenko schreef: > > 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 > > > > > > > ---------------------------------------------------------------------- > For information about J forums see > http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
