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.

Similar Posts:cheap xanax

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.