--MqfJFMwaRdW3xqXyF+9
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

On Tue, 2006-03-28 at 01:18 +0900, Ross Bamford wrote:
> Hmm, this is a tricky one :) This solution is pretty ugly (I've not
> seriously tried to clean it up, either) and slow.

Probably a bit late on (sorry) but this is a cleaned up version that
does much the same and is marginally quicker.

-- 
Ross Bamford - rosco / roscopeco.REMOVE.co.uk

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

require 'quiz'
require 'benchmark'

EMPTYARRAY  ]

# This was originally a delegator, but that was *slow*
class PoolStr < String
  def initialize(obj, parent  il)
    super(obj)
    @parent  arent
  end
  def suffixes(maxlen  il)
    @suffixes || et_suffixes(maxlen).map do |s|
      PoolStr.new(s,self)
    end
  end
  def prefixes(maxlen  il)
    @prefixes || et_suffixes(maxlen,reverse).map do |s|
      PoolStr.new(s.reverse,self)
    end
  end
  private
  def get_suffixes(maxlen  il, str  elf)
    start  axlen ? str.length-maxlen : 1
    (start..(str.length-1)).map do |i| 
      suf  tr[i..-1]
      suf
    end
  end
end

# Make our codes. Using random stop digits gives a more
# compressible string (less stop digits  onger 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

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

# A more involved way, a simplified greedy heuristic
# that takes _forever_ but gives (slightly) better results.
def best_code(digits, stops  1,2,3])
  out  "
  pool  kpool(digits, stops)
  best  ]
  bestcode  il
  
  # 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  
      bestcode  ool[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  est.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  
        bestcode  ool[rand(pool.length)]
      end
    end

    # Remove from the pool. Bit slow...
    pool[pool.index(bestcode),1]  il
    
    # Chop off matched prefix from this code and append it
    merged  estcode[bestscore..-1]
    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  larmKeypad.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  larmKeypad.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  larmKeypad.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  larmKeypad.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



--MqfJFMwaRdW3xqXyF+9
Content-Disposition: attachment; filename=testrun.txt
Content-Type: text/plain; name=testrun.txt; charset=utf-8
Content-Transfer-Encoding: 7bit


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

seq/chk  0.000000   0.000000   0.000000 (  0.008248)
Search space exhausted.
Tested 100 of 100 codes in 249 keystrokes.
19 codes were tested more than once.

simple   0.010000   0.000000   0.010000 (  0.005738)
Search space exhausted.
Tested 100 of 100 codes in 240 keystrokes.
14 codes were tested more than once.

best     0.050000   0.010000   0.060000 (  0.055791)
Search space exhausted.
Tested 100 of 100 codes in 226 keystrokes.
6 codes were tested more than once.

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

seq/chk  0.070000   0.000000   0.070000 (  0.071199)
Search space exhausted.
Tested 1000 of 1000 codes in 2952 keystrokes.
214 codes were tested more than once.

simple   0.080000   0.000000   0.080000 (  0.090018)
Search space exhausted.
Tested 1000 of 1000 codes in 2972 keystrokes.
235 codes were tested more than once.

best     6.140000   0.040000   6.180000 (  6.231027)
Search space exhausted.
Tested 1000 of 1000 codes in 2618 keystrokes.
51 codes were tested more than once.

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

 
 ### 5 digits, [1,2,3] stops ### 
      user     system      total        real
seq.    19.250000   0.190000  19.440000 ( 19.886016)
Search space exhausted.
Tested 100000 of 100000 codes in 600000 keystrokes.
69421 codes were tested more than once.

seq/chk 11.990000   0.170000  12.160000 ( 12.259832)
Search space exhausted.
Tested 100000 of 100000 codes in 371178 keystrokes.
30985 codes were tested more than once.

simple 316.390000   5.580000 321.970000 (325.342727)
Search space exhausted.
Tested 100000 of 100000 codes in 372144 keystrokes.
31125 codes were tested more than once.

best     (not tested)

--MqfJFMwaRdW3xqXyF+9--