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/WE7U88UruSI/S760/keyless_entry.jpg
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
