On Feb 6, 2006, at 3:18 AM, Ross Bamford wrote:

> I had a look at this quiz but didn't get chance to have a go, and  
> although I originally figured it'd be a subset-sum thing, I  
> realised that everyone's share will be one of the partitions of  
> (total / number of guys), right? I ported a fast partition  
> algorithm and was going to try attacking it that way but I just  
> didn't get the chance.
>
> Something like,
>
> 	+ Quit if treasure_sum % guys != 0
> 	+ each = treasure_sum / guys
> 	+ parts = partition(each)
> 	+ have each guy try to take a partition from the treasure,
> 	  removing the taken treasure.

That's pretty much how I handled it.  Mine is really just an unrolled  
recursive solution.

James Edward Gray II

#!/usr/local/bin/ruby -w

class Array
   def without( other )
     result = dup
     other.each do |value|
       i = result.index(value) or next
       result.delete_at(i)
     end
     result
   end

   def sum
     inject { |sum, value| sum + value }
   end
end

def find_shares( target, treasures )
   shares = target.zero? ? [[target, Array.new, Array.new]] :
                           [[target, treasures.dup, Array.new]]

   until shares.empty?
     goal, pool, share = shares.pop
     first             = pool.shift

     shares << [goal, pool.dup, share.dup] unless pool.empty?
     if goal == first
       yield share + [first]
     elsif goal > first and not pool.empty?
       shares << [goal - first, pool.dup, share + [first]]
     end
   end
end

def divide_loot( target, treasures )
   total = treasures.sum

   return [treasures] if total == target

   unless (total % target).nonzero?
     loot = [[treasures.dup, Array.new]]

     until loot.empty?
       rest, divided = loot.pop

       find_shares(target, rest) do |share|
         new_rest  = rest.without(share)
         new_total = new_rest.sum

         if new_total == target
           return divided + [share, new_rest]
         elsif (new_total % target).zero?
           loot << [new_rest, divided.dup << share]
         end
       end
     end
   end

   nil
end

unless ARGV.size >= 2
   puts "Usage:  #{File.basename($PROGRAM_NAME)} ADVENTURERS TREASURES"
   exit
end
adventurers, *treasures = ARGV.map { |n| n.to_i }
target                  = treasures.sum / adventurers

if loot = divide_loot(target, treasures)
   loot.each_with_index do |share, index|
     puts "#{index + 1}: #{share.join(' ')}"
   end
else
   puts "It is not possible to fairly split this treasure # 
{adventurers} ways."
end