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
20def 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]
34end
35
36# This tries all combinations, giving a small test-case, but requires lots of
37# subtests.
38def 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]
92end
93
94def avg(list)
95  sum = list.inject(0.0) { |sum, el| sum += el }
96  return sum / list.length
97end
98
99
100# for testing #################################################################
101if $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}%"
154end
155