Wow....it's been too long since I've posted to this list.
Anyway, we can treat each type of candle as a digit of a number in an arbitrarily-large base. We can thus interpret the total number of candles as a single number, and each possible combination of different types of candles as other numbers whose only digits are 0 and 1 in that base. Under some permutation of the digits, we are trying to add the integers representing these combinations in a way that gets us the closest to the integer representing the total number of candles.
Could use a little more rigor, but I think the above makes it pretty clear: this is essentially the Knapsack Problem. Good luck improving significantly on brute-force!
···
________________________________
From: Matthew Moss <matt@moss.name>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Friday, December 12, 2008 12:36:55 PM
Subject: [QUIZ] Mix and Match (#186)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
The three rules of Ruby Quiz 2:
1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.
2. Support Ruby Quiz 2 by submitting ideas as often as you can!
Visit <http://splatbang.com/rubyquiz/>.
3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
## Mix and Match (#186)
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.