Linear Feedback Shift Registers are worth looking at. 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
