From: Timothy Bennett <timothy.s.bennett@...>
Date: 2006-03-30T12:15:22+09:00
Subject: Re: [QUIZ] B & E (#72)

--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--