From: "Simon Kröger" <SimonKroeger@...>
Date: 2006-02-07T06:49:51+09:00
Subject: Re: [QUIZ][SOLUTION] Splitting the Loot (#65)

Hi,

this is my solution. It first creates every possible combination of gems 
that sums up to the right value in split_loot (multiplying the gems, 
hehe, the magic of ruby?). choose_bags looks for a combination of bags 
where each gem is only used once afterwards (discarding all the 
multiplied gems - oooooh). choose_bags is recursive but has to deal only 
with valid combinations of gems so i hope it is fast.

Ok, here it is:

--------------------------------------------------------------------
require 'set'

def choose_bags nr, bags, choice = Set[]
   return [] if choice.size == nr
   bags.each_with_index do |b, i|
     c = (choice & b).empty? && choose_bags(nr, bags, choice | b)
     return [i] + c if c
   end && nil
end

def split_loot  nr, *treasures
   each = (sum = treasures.sort!.reverse!.inject{|s, t| s + t}) / nr
   return nil if (sum % nr).nonzero?

   piles = Hash.new([]).merge!({0 => [[]]})
   treasures.each_with_index do |t, i|
     piles.dup.each do |k, v|
       if k + t <= each && k + sum >= each
         v.each{|a| piles[k + t] += [a + [i]]}
       end
     end
     sum -= t
   end
   return nil if piles[each].empty?
   return nil if !bags = choose_bags(treasures.size, piles[each])

   piles[each].values_at(*bags).map{|b| b.map{|t| treasures[t]}}
end

loot = split_loot(*ARGV.map{|p| p.to_i})
puts(loot ? loot.map{|a| a.join(' ')} : 'impossible!')
--------------------------------------------------------------------

cheers

Simon