--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed
I apologize for the 11th hour solution; this week was busy. It took
me a while to come up with an algorithm that would actually produce
fewer keystrokes than the naive just write-out-every-code-so-long-as-
it-isn't-already-tested solution in every case. After trying a few
(I believe 3 is the number) poor solutions, I was getting frustrated,
so I figured I'd just try to work through it backwards. This worked
out rather well, I think (it beats the naive solution by over 70,000
strokes on the 5-digit, 3-stop case). It was pretty fun, too: I
actually had a reason to use lambda and shift (which I've never used
before), as well as inject (which I've only used once before).
Of course, it takes a while to run (the 5 digit, 3 stop code case
took nearly 40 minutes on a dual 2.7GHz PowerMac G5), so I'm
providing the output as well as the code.
So, here're my results:
user system total real
One stop digit:
2 digits 0.010000 0.000000 0.010000 ( 0.006755)
Search space exhausted.
Tested 100 of 100 codes in 271 keystrokes.
0 codes were tested more than once.
============================================================
3 digits 0.110000 0.000000 0.110000 ( 0.132552)
Search space exhausted.
Tested 1000 of 1000 codes in 3439 keystrokes.
0 codes were tested more than once.
============================================================
4 digits 9.580000 0.260000 9.840000 ( 11.005426)
Search space exhausted.
Tested 10000 of 10000 codes in 40951 keystrokes.
0 codes were tested more than once.
============================================================
5 digits 1208.900000 23.850000 1232.750000 (1439.590285)
Search space exhausted.
Tested 100000 of 100000 codes in 468682 keystrokes.
46 codes were tested more than once.
============================================================
Three stop digits:
2 digits 0.010000 0.000000 0.010000 ( 0.005834)
Search space exhausted.
Tested 100 of 100 codes in 219 keystrokes.
0 codes were tested more than once.
============================================================
3 digits 0.170000 0.000000 0.170000 ( 0.196276)
Search space exhausted.
Tested 1000 of 1000 codes in 2545 keystrokes.
4 codes were tested more than once.
============================================================
4 digits 16.580000 0.300000 16.880000 ( 19.149404)
Search space exhausted.
Tested 10000 of 10000 codes in 28105 keystrokes.
96 codes were tested more than once.
============================================================
5 digits 1910.240000 27.430000 1937.670000 (2240.603938)
Search space exhausted.
Tested 100000 of 100000 codes in 299559 keystrokes.
1517 codes were tested more than once.
============================================================
My code is attached, along with alarm_keypad.rb (which contains the
AlarmKeypad class).
Tim
--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0755;
x-mac-creator=454D4178;
name="mirror_bne.rb"
Content-Disposition: attachment;
filename=mirror_bne.rb
#!/usr/bin/env ruby -w
require 'alarm_keypad'
require 'benchmark'
def crack_code (code_length, stop_digits)
# This is the weak part of the algorithm (in the case of there being more than 1 stop digit)
# Unfortunately, I don't have the time right now to write something better than a random
# selection.
stop_digit = lambda { stop_digits[rand(stop_digits.size)].to_s }
pad = AlarmKeypad.new code_length, stop_digits
# Work with codes with lots of stop digits in them first.
all_codes = ("0"*code_length.."9"*code_length).to_a.sort_by{|c| num_of_stop_digs c, stop_digits }.reverse
# This algorithm works backwards, so we start with a stop digit, followed by a code.
# You may notice that this doesn't reverse the codes themselves, which means that
# the code that will actually get input into the pad is the reverse of the code used.
solution = stop_digits[0].to_s + all_codes.shift
while !all_codes.empty?
match = /[#{stop_digits.join}](.{0,#{code_length-1}})$/.match(solution[-code_length..-1])
string = (match ? match[1] : nil)
if match.nil?
solution << stop_digit.call + all_codes.shift
elsif string.nil? || string.empty?
solution << all_codes.shift
else
overlap = match ? string.size : 0
code = all_codes.find { |c| c.index(string) == 0 }
if code.nil?
code = all_codes.shift
solution << stop_digit.call + code
else
all_codes.delete code
solution << code[overlap..-1]
end
end
end
solution.reverse.split(//).each{ |d| pad.press d.to_i }
pad
end
def num_of_stop_digs (code, stop_digits)
stop_digits.inject(0) { |num_stop_digs, dig| num_stop_digs + code.count(dig.to_s) }
end
if __FILE__ == $PROGRAM_NAME
include Benchmark
bm(10) do |x|
hacked_pad = nil
puts "One stop digit:\n"
puts
for i in (2..5)
x.report("#{i} digits") { hacked_pad = crack_code(i, [1]) }
hacked_pad.summarize
puts "="*60
end
puts
puts "Three stop digits:"
puts
for i in (2..5)
x.report("#{i} digits") { hacked_pad = crack_code(i, [1,2,3]) }
hacked_pad.summarize
puts "="*60
end
end
end
--Apple-Mail-2-25062225
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0644;
x-mac-creator=454D4178;
name="alarm_keypad.rb"
Content-Disposition: attachment;
filename=alarm_keypad.rb
#!/usr/bin/env ruby -w
#
# 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__
hacked_pads = []
for i in (1..5)
a = AlarmKeypad.new(i, [1, 2, 3])
("0"*i.."9"*i).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
end
for i in (1..5)
a = AlarmKeypad.new(i, [1])
("0"*i.."9"*i).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
end
--Apple-Mail-2-25062225--