1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Array 
  def rand 
    uniqs = self.select{|e| e.uniq.size == e.size}
    uniqs.empty? ? self[Kernel.rand(length)] : uniqs[Kernel.rand(uniqs.length)]
  end

  def unordered_include?(other)
    self.map{|e| e.map{|s| s.to_s}.sort}.include? other.map{|s| s.to_s}.sort
  end  
end

class Hash
  def comb(group_size)
    result = []    
    inner_comb = lambda do |head,tail|
      tail[0..-(group_size-head.size)].each do |e|
        if (head.size >= group_size-1)
          tail.each {|t| result << head + [t]}
        else
          inner_comb[head + [e], tail[tail.index(e)+1..-1]] 
        end
      end
    end
    inner_comb[[],self.inject([]) {|a,v| v[1].times{a <<v[0]}; a}]
    result.uniq    
  end

  def remove_set(set)
    set.each {|e| self[e] -= 1}
  end  
end

def mix_and_match(candles, recipients, candles_per_recipient)
  return ERROR_STRING if ((candles.values.inject{|a,v| a+v}) < (recipients.size * candles_per_recipient))
  candle_set = recipients.inject({}) do |a,v|
    tried = []
    tries = 0
    loop do
      random_pick = candles.comb(candles_per_recipient).rand
      tried << random_pick unless tried.unordered_include? random_pick
      break unless a.values.unordered_include? random_pick
      break if (tries+=1) > candles.values.size * 2 #not perfect, but good enough
    end
    candles.remove_set(tried.last)
    a[v] = tried.last
    a  
  end
  candle_set.merge({:extra => candles})
end