Home | History | Annotate | Download | only in src 
      1 #
      2 # iExploder Combination Scanner Library (used for subtesting)
      3 #
      4 # Copyright 2010 Thomas Stromberg - All Rights Reserved.
      5 #
      6 # Licensed under the Apache License, Version 2.0 (the "License");
      7 # you may not use this file except in compliance with the License.
      8 # You may obtain a copy of the License at
      9 #
     10 #      http://www.apache.org/licenses/LICENSE-2.0
     11 #
     12 # Unless required by applicable law or agreed to in writing, software
     13 # distributed under the License is distributed on an "AS IS" BASIS,
     14 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     15 # See the License for the specific language governing permissions and
     16 # limitations under the License.
     17 
     18 
     19 # This is a simple sequential combination creator with a constantly growing width
     20 def seq_combo_creator(total_lines, width, offset)
     21   # Offsets start at 0 to total_lines-1
     22   use_lines = []
     23   offset.upto(offset+width-1) do |line_number|
     24     use_lines << line_number
     25   end
     26 
     27   if use_lines[-1] == total_lines-1
     28     width += 1
     29     next_offset = 0
     30   else
     31     next_offset = offset + 1
     32   end
     33   return [width, next_offset, use_lines]
     34 end
     35 
     36 # This tries all combinations, giving a small test-case, but requires lots of
     37 # subtests.
     38 def combine_combo_creator(total_lines, width, offsets)
     39   #  puts "Asked: Total Lines: #{total_lines} Line Count: #{width} Offsets: #{offsets.join(',')}"
     40   if not offsets or offsets.length == 0
     41     #    puts "  Setting offsets to 0"
     42     offsets = [0,]
     43   end
     44   if width < 1
     45     width = 1
     46   end
     47 
     48   index = 0
     49   lines = []
     50   new_offsets = []
     51   reset_next_offset = false
     52 
     53   # Reverse the order from fastest to slowest
     54   offsets.each_with_index do |offset, index|
     55     0.upto(width-1) do |line_offset|
     56       lines << (offset + line_offset)
     57     end
     58     if lines[-1] >= total_lines - 1
     59       # If we are the slowest, that means we are done with this iteration.
     60       if index == offsets.length - 1
     61         new_offset_count = offsets.length + 1
     62         # Loosely follow the Fibonacci sequence when calculating width
     63         width = (new_offset_count * 1.61803398).round
     64         new_offsets = []
     65         # 0 to offsets.length creates one additional offset
     66         0.upto(offsets.length) do |new_offset_num|
     67           new_offsets << (new_offset_num * width)
     68         end
     69 
     70         # We need the lowest offset first. Oops.
     71         new_offsets.reverse!
     72       else
     73         # Move to the next available slot.. next offset will take the one before.
     74         new_offsets << offsets[index+1] + (width * 2)
     75         reset_next_offset = true
     76       end
     77     elsif reset_next_offset
     78       new_offsets << (offset + width)
     79       reset_next_offset = false
     80       # The first one always rotates
     81     elsif index == 0
     82       new_offsets << (offset + width)
     83       reset_next_offset = false
     84       # The others stay still normally.
     85     else
     86       new_offsets << offset
     87       reset_next_offset = false
     88     end
     89   end
     90 
     91   return [width, new_offsets, lines]
     92 end
     93 
     94 def avg(list)
     95   sum = list.inject(0.0) { |sum, el| sum += el }
     96   return sum / list.length
     97 end
     98 
     99 
    100 # for testing #################################################################
    101 if $0 == __FILE__
    102   line_count = ARGV[0].to_i || 100
    103   try_count = ARGV[1].to_i || 10
    104 
    105   seq_iterations = []
    106   combine_iterations = []
    107   seq_size = []
    108   combine_size = []
    109 
    110   1.upto(try_count) do |run|
    111     puts "*" * 78
    112     puts "# RUN #{run} (line-count: #{line_count})"
    113     find_lines = []
    114     0.upto(rand(4)) do |count|
    115       choice = rand(line_count).to_i
    116       if ! find_lines.include?(choice)
    117         find_lines << choice
    118       end
    119     end
    120 
    121     lines = []
    122     width = 1
    123     offset = 0
    124     attempts = 0
    125     puts "Find lines: #{find_lines.join(',')}"
    126     while not find_lines.all? { |x| lines.include?(x) }
    127      (width, offset, lines) = seq_combo_creator(line_count, width, offset)
    128       attempts += 1
    129     end
    130     puts "Sequential found #{find_lines.join(',')} in #{attempts} attempts with #{lines.length} total lines."
    131     seq_iterations << attempts
    132     seq_size << lines.length
    133 
    134     lines = []
    135     width = 1
    136     offsets = []
    137     attempts = 0
    138     while not find_lines.all? { |x| lines.include?(x) }
    139       #    puts "Looking for #{find_lines.join(',')}"
    140        (width, offsets, lines) = combine_combo_creator(line_count, width, offsets)
    141       attempts += 1
    142     end
    143     puts "Combine found #{find_lines.join(',')} in #{attempts} attempts with #{lines.length} total lines."
    144     combine_iterations << attempts
    145     combine_size << lines.length
    146   end
    147   puts "-" * 78
    148   puts "Seq avg iterations=#{avg(seq_iterations).to_i} length=#{avg(seq_size).to_i}"
    149   puts "combine avg iterations=#{avg(combine_iterations).to_i} length=#{avg(combine_size).to_i}"
    150   diff_iter = (avg(combine_iterations) / avg(seq_iterations)) * 100
    151   diff_lines = (avg(combine_size) / avg(seq_size)) * 100
    152   puts "Diff iterations: #{diff_iter}%"
    153   puts "Diff lines: #{diff_lines}%"
    154 end
    155