Forum: Ruby Mix and Match (#186)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-12-12 19:44
(Received via mailing list)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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.
2922715cbee99df9b47619992cf5c9ae?d=identicon&s=25 James Koppel (Guest)
on 2008-12-16 19:19
(Received via mailing list)
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.
2922715cbee99df9b47619992cf5c9ae?d=identicon&s=25 James Koppel (Guest)
on 2008-12-17 02:04
(Received via mailing list)
Wow, it's been a long time since I've posted to this list.

Anyway, we can treat the candles of each type as a digit in an integer
in an arbitrarily-high base. Applying that transformation, the problem
becomes "Given several numbers, find a way to add them up so that each
digit is as close as possible to a given number." Not sure how to
rigorously prove it, but that's highly suggesting that this quiz is
reducible to the Knapsack Problem.




________________________________
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.
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-12-19 00:18
(Received via mailing list)
_This week's summary is provided by Peter, originally [posted to his
blog][1]. I am providing it here with permission._

[1]: http://www.rubyrailways.com/ruby-quiz-mix-and-match/


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

For example:

     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 (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.
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.
This topic is locked and can not be replied to.