by Stephen Waits
Like many homeowners, I have a residential monitored alarm system installed in my house. It consists of a few keypads and several remote sensors.
My alarm has three modes of operation:
1. Off - completely disarmed
2. Away - everything (perimeter and interior) armed
3. Stay - perimeter armed
The keypad consists of 12 buttons, which includes the digits '0' through '9', plus '*' and '#'. The '*' and '#' are only used for special programming.
The digits '1', '2', and '3' are also labeled "Off", "Away", and "Stay". This corresponds to the three system modes mentioned above.
The security code is 4 digits long. To set or change the system's mode, you simply enter your 4 digit security code, followed by the digit ('1', '2', or '3') which corresponds to the mode you want to set.
For example, if the security code was 1234:
12341 - sets system to "Off"
12342 - sets system to "Away"
12343 - sets system to "Stay"
What if you make a mistake when you're entering your code? Yes, this is where an interesting observation comes into play. To answer the question... if you make a mistake you just start over. In other words, the keypad seems to only care that the last 5 keypresses match a valid code+command sequence.
For example, if you entered the first two digits of your code incorrectly, you could just simply start over with the correct code, without any kind of reset:
8912341
++ => first 2 keypresses erroneous, oops!
+++++ => last 5 keypresses == valid code+command sequence
The thought occurs to me, and I'm sure to the reader, that perhaps this can be exploited. For example, if you entered the sequence 1234123, you are actually testing 3 different codes:
1234123 => what you entered
12341 => 1234 + 1/off
.23412 => 2341 + 2/away
..34123 => 3412 + 3/stay
Problems:
1. What is the shortest sequence of digits you can come up with that tests every code in this alarm system? The worst case is 5*10**4, or 50000 keypresses.
2. What if the security code was 5 digits instead of 4? Worst case here is 6*10**5, or 600000 keypresses.
3. What if the "stop digits" changed from [1, 2, 3], to just [1]? For instance, maybe the system is armed (mode 2 or 3) and only actually beeps when switching to mode 1. (See Assumptions below)
4. Can you also minimize the number of duplicate code tests?
Assumptions:
* We assume the keypad will actually let you go on entering digits for this long. I haven't tested it, but it seems silly that it might actually allow this. However, as a long time comp.risks reader, almost nothing surprises me.
* We assume that the keypad will always signify a valid code+command sequence, regardless of mode. In reality, if you set to Away when it's already in Away, it might not emit it's "success" signal.
#
# Stephen Waits <steve@waits.net>
#
class AlarmKeypad
# init a keypad, with length of security code, and the code's
# stop digits
def initialize(code_length = 4, stop_digits = [1,2,3])
# remember the length of the security code
@code_length = code_length
# and which digits cause a code to be checked
@stop_digits = stop_digits
# and reset our data structures to 0
clear
end
# reset keypad to initial state
def clear
# an array of each code and how many times it's been entered
@codes = Array.new(10**@code_length,0)
# last N+1 keypad button presses
@key_history = []
# total number of keypad button presses
@key_presses = 0
end
# press a single digit
def press(digit)
# add digit to key history
@key_history.shift while @key_history.size > @code_length
@key_history << digit
@key_presses += 1
# see if we just tested a code
if @stop_digits.include?(@key_history.last) and
@key_history.length > @code_length
@codes[@key_history[0,@code_length].join.to_i] += 1
end
end
# find out if every code had been tested
def fully_tested?
not @codes.include?(0)
end
# find out if an individual code has been tested
# NOTE: an actual keypad obviously doesn't offer this functionality;
# but, it's useful and convenient (and might save duplication)
def tested?(code)
@codes[code] > 0
end
# output a summary
def summarize
tested = @codes.select { |c| c > 0 }.size
tested_multiple = @codes.select { |c| c > 1 }.size
puts "Search space exhausted." if fully_tested?
puts "Tested #{tested} of #{@codes.size} codes " +
"in #{@key_presses} keystrokes."
puts "#{tested_multiple} codes were tested more than once."
end
end
if $0 == __FILE__
# a random button presser, 3 digit codes
a = AlarmKeypad.new(3)
a.press( rand(10) ) until a.fully_tested?
a.summarize
# sequential code entry, 4 digit codes
a = AlarmKeypad.new(4)
("0000".."9999").each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(rand(3)+1)
end
a.summarize
# sequential code entry, 5 digit codes, only [1] as a stop digit
a = AlarmKeypad.new(5,[1])
("00000".."99999").each do |c|
next if a.tested?(c.to_i)
c.split(//).each { |d| a.press(d.to_i) }
a.press(1)
end
a.summarize
end
Quiz Summary
This quiz turned out to be surprisingly tough. Ross Bamford seemed to get the tighter solution and it's not as big a difference as you might think. Here's some output from running Ross's solution:
### 4 digits, [1,2,3] stops ###
user system total real
seq. 1.000000 0.020000 1.020000 ( 1.021674)
Search space exhausted.
Tested 10000 of 10000 codes in 50000 keystrokes.
6146 codes were tested more than once.
seq/chk 0.790000 0.000000 0.790000 ( 0.804365)
Search space exhausted.
Tested 10000 of 10000 codes in 33395 keystrokes.
2557 codes were tested more than once.
simple 2.840000 0.040000 2.880000 ( 2.930310)
Search space exhausted.
Tested 10000 of 10000 codes in 33830 keystrokes.
2721 codes were tested more than once.
best 665.050000 5.390000 670.440000 (678.840230)
Search space exhausted.
Tested 10000 of 10000 codes in 28687 keystrokes.
464 codes were tested more than once.
Compare that with the trivial tests in the quiz code:
Search space exhausted.
Tested 10000 of 10000 codes in 33635 keystrokes.
2664 codes were tested more than once.
At "best", Ross managed to trim 4,948 keystrokes and there was a hefty time penalty to pay for getting that far.
Let's work through the code that amounts to the "best" search. First we need to examine a helper class it makes use of:
class PoolStr < String
def initialize(obj, parent = nil)
super(obj)
@parent = parent
end
def suffixes(maxlen = nil)
@suffixes ||= get_suffixes(maxlen).map do |s|
PoolStr.new(s,self)
end
end
def prefixes(maxlen = nil)
@prefixes ||= get_suffixes(maxlen,reverse).map do |s|
PoolStr.new(s.reverse,self)
end
end
private
def get_suffixes(maxlen = nil, str = self)
start = maxlen ? str.length-maxlen : 1
(start..(str.length-1)).map do |i|
suf = str[i..-1]
suf
end
end
end
There's nothing too tricky hiding in here. Basically we have a String, that can give us an Array of suffixes or prefixes as needed. Those are both found with some simple index work in get_suffixes(). To handle prefixes, the String is reversed before it goes in, and the suffixes are reversed as they come out to transform them into prefixes. Note that both of these are cached the first time they are figured, to speed up future calls. (I'm not sure what @parent is for here. It doesn't seem to be used.)
Next we need to look at one more short helper, which turns out to be the heart of the "seq." search from the results:
# compressible string (less stop digits = longer string).
def mkpool(digits, stops)
(("0"*digits)..("9"*digits)).inject([]) do |ary,e|
ary << PoolStr.new("#{e}#{stops[rand(stops.length)] if stops}", nil)
end
end
Again, nothing tricky here. Assuming a parameter of 4 for digits, this builds an Array of the codes from "0000" to "9999", with a random stop digit at the end of each one.
Now we are ready for the main method of the "best" search:
# that takes _forever_ but gives (slightly) better results.
def best_code(digits, stops = [1,2,3])
out = ""
pool = mkpool(digits, stops)
best = []
bestcode = nil
# Keep going until it's empty - if ever we can't find a match
# we'll just take one at random.
until pool.empty?
unless bestcode
# first iteration, just grab a start and carry on
bestscore = 0
bestcode = pool[rand(pool.length)]
else
# Get the array of arrays of best matches for the previous code.
# This array matches suffixes to best-fit prefixes for
# the previously-added code to find the most mergeable code
# (i.e. the one that shares most of it's prefix with the end
# of the output string).
#
# This contains at a given index all the codes that share that
# many letters of pre/suffix with 'need'. Eh? Well, it's like this:
#
# best for "1234" => [ nil, ["4321", "4048"], ["3412"], ["2348"]]
#
# Then, (one of) the highest scoring code(s) is taken from
# the top of the last nested array, best[best.length-1].
#
# We do it this way, rather than reversing the array, because
# we need to know what the actual score was, to merge the
# strings. Running on each iteration helps a bit
# with performance, since as time goes on the number of
# elements decreases.
best.clear
pool.each do |nxt|
next if nxt == bestcode
if r = (bestcode.suffixes & nxt.prefixes).first
(best[r.length] ||= []) << nxt
end
end
bestcode = (best[bestscore = best.length - 1] || EMPTYARRAY).first
# No best code? Nothing with matching pre/suff, so let's just grab
# a code at random instead to keep things moving.
unless bestcode
bestscore = 0
bestcode = pool[rand(pool.length)]
end
end
# Remove from the pool. Bit slow...
pool[pool.index(bestcode),1] = nil
# Chop off matched prefix from this code and append it
merged = bestcode[bestscore..-1]
out << merged
end
out
end
Here's the beast, but the comments are good and they will get us through it. First you can see that the method makes a pool of all the codes, using the mkpool() method we just examined. Now anytime this method doesn't have a bestcode, like right at the beginning here, it just pulls one at random from the pool. (You can see the code for this in the first unless clause and at the end of the big else clause.)
The real work is done right after that big comment. The pool is walked comparing prefixes of possible codes with the suffixes of the bestcode (our last find). The matching groups are placed in an Array where the index is their score or how many digits they share. The code then just chooses a match with the highest score so it shares the most possible digits. (The EMPTYARRAY constant used here is defined elsewhere in the code as `EMPTYARRAY = []`.)
From there the code merges the suffix of the selected code (we already have the matching prefix from the last code), and adds it to the digits to enter. It then loops until the pool is exhausted.
The actual solution is just one line from that:
You saw the results of that at the beginning of this summary. You would have to examine usage for this code carefully though, to determine if shaving around 5,000 keystrokes is worth the unfortunately large speed penalty. It's all about tradeoffs.
A huge thank you to the quiz creator for a challenging little problem and the two brave souls who were equal to the task.
Tomorrow's quiz is still up in the air! We're trying to sneak in a research project we can all help with, if we can get it ready in time...
