Solved another Ruby Quiz:

I purchased a number of scented candles recently for sending out to friends and family. While I could be accused of being lazy by getting candles for several people, I’d like to mix up the candles a bit so that each recipient gets a different combination of scents. Please help me out! Your task is to write a method that randomizes and mixes up the individual candles into groups, one per recipient, in order to minimize group duplication. So, for example:

candles = { :orange   => 3,
            :vanilla  => 2,
            :lavender => 2,
            :garden   => 4 }

recipients = %w(janet nancy susan)

candles_per_recipient = 3

mix_and_match(candles, recipients, candles_per_recipient)

=> { "janet" => [:garden, :lavender, :orange],
     "nancy" => [:garden, :orange, :vanilla],
     "susan" => [:garden, :lavender, :vanilla],
     :extra  => { :orange   => 1,
                  :vanilla  => 0,
                  :lavender => 0,
                  :garden   => 1
                 }
    }

If it is impossible to have a unique combination for every recipient, you should still generate some set of combinations, minimizing repetition of combinations. If the number of recipients times the number of candles per recipient is more than the supply, generate an error.

Proposed solution: (for the impatient, the source code is here.) In my interpretation, this is a simple combinatorial problem: say the number of recipients is r and candles_per_recipient is c, then you are looking for a (preferably non-repeating) random selection of r elements of c-combinations of the original set of candles. (In fact it’s a bit more complicated than that: the c-combinations have to be recalculated from the remaining candles each time you give away a group of candles, so we’ll get to that). Sounds confusing? Don’t worry, after the implementation everything will be clear!

So first, define a k-combination for a histogram (a Hash like candles above, where keys are elements and values are cardinalities):

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

e.g.:

candles = { :orange   => 2,
            :vanilla  => 1,
            :lavender => 1, 
            :garden => 1 }

pp candles.comb(3)

=> [[:lavender, :garden, :orange],
    [:lavender, :garden, :vanilla],
    [:lavender, :orange, :orange],
    [:lavender, :orange, :vanilla],
    [:garden, :orange, :orange],
    [:garden, :orange, :vanilla],
    [:orange, :orange, :vanilla]]

so for a set of candles, this method generates all possible 3-combinations of the candles. We can then pick one and assign it to one of the recipients. Then recalculate the above from the remaining candles, give it to the next recipient - and so on and so forth. That’s the basic idea, but we also need to ensure the candle combinations are as non-repeating as possible. So let’s define some further utility methods:

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

The above code adjusts the number of candles in the original hash once we give away some of them. So for example:

candles = { :orange   => 2,
            :vanilla  => 1,
            :lavender => 1, 
            :garden => 1 }

candles.remove_set([:orange,:orange,:lavender])
p candles
=> {:lavender=>0, :garden=>1, :orange=>0, :vanilla=>1}

and some Array extensions:

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

Array#rand is trying to pick a random non-repeating combination if there is one (so e.g. [:orange, :lavender, :garden]) or, if there is no such combination, then just a random one (e.g. [:orange, :orange, :garden] - orange is repeating, but we have no other choice).

Array#unordered_include? is like normal Array#include?, but disregards the ordering of the elements. So for example:

  [[:lavender, :garden, :orange]].include? [:lavender, :orange, :garden] => false
  [[:lavender, :garden, :orange]].unordered_include? [:lavender, :orange, :garden] => true

Hmm… it would have been much more effective to use a set here rather than the above CPU-sucker, but now I am lazy to change it

OK, so finally for the solution:

ERROR_STRING = "The number of recipients times the number of candles per recipient is more than the supply!"

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
    end
    candles.remove_set(tried.last)
    a[v] = tried.last
    a  
  end
  candle_set.merge({:extra => candles})
end

So, in the inner loop we randomly pick a candles-per-recipient-combination of all the possible combinations; If no one has that combo yet, we assign it to the next recipient. If someone has it already, we try to find an unique combination (loop on), unless it is impossible (checked on line #12). In this case we simply start giving out any combinations. Once we give away a set of candles, we remove them from the original set. Easy-peasy.

You can check out the source code here.

This was a great quiz, too bad that not many people took a stab at it (so far 1 except me ;-)). The hardest part for me was the implementation of the k-combination (and the result looks awful to me - I didn’t check any algorithm/pseudocode/other solution though, I wanted to roll my own) - after that the problem was pretty simple. Cheers for the Ruby Quiz guys (== ["Matthew Moss"] I guess?) for this quiz.

If you liked the article, subscribe to the feed   and follow me on .

This entry was posted on Monday, December 15th, 2008 at 3:08 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.