You, and your trusty band of adventurers, have stumbled upon a hidden cache of rubies! (What luck, eh?) Not all gems are created equal, so you sneak them home and take your time evaluating the stones. The find was an equal effort, and you're all horribly greedy, so you must find a fair system for dividing up the gems.
This week's Ruby Quiz is to write a program that fairly divides treasures, based on worth.
The first command-line argument to the program will be the number of adventures. All other arguments are the numerical values of treasures found. You're program should output a fair split of the treasures, if possible, or a warning message if a fair split cannot be found.
Examples:
$ ruby loot.rb 3 1 2 3 4
It is not possible to fairly split this treasure 3 ways.
$ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
1: 9 12 32 34 49
2: 14 17 23 40 42
Quiz Summary
There was some debate on the list about which NP-complete problem this actually is. I personally thought it was a variant of the partitioning problem when I put it together, but others made good cases for similar problems. In the end, two things are important: it's difficult and tricky to get right. :)
Some people thought you could work with the treasures largest to smallest to save time. A few edge cases were pointed out for this approach though. The easiest example to understand being this one posted by Avi Bryant:
$ ruby loot.rb 3 3 3 3 2 2 2 2 2 2 2 2 2
1: 3 2 2 2
2: 3 2 2 2
3: 3 2 2 2
Here we are looking for totals of nine. If we work only with the big values, we will find 3 3 3 as an option, but then it is impossible to break the remaining even numbers into totals of nine. For this reason, you must consider all of the possibilities.
Manuel Kasten posted many of the edge cases that solutions had trouble with, in addition to the first solution that seems to be able to find them all. Let's look at that code now, from the bottom up:
if $0 == __FILE__
pirates = ARGV.shift.to_i
treasure = ARGV.map{ |gem| gem.to_i }.sort
si = SplitIt.new(pirates, treasure)
si.go
si.done
end
That's the first bit of code run when Manuel's program is launched. We can see that it reads and converts arguments, builds some SplitIt object with them, and finally calls SplitIt#go and SplitIt#done.
Time to dig into SplitIt:
def initialize pirates, treasure
@pirates = pirates
@treasure = treasure
@bags = []
(0...@pirates).each{ |pirate| @bags[pirate] = [[], 0] }
loot = @treasure.inject(0){ |res, gem| res + gem }
done unless loot % @pirates == 0
@share = loot/@pirates
end
# ...
The only remotely tricky thing in here is the creation of @bags. Each pirate is given a two-element Array. The first element is another Array, which will be filled with the gems placed in their share. The second element is just the total of their share thus far.
Also note that this method may immediately force a call to SplitIt#done, if the treasure does not evenly divide. Let's skip down to done now:
def done
puts
if (@treasure.length == 0)
@bags.each_with_index do |bag, pirate|
puts "#{pirate+1}: #{bag[0].sort.inspect}"
end
else
puts "The #{@pirates} pirates won't be able to " +
"split their loot fairly. Take cover!"
end
exit
end
end
This method just shows the final results. If all the treasure is gone, we split it up correctly and the shares are printed. Otherwise, we give the error message. Either way Kernel#exit is called, because we're all finished.
That leaves only one method to examine:
def go
done if @treasure.length == 0
gem = @treasure.pop
(0...@pirates).each do |pirate|
if @bags[pirate][1] + gem <= @share
@bags[pirate][1] += gem
@bags[pirate][0].push gem
go
@bags[pirate][0].pop
@bags[pirate][1] -= gem
# it doesn't matter which pirate is which,
# as long as their bags are empty
break if @bags[pirate][1] == 0
end
end
@treasure.push gem
end
# ...
This method does all the work, with a brute-force recursive search. A gem is pulled off the pile here and tried in each pirate's bag. After it is placed in a bag, the method recurses to try the remaining treasures.
If a recursive call returns, there was no split found (because SplitIt#done would have been called if there was). Since that is the case, the treasure is pulled back out of the bags and replaced on the pile.
The break line is just a minor optimization. If a treasure didn't work in one pirate's empty bag, it won't work in any of the empty bags following his and we can skip those checks.
Since that is an exhaustive search, it will find a correct split eventually, as long as one exists. Let's look at another variation of the same technique, this time by Simon Kroeger:
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!')
Here again, we see the treasures are converted from the command-line arguments and this time they are sent to #split_loot. The first line of #split_loot sums the treasures, and places the share total needed in a variable called each. The second line just cancels the search if the total sum is not easily divided.
The next bit of Hash manipulation is the magic here. Each treasure is pulled off the pile and combined with all other totals as long as the resulting total will be less than or equal to the share goal and it will leave us enough treasures to reach that goal.
How they are stored in the Hash is interesting. The keys are sums of shares found thus far. The values for those sums are an Array of the shares that can make that sum (another Array). The individual items in the shares are indexes into the treasure pile, instead of the treasures themselves. For example, if I feed Simon's program the problem 2 3 2 1, the piles Hash ends up as:
{ 0 => [ [] ],
2 => [ [1] ],
3 => [ [0], [1, 2] ] }
The 0 empty set split is what the code primes the Hash with, so it has something to add to. The other two are totals it calculated. Higher totals weren't figured because they aren't needed. And remember 0, 1, and 2 inside those sets refer to indexes of treasures.
I want to mention one more gotcha in this code, before we move on. Note that the default Hash object is set to an Array. Usually you want to avoid doing that without the block form of Hash#new, because you will get the same Array each time. However, whenever this code calls it up, it is to add it to another Array, which returns a third Array (the combined results) that actually gets stored in the Hash.
The rest of #split_loot makes sure a solution is still possible, tries to divide it out with a call to #choose_bags, and finally translates all those treasure indexes back to actual gems. (Note that Simon's use of these unique indexes, saved him the trouble of pulling non-unique elements from an Array one-at-a-time that was a discussion topic spawned by this problem.)
That leaves the only mystery as #choose_bags. Here's another look at that code:
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
# ...
This method obviously uses the Set library to do its work. Here each bag is tried one by one and checked that it doesn't contain any already-used elements. That check is accomplished with a set intersection (&) test. If clear, the method recurses to find the other bags, after performing a set union (|) with the selected bag and all bags chosen thus far.
When the first line of the method informs us that we have used all of the treasures, we can start passing the results back up the callstack. The result set starts as an empty Array, but each level adds in the bag used, again by index of the bag. If we take one more peek at the final line of #split_loot, we will see that those bag indexes are resolved with a call to Array#values_at, just before the results are returned:
piles[each].values_at(*bags).map{|b| b.map{|t| treasures[t]}}
end
# ...
Finally, one last trick is worth mentioning in #choose_bags. There is a funny ... && nil on the last line. The reason is that Enumerable#each_with_index always returns a true value, but this method needs a false result if a bag could not be added. You can get that by &&ing any true value with nil, or Simon could have just returned a nil at the end of the method for identical results.
As usual, all solutions were educational. My thanks to all for the code and excellent discussion this time around.
Tomorrow we will begin a run of at least three non-NP-complete problems by myself and others...
