From: Ross Bamford <rossrt@...>
Date: 2006-03-28T01:18:07+09:00
Subject: Re: [QUIZ] B & E (#72)

--=-mInLvOB6Mci9vowW5PV7
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

Hmm, this is a tricky one :) This solution is pretty ugly (I've not
seriously tried to clean it up, either) and slow.

There are actually two solutions in here, one that's fast and 'good
enough' for the smaller digit counts, and one that's *very* slow but
gives shorter results with less retesting of codes.

Neither of these are all that much better than simply running through
and checking each code against AlarmKeypad#tested? but then that's to be
expected I guess, perhaps this is why real alarms don't tend to
duplicate that functionality :P

I ran benchmarked tests to get an idea of how it did. The tests are
doing simple sequential tests (seq), sequential using tested? (seq/chk),
the simple/quick(er) way (simple) and the slow, better way (best). Check
out the 'best' time for 4 digit codes - there has to be room for
improvement there :/ 



 ### 2 digits, [1,2,3] stops ###
      user     system      total        real
seq.     0.010000   0.000000   0.010000 (  0.005530)
Search space exhausted.
Tested 100 of 100 codes in 300 keystrokes.
39 codes were tested more than once.

seq/chk  0.010000   0.000000   0.010000 (  0.008893)
Search space exhausted.
Tested 100 of 100 codes in 234 keystrokes.
11 codes were tested more than once.

simple   0.000000   0.000000   0.000000 (  0.006074)
Search space exhausted.
Tested 100 of 100 codes in 243 keystrokes.
15 codes were tested more than once.

best     0.050000   0.000000   0.050000 (  0.054995)
Search space exhausted.
Tested 100 of 100 codes in 223 keystrokes.
2 codes were tested more than once.


 ### 3 digits, [1,2,3] stops ###
      user     system      total        real
seq.     0.070000   0.000000   0.070000 (  0.064838)
Search space exhausted.
Tested 1000 of 1000 codes in 4000 keystrokes.
513 codes were tested more than once.

seq/chk  0.060000   0.000000   0.060000 (  0.062613)
Search space exhausted.
Tested 1000 of 1000 codes in 2944 keystrokes.
224 codes were tested more than once.

simple   0.090000   0.000000   0.090000 (  0.086938)
Search space exhausted.
Tested 1000 of 1000 codes in 2960 keystrokes.
223 codes were tested more than once.

best     6.430000   0.050000   6.480000 (  6.741495)
Search space exhausted.
Tested 1000 of 1000 codes in 2623 keystrokes.
50 codes were tested more than once.


 ### 4 digits, [1,2,3] stops ###
      user     system      total        real
seq.     0.820000   0.020000   0.840000 (  0.871923)
Search space exhausted.
Tested 10000 of 10000 codes in 50000 keystrokes.
6108 codes were tested more than once.

seq/chk  0.690000   0.010000   0.700000 (  0.704795)
Search space exhausted.
Tested 10000 of 10000 codes in 33395 keystrokes.
2569 codes were tested more than once.

simple   1.830000   0.030000   1.860000 (  1.869937)
Search space exhausted.
Tested 10000 of 10000 codes in 33555 keystrokes.
2620 codes were tested more than once.

best   781.350000   5.520000 786.870000 (796.666829)
Search space exhausted.
Tested 10000 of 10000 codes in 28614 keystrokes.
435 codes were tested more than once.


 ### 5 digits, [1,2,3] stops ###
      user     system      total        real
seq.    11.010000   0.140000  11.150000 ( 11.248501)
Search space exhausted.
Tested 100000 of 100000 codes in 600000 keystrokes.
69494 codes were tested more than once.

seq/chk  7.450000   0.060000   7.510000 (  7.563379)
Search space exhausted.
Tested 100000 of 100000 codes in 371028 keystrokes.
30902 codes were tested more than once.

simple 136.960000   6.250000 143.210000 (145.916674)
Search space exhausted.
Tested 100000 of 100000 codes in 371394 keystrokes.
31105 codes were tested more than once.

best     (not tested)


--=-mInLvOB6Mci9vowW5PV7
Content-Disposition: attachment; filename=bne.rb
Content-Type: text/plain; name=bne.rb; charset=utf-8
Content-Transfer-Encoding: 7bit

require 'quiz'
require 'benchmark'

# Make our codes. Using random stop digits gives a more
# compressible string.
def mkpool(digits, stops)
  (("0" * digits)..("9" * digits)).map do |e| 
    "#{e}#{stops[rand(stops.length)]}"
  end
end

# A really simple, yet surprisingly effective way to do it.
def simple_code(digits, stops = [1,2,3])
  mkpool(digits, stops).inject("") do |s,e| 
    s =~ /#{e[0..-2]}[#{stops}]/ ? s : s << e 
  end
end

# Just gets suffixes up to a certain length. Used for 
# prefixes to (reverse in then reverse each out).
def suffixes(str, maxlen = nil)
  start = maxlen ? str.length-maxlen : 1
  (start..(str.length-1)).map do |i| 
    suf = str[i..-1]
    suf
  end
end

# A more involved way, a variation on the greedy heuristic (I think)
# that takes _forever_ but gives (slightly) better results.
def best_code(digits, stops = [1,2,3])
  out = ""
  pool = mkpool(digits, stops)

  # build a hash with each of the valid prefixes for a given
  # code. These are matched with valid suffixes of 'out' on
  # each iteration to find the most mergeable code (i.e.
  # the one that shares most of it's prefix with the end of
  # the output string).
  #
  # Note it's digits, not digits - 1, since we have to 
  # account for the stop digit.
  prefhash = pool.inject({}) do |hsh, code|
    hsh[code] = suffixes(code.reverse, digits).map { |s| s.reverse! }
    hsh
  end

  # Keep going until it's empty - if ever we can't find a match 
  # we'll just take one at random.
  until pool.empty?
    if out.empty?
      # first iteration, just grab a start and carry on
      bestcode = pool.first
      pool.delete(bestcode)
      prefhash.delete(bestcode)
      out << bestcode
      next
    end

    # figure out the suffixes we have (i.e. prefixes we can accept) for 
    # this iteration.
    need = suffixes(out,digits)

    # Build up an array of arrays, containing at a given index all
    # the codes that share that many letters of pre/suffix with
    # 'need'. Eh? Well, it's like this:
    #
    #   "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].
    best = pool.inject([]) do |best, code|
      prefs = prefhash[code].dup

      # arrays are always same length
      if r = need.detect { |s| prefs.shift == s }
        (best[r.length] ||= []) << code
      end

      best
    end

    # Find (one of) our best scoring code(s)
    bestscore = best.length-1
    bestcode = (best[bestscore] || []).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
    
    # Chop off matched prefix from this code
    merged = bestcode[bestscore..-1]

    # Remove from our pool and prefix hash to ensure it isn't reused
    pool.delete(bestcode)
    prefhash.delete(bestcode)
      
    out << merged 
  end
  out
end

[2,3,4,5].each do |n|
  puts "\n "
  puts " ### #{n} digits, [1,2,3] stops ### "
  Benchmark.bm do |x|
    a = AlarmKeypad.new(n)
    x.report('seq.   ') do
      mkpool(n,[1,2,3]).join.split(//).each { |c| a.press c.to_i } 
    end
    a.summarize

    puts 
    
    a = AlarmKeypad.new(n)
    x.report('seq/chk') do
      mkpool(n,[1,2,3]).each do |c|
        next if a.tested?(c[0..-2].to_i)
        c.split(//).each { |d| a.press d.to_i }
      end
    end
    a.summarize

    puts
    
    a = AlarmKeypad.new(n)
    x.report('simple ') do
      simple_code(n).split(//).each { |c| a.press c.to_i } 
    end
    a.summarize

    puts
    
    if n < 5
      a = AlarmKeypad.new(n)
      x.report('best   ') do 
        best_code(n).split(//).each { |c| a.press c.to_i } 
      end
      a.summarize
    else
      puts 'best     (not tested)'
    end
  end
end



--=-mInLvOB6Mci9vowW5PV7--