Splitting the Loot (#65)

[bbazzarrakk]

The three rules of Ruby Q.:

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

[bbazzarrakk]

1: 9 12 32 34 49
2: 14 17 23 40 42

Can one assume that the treasure values are only integers?

Aditya

[bbazzarrakk]

Aditya M. wrote:

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.

…
Can one assume that the treasure values are only integers?
I certainly hope so.

[bbazzarrakk]

On 2/5/06, Luke B. [email protected] wrote:

Can one assume that the treasure values are only integers?
I certainly hope so.

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

[bbazzarrakk]

Patrick H. [email protected] writes:

…
Can one assume that the treasure values are only integers?
I certainly hope so.

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

Trying not to criticize the Quiz too harsh, but I think the amount of
NP-complete quizzes got pretty high… couldn’t we have some quizzes
that can be solved without brute-forcing or heuristics?

[bbazzarrakk]

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

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[i].sort.join(” ") }
end

[bbazzarrakk]

Patrick H. wrote:

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

It’s the famous Subset Sum Problem (a special case of the knapsack
problem), and generally it’s an NP-Complete problem.

Cheers,
Antonio

[bbazzarrakk]

On Feb 5, 2006, at 12:09 AM, Aditya M. wrote:

$ 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

Can one assume that the treasure values are only integers?

Yes, they are.

James Edward G. II

[bbazzarrakk]

On Feb 5, 2006, at 9:04 AM, Christian N. wrote:

Trying not to criticize the Quiz too harsh, but I think the amount of
NP-complete quizzes got pretty high… couldn’t we have some quizzes
that can be solved without brute-forcing or heuristics?

Luckily, you, as a community, are 100% in control of this. It’s your
quiz, I just manage it:

[email protected]

Personally, I agree with you, but it’s hard to deny what is popular.
Take a look through the past quizzes and see what people tend to
submit most for…

James Edward G. II

P.S. Last week’s quiz was not an NP-complete problem.

[bbazzarrakk]

Patrick D. wrote:

…
The splitting the loot problem is actually a problem known as the
“Knapsack problem” or the “Subset sum problem”.
Subset sum problem - Wikipedia
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 B.

[bbazzarrakk]

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

Hello,
this is my first participation in a Ruby Q… 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 K.

=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

[bbazzarrakk]

#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[i].add ruby #add the ruby to the this pile
if piles[i].sum <= divy and sumit(piles,treasure,divy) != nil
return (piles) #that worked ok, now divy up the rest of the
booty
else
piles[i].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[i].sort!
print “#{i}:”
print " #{piles[i].rem}" while piles[i].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)

“Ruby Q.” [email protected] wrote in message
news:[email protected]…

[bbazzarrakk]

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

[bbazzarrakk]

“Ruby Q.” [email protected] wrote in message

This week’s Ruby Q. 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 S.
#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==self
arr.each{|e| if (n=index(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 = self.sort.reverse
sum,set = 0,[]
a.each {|e|
if (sum+e <= n)
sum+=e
set<<e
return set if sum == n
end
}
nil
end

def find_subset_with_sum n
s = quick_find_subset_with_sum n
return s if s
possibilities, seen = [self.select{|e| e<=n}],{}
until possibilities.empty?
candidate = possibilities.pop
diff = candidate.sum - n
return candidate if diff == 0
break if diff < 0
candidate.each_with_index{|e,i|
break if e > diff
new_cand = (candidate.dup)
new_cand.delete_at(i)
return new_cand if e == diff
possibilities << new_cand if !seen[new_cand]
seen[new_cand]=true
}
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=[]
pile1,pile2=loot.dup.sort.reverse,[]
total = loot.sum
share = total/n
return nil if total%n != 0 || loot.size < n || loot.max > share

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

if FILE == $0

if ARGV.size < 2 || ARGV[0].to_i < 1
puts “Usage: #{$0} partners item1 item2 …”
else
shares = 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

[bbazzarrakk]

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

[bbazzarrakk]

On Feb 5, 2006, at 5:56 PM, Dave H. wrote:

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.

The submission message you quoted explained the change.

James Edward G. II

[bbazzarrakk]

Stu Glaser wrote:

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

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.

Cheers,
Antonio

[bbazzarrakk]

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 == first
return [first]
else
sub = tail.find_sum(n - first)
return [first] + sub unless sub.nil?
return tail.find_sum(n)
end
end
nil
end
end

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

total = loot.sum

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

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

if shares.size == 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

[bbazzarrakk]

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.

[bbazzarrakk]

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

Patrick D.