Splitting the Loot (#65)

Subset Sum and Partition problem are similar, I agree that this quiz
is closer to a Partition problem. However, if we consider the Subset
Sum problem: given a set of integers and an integer k, find a subset
whose sum is k? We can apply a subset sum algorithm to find the
possible subset that sums to the fair share for the first “pirate”,
and then work in the same way on the remaining elements for the other
pirates.

Not without backtracking… suppose you have the treasures [1 2 3 4 5 6]
to be split among three pirates. If the subset sum algorithm finds the
treasures [1 2 4] for the first pirate it is impossible to divide the
remaining treasures [3 5 6] among the remaining two pirates even though
there exists a valid solution [1 6] [2 5] [3 4].

// Niklas

On Mon, 06 Feb 2006 06:16:39 -0000, Patrick D. [email protected]
wrote:

It is the subset sum problem. Read the description on the site:

“An equivalent problem is this: given a set of integers and an integer
/s/, does any subset sum to /s/? Subset sum can also be thought of as a
special case of the knapsack problem
http://en.wikipedia.org/wiki/Knapsack_problem.”

I’ve solved this problem before, so I’m sure it’s the subset sum problem.

(Total non-mathematician about to butt in)

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.

I think it gets problematic at that last step, because I think it’s
possible for the first guy to take a combination that makes sure the
second guy can’t be satisfied, while if the first guy had taken a
different combination (say, a 2 instead of two 1s) then guy two (needing
a

  1. could have been satisfied. Maybe sorting the treasure would fix that
    but I can’t be certain.

Maybe not a good plan but it’d have been interesting to see if it
worked…

Chris Parker wrote:

Here is my solution. It is short and simple. I take advantage of the
fact that for there to be an answer, every treasure must be used, so a
greedy algorithm that tries the highest valued treasures first works
well.

Unfortunately there are cases where the greedy algorithm fails. Try
this set of arguments:

3 3 3 3 2 2 2 2 2 2 2 2 2

The correct answer is:

1: 3 2 2 2
2: 3 2 2 2
3: 3 2 2 2

But the greedy algorithm get stuck at:

1: 3 3 3

Cheers,
Avi

=begin
my solution was inspired by a lecture about scheme/lisp streams. the
possible-solution space is searched in a quite stupid manner which
makes it kind of slow… :slight_smile:
=end

require ‘lazylist’

pirates = ARGV.shift.to_i
loot = ARGV.map {|x| x.to_i}

this computes all solutions (but does so lazyly)

also this doesn’t check for equivalent solutions, but we don’t care

since only the first solution is computed and printed

LazyList[1 … pirates**loot.size].map {|owners|
# owners encodes a way to give each pirate a subset of the loot
# (as a number of base “pirates”)
bags = Array.new(pirates) {[]}
idx = loot.size - 1
begin
owners, owner = owners.divmod(pirates)
bags[owner] << loot[idx]
idx -= 1
end while owners > 0
idx.downto(0) do |i|
bags[0] << loot[i]
end
bags
}.map {|splitting|
# now map to the sums
puts “computed sums for #{splitting.inspect}”
[splitting, splitting.map {|pieces| pieces.inject(0) {|s,p| s +
p}}]
}.select {|splitting, sums|
# are all sums the same?
sums.uniq.length == 1
}.map {|splitting, sums|
# forget the sums
splitting
}.take.each {|splitting|
# take the first solution and just output it
splitting.each_with_index {|pieces, owner|
puts " #{owner+1}: #{pieces.sort.join(" “)}”
}
}

Dave H. [email protected] writes:

On Feb 5, 2006, at 8:53, Manuel K. wrote:

def initialize pirates, treasure

I’ll just note that the original posting never said anything about
pirates. :slight_smile:

But pirates are the chosen ones!

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

  • 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 G. 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

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

Matthew M. wrote:

My solution… very simple, recursive, no optimizations…

Hello.
Well, your solution doesn’t split [34 78 21 70 45 67 70 19 90 76 54 20
30 19 80 7 65 43 56 46] 6-ways. The problem is that you can find a
combination of gems that sum up to the correct value, but make it
impossible to complete the split, whereas if you had chosen another
combination, the split would have been possible.

Manuel

[email protected] $ ruby Matthew\ Moss.rb 6 34 78 21 70 45 67 70 19 90 76
54 20 30 19 80 7 65 43 56 46

It is not possible to fairly split this treasure 6 ways.

Luke B. wrote:

It is the subset sum problem. Read the description on the site:
not NP-complete, it is this partitioning that makes this problem hard.

Seems to me that this is a variant of a bin-packing problem with no
allowance for leftover space.

Luke B.

Yes, you’re right.
I realized that a few days ago and recoded my solution, because my first
one did just solve a simple subset problem and not the problem you
explained. :slight_smile:

Patrick

Patrick D. wrote:

Luke B. wrote:

Patrick D. wrote:


The splitting the loot problem is actually a problem known as the
“Knapsack problem” or the “Subset sum problem”.
http://en.wikipedia.org/wiki/Subset_sum_problem
I don’t believe that this problem is equivalent to the subset sum
problem, because all of the numbers involved are positive. Different
animal.
It is the subset sum problem. Read the description on the site:
Why yes, I did read it, thank you very much. And of course you’re
correct that it bears a strong resemblance to subset sum, and indeed
overlaps a special case of it. However, I still say it’s a different
animal, for two reasons:

  1. The special case it overlaps with is not NP-complete. If you have
    all positive numbers, you can find a subset sum in O(n^2).

  2. You aren’t just finding a single subset. You are partitioning the
    set into a collection of equal subsets. And since the special case is
    not NP-complete, it is this partitioning that makes this problem hard.

Seems to me that this is a variant of a bin-packing problem with no
allowance for leftover space.

Luke B.

On 2/7/06, Manuel K. [email protected] wrote:

Matthew M. wrote:

My solution… very simple, recursive, no optimizations…

Hello.
Well, your solution doesn’t split [34 78 21 70 45 67 70 19 90 76 54 20
30 19 80 7 65 43 56 46] 6-ways. The problem is that you can find a
combination of gems that sum up to the correct value, but make it
impossible to complete the split, whereas if you had chosen another
combination, the split would have been possible.

Yup, yer right, I noticed that couple of days ago, but I haven’t had a
chance yet to make it work right. Maybe later today…

Chris Parker wrote:

Here is my solution. It is short and simple. I take advantage of the
fact that for there to be an answer, every treasure must be used, so a
greedy algorithm that tries the highest valued treasures first works
well.

Hi.

It doesn’t split

72, 49, 83, 74, 65, 81, 92, 27, 58, 12, 97, 5, 8, 1, 38, 73, 6, 13, 29,
36, 83, 65, 95, 96, 89, 55, 43, 91

8-ways

nor

62, 93, 97, 85, 31, 2, 80, 83, 76, 54, 71, 70, 74, 42, 79, 7, 14, 66, 7,
100, 88, 68, 37, 99, 47, 51, 66, 23, 80

8-ways

Manuel K.

Here is my solution.

It first sorts the gems by value and then, tries to split them
recursively. The sorting is not necessary for split_loot to work, but it
works much faster on sorted sets.

If only a number of adventurers and no loot is given, then a random loot
is generated.

Dominik

def split_loot(cnt, gems, first_call = true)
return [gems] if cnt == 1
sum = gems.inject(0) { |s, n| s + n }
share = sum / cnt
if first_call
# only do these checks once
if sum % share != 0 || gems.max > share || gems.empty?
raise “impossible”
end
end

search all subsets of the gems whose sum is share, for each try to

split the remaining loot into cnt - 1 parts

choose_stack = [0]
share_sum = gems.first
last = gems.size - 1
until choose_stack.empty?
while share_sum < share && choose_stack.last < last
choose_stack << choose_stack.last + 1
share_sum += gems[choose_stack.last]
end
if share_sum == share
# recursive call
rest_gems = gems.values_at(*((0…gems.size).to_a -
choose_stack))
if (res = split_loot(cnt - 1, rest_gems, false) rescue nil)
return (res << gems.values_at(*choose_stack))
end
end
if choose_stack.last == last
share_sum -= gems[last]
choose_stack.pop
end
unless choose_stack.empty?
share_sum -= gems[choose_stack.last]
choose_stack << choose_stack.pop + 1
share_sum += gems[choose_stack.last]
end
end
raise “impossible”
end

if $0 == FILE
begin
if ARGV.size >= 2
cnt, *gems = ARGV.map { |s| Integer(s) }
else
# generate a test
cnt = ARGV.shift.to_i
share_sum = rand(1000)
gems = []
cnt.times {
rest = share_sum
while rest > 0
cur = rand(rest) + 1
gems << cur
rest -= cur
end
}
end
split_loot(cnt, gems.sort.reverse).each_with_index { |s, i|
puts “#{i+1}: #{s.join(’ ')}”
}
rescue => e
puts e
end
end