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
