[QUIZ] Splitting the Loot (#65)
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:
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
>> 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.
Patrick Hurley
I just certainly hope there is not too many treasures, I am pretty
sure this is NP complete.
Christian Neukirchen
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?
--
Christian Neukirchen <chneuk...@gmail.com> http://chneukirchen.org
Antonio Cangiano
> 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
--
Zen and the Art of Ruby Programming
http://antoniocangiano.com
Patrick Deuster
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)>=@numbers.count(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
James Edward Gray II
>> 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
>
> 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
problem, because all of the numbers involved are positive. Different
animal.
Luke Blanshard
Manuel Kasten
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[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 Quiz" <ja...@grayproductions.net> wrote in message
news:20060203152022.EJEN831...@localhost.localdomain...
Adam Shelly
> 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==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
Chris Parker
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
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
On Feb 5, 2006, at 8:53, Manuel Kasten wrote:
> def initialize pirates, treasure
I'll just note that the original posting never said anything about
pirates. :)
James Edward Gray II
The submission message you quoted explained the change. :)
James Edward Gray II
Antonio Cangiano
> 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.
Matthew Moss
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
Patrick Deuster
"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
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
wrote:
> Luke Blanshard wrote:
>> Patrick Deuster 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:
>
> "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...
--
Ross Bamford - ro...@roscopeco.remove.co.uk
avi.b...@gmail.com
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
Christian Neukirchen
0x0...@gmail.com
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[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(" ")}"
}
}
Simon Kröger
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
Manuel Kasten
> 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
----------------------
madonion@gentoo $ 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 Blanshard
> Luke Blanshard wrote:
>> Patrick Deuster 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.
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 Blanshard
Patrick Deuster
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. :-)
Patrick
Bill Dolinar
Here's my solution. It uses recursion and doesn't check unnecessary
combinations. I don't think it misses any, but that seems pretty
hard to test. It checks for a valid combination by looking for the
smallest number of items in a set first since it's faster to rule
out. It uses a Combinations class to iterate through the
possible combinations. The class also keeps a running sum of the
current combination to reduce the number of additions/subtractions.
=end
def split_equally(partners, a)
a.sort!
total = a.inject {|sum, n| sum + n}
# check for sum not multiple of partners
return nil if total % partners != 0
split = total/partners
# check for largest greater than split
return nil if a.last > split
if a.last == split
# solution with last item
return check_solution(partners, [a.pop], a)
else
min_elements = split/a.last + 1
max_elements = a.size/partners
# search for solution with combinations of valid # elements
(min_elements..max_elements).each do |items|
combo = Combinations.new(a, a.size - items)
solution, leftover = find_one_split(split, combo, a)
while solution != nil
solution = check_solution(partners, solution, leftover)
if solution != nil
return solution
end
solution, leftover = find_one_split(split, combo, a)
end
end
end
nil
end
# return solution for two partners or recurse back
# to split_equally for more
def check_solution(partners, solution, leftover)
if partners == 2
return [leftover] + [solution]
else
leftover_solution = split_equally(partners - 1, leftover)
if leftover_solution != nil
return leftover_solution << solution
end
end
nil
end
# look for one split by beginning with passed combination (missing
# one item) and then working down
def find_one_split(sum, combo, a)
finished = false
until finished
first_item = combo.index_of(1)
if first_item > 0
leftover = sum - combo.sum
if leftover > a[first_item-1]
combo.skip_smallest
elsif a.first <= leftover
matching = a[0..first_item].index(leftover)
if matching != nil
combo[matching] = 1
return combo.split(a)
end
end
end
finished = !combo.next_smaller
end
nil
end
class Combinations
attr_accessor :bits
attr_accessor :sum
def initialize(a, max_zero)
@bits = Array.new(a.size) {|i| i > max_zero ? 1 : 0}
@a = a
@sum = find_sum
end
def [](i)
@bits[i]
end
def []=(i, value)
if @bits[i] == 1 && value == 0
@sum -= @a[i]
elsif @bits[i] == 0 && value == 1
@sum += @a[i]
end
@bits[i] = value
end
def index_of(value)
i = @bits.index(value)
end
# next smaller combination with same number of items
def next_smaller
first_item = @bits.index(1)
if first_item == 0
skipped = 0
@bits.each_with_index do |n, i|
if n == 1
self[i] = 0
if i <= skipped
skipped += 1
else
self[i] = 0
(i-1).downto(i-1-skipped) {|i| self[i] = 1}
return true
end
end
end
else
self[first_item - 1] = 1
self[first_item] = 0
return true
end
return false
end
def skip_smallest
first_item = @bits.index(1)
self[first_item] = 0
self[0] = 1
end
def split(a)
i = -1
a.partition {|n| i += 1; @bits[i] == 1;}
end
private
def find_sum
total = 0
@a.each_with_index {|n, i| total += n if @bits[i] != 0}
total
end
end
if __FILE__ == $0
a = ARGV.collect {|n| n.to_i}
partners = a.shift
split = split_equally(partners, a)
if split == nil
print "It is not possible to fairly split this treasure "
print "#{partners} ways.\n"
else
split.each_with_index do |n,i|
print "#{i}: ", n.join(" "), "\n"
end
end
end
Manuel Kasten
> 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 Kasten
Manuel Kasten
> =begin
> Here's my solution. It uses recursion and doesn't check unnecessary
> combinations. I don't think it misses any, but that seems pretty
> hard to test. It checks for a valid combination by looking for the
> smallest number of items in a set first since it's faster to rule
> out. It uses a Combinations class to iterate through the
> possible combinations. The class also keeps a running sum of the
> current combination to reduce the number of additions/subtractions.
> =end
Hi.
It doesn't split
61, 63, 21, 87, 64, 84, 96, 35, 14, 74, 20, 62, 36, 64, 6, 14, 54, 53,
46, 84, 62, 10, 64, 33, 32, 24, 89
8-ways
nor
7, 21, 30, 54, 52, 99, 77, 85, 56, 28, 80, 17, 60, 60, 38, 68, 53, 80,
75, 85, 9
7-ways
Manuel Kasten
James Edward Gray II
> If my solution is correct :)
I believe it is. I couldn't break it while writing the summary
anyway. ;)
James Edward Gray II
Simon Kröger
> So it doesn't. But it says it won't split quickly! :) Do you have a
> solutions for these and list of other tests I could throw at it?
>
>> 61, 63, 21, 87, 64, 84, 96, 35, 14, 74, 20, 62, 36, 64, 6, 14, 54,
>> 53, 46, 84, 62, 10, 64, 33, 32, 24, 89
>>
>> 8-ways
64 64 35 6
96 63 10
89 32 20 14 14
84 64 21
84 61 24
74 62 33
87 46 36
62 54 53
>> 7, 21, 30, 54, 52, 99, 77, 85, 56, 28, 80, 17, 60, 60, 38, 68, 53,
>> 80, 75, 85, 9
>>
>> 7-ways
80 75 7
99 54 9
85 60 17
60 53 28 21
80 52 30
68 56 38
85 77
If my solution is correct :)
cheers
Simon
Dominik Bathon
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
Ruby Quiz
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:
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
# ...
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:
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:
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
# ...
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...
Manuel Kasten
> (...)
>
> (my go method)
>
> 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.
You may call it a minor optimization, and I agree it's an easy one. But
it speeds up the whole process around factor 100, so without it my
simple brute force approach would have been intolerable slow.
> As usual, all solutions were educational. My thanks to all for the
> code and excellent discussion this time around.
I want to mention Luke Blanchard's second solution. It is the fastest
solution of those I tested that worked without flaws. I never ever saw
it running longer than 0.2 seconds and I did test it a *lot* (because it
is around factor 10-20 faster than the next correct solution, and I
thought it must fail sometimes, but it never did). I couldn't believe
its speed. I studied his code for ca. 30 min just to understand what
it's doing (luckily it's got a lot of comments, I wouldn't have been
able to understand it otherwise). Then I could tell it is indeed
correct, but its speed is nevertheless amazing.
Another interesting solution is the one from 0x002A. It is quite slow,
but if you've never seen anything with lazy evaluation ("require
'lazylist'") you should check it. The concept was new to me and gave me
quite a headache analyzing it (the good kind of headache - I love when
the fog raises and I suddenly understand what's going on).
> Tomorrow we will begin a run of at least three non-NP-complete
> problems by myself and others...
I see forward to it. I'm not home for the weekend, but I hope to have a
go at it on Monday.
Manuel
Bill Dolinar
came up with all these difficult tests?
Thanks,
Bill
=begin
Here's my 2nd try. My last try missed one combination when
backtracking. This time I tested it by writing code to go through
all the possible combinations adding up to a given sum and number
of partners, but it seems like it's the larger summed tests that
find the bugs. I also changed the part that calculates the
minimum number of elements in a combination to check, which made
it faster than before. It's still lags a bit behind the speed of
Manuel Kasten's solution.
=end
def split_equally(partners, a)
a = a.sort
total = a.inject {|sum, n| sum + n}
# check for sum not multiple of partners
return nil if total % partners != 0
split = total/partners
# check for largest greater than split
return nil if a.last > split
if a.last == split
# solution with last item
return split_subset(partners, [a.last], a[0...(a.size-1)])
else
sum = 0
min_elements = 2
(a.size-1).downto(0) do |i|
sum += a[i]
if sum >= split
min_elements = [a.size - i, 2].max
break
end
end
max_elements = a.size/partners
# search for solution with combinations of valid # elements
(min_elements..max_elements).each do |items|
combo = Combinations.new(a, a.size - items)
begin
more_combos, solution, leftover = find_one_split(split,
combo, a)
if (solution != nil && solution.compact != [])
solution = split_subset(partners, solution, leftover)
end
if solution != nil && solution.compact != []
return solution
end
end while more_combos
end
end
nil
end
# return solution for two partners or recurse back
# to split_equally for more
def split_subset(partners, solution, leftover)
if partners == 2
return [leftover] + [solution]
else
leftover_solution = split_equally(partners - 1, leftover)
if leftover_solution != nil
return leftover_solution << solution
end
end
nil
end
# look for one split by beginning with passed combination (missing
# one item) and then working down
def find_one_split(sum, combo, a)
finished = false
until finished
first_item = combo.index_of(1)
if first_item > 0
leftover = sum - combo.sum
if leftover > a[first_item-1]
combo.skip_smallest
elsif a.first <= leftover
matching = a[0..first_item].index(leftover)
if matching != nil
solution, leftover = combo.split(a, matching)
more_combos = combo.next_smaller
return more_combos, solution, leftover
end
end
end
finished = !combo.next_smaller
end
return false
end
def split(a, index)
i = -1
a.partition {|n| i += 1; @bits[i] == 1 || i == index;}
James Edward Gray II
> Another interesting solution is the one from 0x002A. It is quite slow,
> but if you've never seen anything with lazy evaluation ("require
> 'lazylist'") you should check it.
I agree. I almost discussed this one, but it had a few issues, like
the speed you mentioned. I'm always limited by my time, otherwise I
would surely write-up all the solutions each week. :(
James Edward Gray II
Luke Blanshard
> ...
> I want to mention Luke Blanchard's second solution. It is the fastest
> solution of those I tested that worked without flaws. I never ever saw
> it running longer than 0.2 seconds and I did test it a *lot* (because it
> is around factor 10-20 faster than the next correct solution, and I
> thought it must fail sometimes, but it never did). I couldn't believe
> its speed. I studied his code for ca. 30 min just to understand what
> it's doing (luckily it's got a lot of comments, I wouldn't have been
> able to understand it otherwise). Then I could tell it is indeed
> correct, but its speed is nevertheless amazing.
>
that guy -- I finally got up to code the thing at 3 after lying awake
all night -- I think my explanation was a little terse if not downright
misleading.
The key idea is that the easiest way to manage searching all possible
combinations of something is with loops and recursion, meaning you just
step through all combinations right inline. Most solvers of NP-complete
problem spaces end up spending a lot of effort setting up data
structures to keep track of where they are in the process. My approach
was to just use local variables and the stack, combined with Ruby's
magical ability to long-jump out of a deep stack by just returning from
a block (which I first used some 15 years ago in Smalltalk). No extra
bookkeeping required.
The "pick" function just walks all combinations recursively, and when it
finds one it yields a list of the indexes that make up the successful
combination. Since it is recursive, it ends up yielding to itself up
the chain. To take the 3-3s-and-9-2s example, we'll have an execution
setup like this, where further down the page corresponds to further down
the stack and further to the right corresponds to further nesting:
values = [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2]
pick values, 9, 0:
pick values, 6, 1:
pick values, 3, 2:
yield [2]
yield [2, 1]
yield [2, 1, 0]
The [2, 1, 0] yielded by the outermost call corresponds to the indexes
of the 3 3s. The caller of that outermost call is "find_split", and the
way it handles this list of indexes is to dup the array of values,
delete the indices yielded from the dup, and then recurse itself on the
shorter array. In this case, it's trying to divide 9 2s in half, and
that will fail, so it just returns. This means the original call to
pick continues, meaning all of those yields finish, and we're nested
three levels deep again. The innermost one ends up recursing again
without success, and then the second one moves on to the 2s and recurses
a couple of times to get our next solution:
values = [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2]
pick values, 9, 0:
pick values, 6, 1:
pick values, 4, 4:
pick values, 2, 5:
yield [5]
yield [5, 4]
yield [5, 4, 3]
yield [5, 4, 3, 0]
This time find_split's recursion succeeds (on 2 3s and 6 2s), and so it
returns the solution, jumping out of the above stack of picks without
ever continuing them.
Isn't that cool?
Luke Blanshard
James Edward Gray II
> Isn't that cool?
It sure is and that was a great explanation of just how cool it is.
I'll be the one loosing sleep tonight, trying to wrap my head around
all that and where I can use it... ;)
James Edward Gray II
Bill Dolinar
for was when the loot included a single value to be split to one
partner such as:
ruby loot.rb 3 5 4 4 1 1
It will work if you expand the line in the pick function reading:
i += 1 while i < values.size && values[i] >= sum
to:
if values[lo] == sum
i += 1
else
i += 1 while i < values.size && values[i] >= sum
end
I'm not sure how this changed the speed, but for all solvable
combinations of 3 partners with a sum of 9 Luke's ran in 80 seconds,
and Manuel's ran in 105 seconds.
Bill
Luke Blanshard
"loot2.rb". Though actually, when I tested them with your example, they
both worked. Can you give more detail?
Luke
Bill Dolinar
equalling the maximum split amount like:
loot.rb 3 5 5 5
loot.rb 3 4 1 5 5
loot.rb 3 3 2 5 5
loot.rb 3 3 1 1 5 5
loot.rb 3 2 3 5 5
loot.rb 3 2 2 1 5 5
loot.rb 3 2 1 1 1 5 5
loot.rb 3 1 1 1 1 1 5 5
loot.rb 3 5 4 1 5
loot.rb 3 5 3 2 5
loot.rb 3 5 3 1 1 5
loot.rb 3 5 2 3 5
loot.rb 3 5 2 2 1 5
loot.rb 3 5 2 1 1 1 5
loot.rb 3 5 1 1 1 1 1 5
loot.rb 3 5 5 4 1
loot.rb 3 5 5 3 2
loot.rb 3 5 5 3 1 1
loot.rb 3 5 5 2 3
loot.rb 3 5 5 2 2 1
loot.rb 3 5 5 2 1 1 1
loot.rb 3 5 5 1 1 1 1 1
Bill