Class: ComboFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/minitest/find_minimal_combination.rb

Instance Method Summary collapse

Instance Method Details

#cache_result(result, data, cache) ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/minitest/find_minimal_combination.rb', line 86

def cache_result result, data, cache
  cache[data] = true

  return result if result

  unless result or data.size > 128 then
    max = data.size
    subdiv = 2
    until subdiv >= max do
      data.each_slice(max / subdiv) do |sub_data|
        cache[sub_data] = true
      end
      subdiv *= 2
    end
  end

  result
end

#d(s = "") ⇒ Object 



82
83
84
 
# File 'lib/minitest/find_minimal_combination.rb', line 82

def d s = ""
  warn s if ENV["MTB_DEBUG"]
end

#find_minimal_combination(ary) ⇒ Object

Find the minimal combination of a collection of items that satisfy test.

If you think of the collection as a binary tree, this algorithm does a breadth first search of the combinations that satisfy test. –

level   collection

0          A
1      B       C
2    D   E   F   G
3   1 2 3 4 5 6 7 8

This assumes that A has already been tested and you’re now trying to reduce the match. Starting at level 1, test B & C separately. If either test positive, reduce the search space accordingly. If not, step down to level 2 and search w/ finer granularity (ie, DF, DG, EF–DE and FG were already tested as B & C). Repeat until a minimal combination is found.



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/minitest/find_minimal_combination.rb', line 27

def find_minimal_combination ary
  level, n_combos = 1, 1
  seen = {}

  d "Total number of culprits: #{ary.size}"

  loop do
    size = 2 ** (Math.log(ary.size) / Math.log(2)).round
    divs = 2 ** level
    done = divs >= size
    divs = size if done

    subsections = ary.each_slice(size/divs).to_a.combination(n_combos)

    d
    d "# new round!"
    d "#   of subsections in this round: #{subsections.to_a.size}"
    d

    found = subsections.find { |a|
      b = a.flatten

      next if seen[b]

      d "#   trying #{b.size} at level #{level} / combo #{n_combos}"
      cache_result yield(b), b, seen
    }

    if found then
      ary = found.flatten
      break if done

      seen.delete ary

      d "#   FOUND!"
      d "#     search space size = #{ary.size}"
      d "#     resetting level and n_combos to 1"

      level = n_combos = 1
    else
      if done then
        n_combos += 1
        d "#   increasing n_combos to #{n_combos}"
        break if n_combos > size
      else
        level += 1
        n_combos = level
        d "#   setting level to #{level} and n_combos to #{n_combos}"
      end
    end
  end

  ary
end