[QUIZ] Splitting the Loot (#65)

[Ruby Quiz]

The three rules of Ruby Quiz:

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 by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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

 

[Luke Blanshard]

Can one assume that the treasure values are only integers?

I certainly hope so.

 

[Patrick Hurley]

I certainly hope so.

I just certainly hope there is not too many treasures, I am pretty
sure this is NP complete.

 

[Patrick Deuster]

Ok, the 48 hours passed just now and as I have to leave for a day or two
I post my solution early.

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 solved the problem how I learned it at university, by walking through
a tree.
I hand the loot and the target value over to the knapsack solver and
remove the result from the loot until either the loot is empty or
solving the problem failed.

Here's my complete solution:

class Array
def sum
inject { |s,x| s + x }
end
def delete_one! n
(i = index(n)) ? delete_at(i) : nil
end
def count n
inject(0) { |c,x| x == n ? c+1 : c }
end
end

class Knapsack
def initialize target, numbers
@target,@numbers = target, numbers
end
def solve
solver @numbers.map { |n| [n] }
end
def solver paths
new_paths = Array.new
paths.each do |path|
return path if path.sum == @target
@numbers.each do |n|
unless path.count(n)>[email protected](n) || path.sum+n > @target
new_path = path.dup
new_path << n
new_paths << new_path
return new_path if new_path.sum == @target
end
end
end
return nil if new_paths.empty?
solver new_paths
end
end

adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }
fair_split,stakes = loot.sum/adventures,Array.new

begin
stake = Knapsack.new(fair_split,loot).solve
stakes << stake
stake.each { |s| loot.delete_one!(s) } unless stake.nil?
end until stake.nil? || loot.empty?

if stakes.include?nil
puts "It is not possible to fairly split this treasure #{adventures}
ways."
else
stakes.size.times { |i| puts "#{i+1}: " + stakes.sort.join(" ") }
end

 

[James Edward Gray II]

Can one assume that the treasure values are only integers?

Yes, they are.

James Edward Gray II

 

[Luke Blanshard]

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

Luke Blanshard

 

[Manuel Kasten]

=begin ############################################################

Hello,
this is my first participation in a Ruby Quiz. I used a simple
recursive algorithm, so don't expect speed wonders from this one.
I'm sure there are faster and more elegant solutions out there.
Nevertheless, I had fun implementing this.
Oh, and I swapped the adventurers for pirates, because they gave
me a headache spelling them. (adventurerers, adventurererer.. ?)

Manuel Kasten

=end ############################################################

class 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
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
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

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

 

[soxinbox]

#booty
class Array
def sum
inject(0){|v,e| v += e.to_i}
end
end
class PileOfBooty
attr :sum
def initialize
@sum = 0
@pile = []
end
def add(i)
@sum += i.to_i
@pile << i.to_i
end
def rem
r = @pile.pop
@sum -= r
r
end
def sort!
@pile.sort!
end
end

def sumit(piles,treasure,divy)
if treasure.sum == 0
return piles
else
ruby = treasure.rem
piles.size.times{|i| #try adding the ruby to each pirate's pile in
turn
piles.add ruby #add the ruby to the this pile
if piles.sum <= divy and sumit(piles,treasure,divy) != nil
return (piles) #that worked ok, now divy up the rest of the booty
else
piles.rem #that didn't work, take the ruby back
end
}
treasure.add ruby #couldn't find a soultion from here, put the ruby
back in the booty pile and return nil
return nil
end
end
def dumpit ( piles,n )
print "\n\n"
if piles == nil
print "It bees not possible to divy the booty amongst #{n} pirates,
ARRRGH!\n"
else
piles.each_index{|i|
piles.sort!
print "#{i}:"
print " #{piles.rem}" while piles.sum != 0
print "\n"
}
end
end

n=ARGV.shift.to_i #number of pirates
treasure = PileOfBooty.new
ARGV.each{|e| treasure.add e} #collection of rubys to divy up
divy = treasure.sum/n #each pirate's share
piles = []
n.times{piles << PileOfBooty.new} #a pile of booty for each pirate
dumpit( sumit(piles,treasure,divy) ,n)

 

[Adam Shelly]

This week's Ruby Quiz is to write a program that fairly divides treasures= ,
based on worth.

Here's mine. I reused several methods from the wierd numbers quiz.

#############################################
#loot.rb
#Adam Shelly
#evenly splits an array into N parts with equal value , if possible

class Array
def sum
inject(0){|s,v| s+v}
end

def subtract arr
return clear if arr=3D=3Dself
arr.each{|e| if (n=3Dindex(e)) then delete_at(n); end }
self
end

#fast version which misses some subsets.
#useful as a rough filter.
def quick_find_subset_with_sum n
a =3D self.sort.reverse
sum,set =3D 0,[]
a.each {|e|
if (sum+e <=3D n)
sum+=3De
set<<e
return set if sum =3D=3D n
end
}
nil
end

def find_subset_with_sum n
s =3D quick_find_subset_with_sum n
return s if s
possibilities, seen =3D [self.select{|e| e<=3Dn}],{}
until possibilities.empty?
candidate =3D possibilities.pop
diff =3D candidate.sum - n
return candidate if diff =3D=3D 0
break if diff < 0
candidate.each_with_index{|e,i|
break if e > diff
new_cand =3D (candidate.dup)
new_cand.delete_at(i)
return new_cand if e =3D=3D diff
possibilities << new_cand if !seen[new_cand]
seen[new_cand]=3Dtrue
}
end
nil
end
end


# Splitter algorithm
#1: put all loot in pile 1
#2: find a share from pile 1
#3: if you can't find one, it can't be split
#4: find a share in the remaining pile
#5: repeat unitl you find all shares
#6: if you can't find enough shares
#7: move the first share to pile2
#8: repeat from step 2, but add pile2 to the remainder in step 4
# this serves to shuffle the possible combinations, until you find one
that works.


def splitter n, loot
splits=3D[]
pile1,pile2=3Dloot.dup.sort.reverse,[]
total =3D loot.sum
share =3D total/n
return nil if total%n !=3D 0 || loot.size < n || loot.max > share

until pile1.empty?
splits[0] =3D pile1.find_subset_with_sum(share)
break if !splits[0]
remaining =3D pile1.subtract(splits[0])+pile2
(1...n).each do |i|
break if nil =3D=3D (splits =3D remaining.find_subset_with_sum(sha=
re))
remaining.subtract(splits)
end
return splits if splits[n-1]
pile2 +=3D splits[0]
end
return nil
end

if __FILE__ =3D=3D $0

if ARGV.size < 2 || ARGV[0].to_i < 1
puts "Usage: #{$0} partners item1 item2 ..."
else
shares =3D splitter(ARGV.shift.to_i, ARGV.map{|a| a.to_i })
if !shares
puts "This loot can not be evenly divided into #{n} parts!"
else
shares.each_with_index{|share,i| puts "#{i}: #{share.join(' ')}"}
puts "everyone gets #{shares[0].sum}"
end
end

end


#############################################

-Adam

 

[Chris Parker]

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

class Array
def delete_one(item)
return unless include?(item)
index = nil
self.each_with_index{|elem,index|break if elem == item}
delete_at(index)
end

def delete_set(arry_to_delete)
arry_to_delete.each{|elem| self.delete_one(elem)}
end
end

def subset_sum(set, goal)
return nil if set == [] and goal != 0
return [] if goal == 0
if goal >= set[0]
ret_val = subset_sum(set[1..-1],goal - set[0])
return ret_val << set[0] if ret_val != nil
end
return subset_sum(set[1..-1],goal)
end

if ARGV.length < 2
print "Invalid arguments\n#{__FILE__} #adventurers list of booty\n"
exit
end

num_people = ARGV[0].to_i

treasures = []
ARGV[1..-1].each do |num_string|
treasures << num_string.to_i
end

total_treasure = treasures.inject(0){|sum, i| sum + i}

if total_treasure % num_people != 0 || num_people > treasures.length ||
treasures.max > total_treasure / num_people
print "impossible to split treasure equally"
exit
end

treasures = treasures.sort.reverse
num_people.times do |i|
subset = subset_sum(treasures, total_treasure / num_people)
if subset == nil
print "can't split treasure evenly\n"
exit
else
print "pirate #{i}: got #{subset.inject(""){|string, num|string
+num.to_s+" "}}\n"
end
treasures.delete_set(subset)
end

 

[Stu Glaser]

Actually, it's more closely related to the Partition problem (which is
also NP-Complete). (In fact, the 2-person instance is the Partition
problem).

Translation for the non-Computer Science: the problem cannot be solved
(exactly) without using a brute-force (slow) recursive-like algorithm.

-Stu

 

[Dave Howell]

def initialize pirates, treasure

I'll just note that the original posting never said anything about
pirates.

 

[James Edward Gray II]

I'll just note that the original posting never said anything about
pirates.

The submission message you quoted explained the change.

James Edward Gray II

 

[Matthew Moss]

My solution... very simple, recursive, no optimizations...




class Numeric
def positive?
self > 0
end
end

class Array
def tail
self[1..-1]
end

def sum
inject { |s, k| s + k }
end

def find_sum(n)
if not empty? and n.positive?
if n =3D=3D first
return [first]
else
sub =3D tail.find_sum(n - first)
return [first] + sub unless sub.nil?
return tail.find_sum(n)
end
end
nil
end
end

guys =3D ARGV.shift.to_i
loot =3D ARGV.map { |i| i.to_i }.sort

total =3D loot.sum

unless (total % guys).zero?
puts "It is not possible to fairly split this treasure #{guys} ways."
else
share =3D total / guys

shares =3D []
guys.times do |i|
mine =3D loot.find_sum(share)
unless mine.nil?
mine.each { |k| loot.delete_at(loot.index(k)) }
shares << mine
end
end

if shares.size =3D=3D guys
shares.each_with_index do |s, i|
puts "#{i}: #{s.join(' ')}"
end
else
puts "It is not possible to fairly split this treasure #{guys} ways."
end
end

 

[Patrick Deuster]

--------------010501060907080903000407
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

I don't believe that this problem is equivalent to the subset sum
problem, because all of the numbers involved are positive. Different
animal.

Luke Blanshard

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.

Patrick Deuster

--------------010501060907080903000407--

 

[Niklas Frykholm]

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

 

[Ross Bamford]

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

 

[avi.bryant]

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

 

[0x002A]

=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...
=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
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(" ")}"
}
}

 

[Simon Kröger]

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 + 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 + ]}
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!')