Class: ComboFinder

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

Overview

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

Instance Method Summary collapse

Instance Method Details

#cache_result(result, data, cache) ⇒ Object

:nodoc:



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

def cache_result result, data, cache # :nodoc:
  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

:nodoc:



85
86
87
 
# File 'lib/minitest/find_minimal_combination.rb', line 85

def d s = "" # :nodoc:
  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.



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
81
82
83
 
# File 'lib/minitest/find_minimal_combination.rb', line 30

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