[SOLUTION] Splitting the Loot (#65) (My second attempt)


#1

I had a small chat with Manuel K., who found out that my version
can’t split all loots correctly.
For example, my old version didn’t split

ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56
46

But it’s possible to split this loot to:
1: 7 78 80
2: 30 45 90
3: 19 70 76
4: 46 54 65
5: 21 34 43 67
6: 19 20 56 70

Here’s my second attempt. It should now split all loots correctly.
It now remembers splits that didn’t result in a complete solution and
trys again.
I also added some comments, so it’s easier to understand the code I use.

And because I had problems with Thunderbird wrapping the lines wrong I
attached my program to the email, too. Just in case :wink:


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, avoid=Array.new
@target,@numbers,@avoid = target, numbers,avoid.compact.uniq
end
def solve
solver @numbers.map { |n| [n] }
end
def solver paths
new_paths = Array.new # New paths will be stored here
paths.uniq.each do |path| # For each path do
return path if path.sum == @target && (!@avoid.include?path) # If
it’s a valid soulution and shouldn’t be avoided return in
@numbers.uniq.each do |n| # Add each number to the path
# If we have numbers left to add to the path and the sum will
not get greater then the target we want
if (path.count(n)<@numbers.count(n)) && (path.sum+n <= @target)
# Store the new path in our new new_path array if it
shouldn’t be avoided
new_path = path.dup
new_path << n
unless @avoid.include?new_path
new_paths << new_path unless new_path.sum == @target
return new_path if new_path.sum == @target
end
end
end
end
return nil if new_paths.empty? # We walked the whole tree and no
new path has been found, return nil
solver new_paths # Launch again with the new paths
end
end

def find_split fair_split,loot,avoid=Array.new
current_loot = loot.dup # Remember the loot before a split has been
made
stakes = Array.new

Try splitting the loot

begin
stake = Knapsack.new(fair_split,loot,avoid).solve
stakes << stake
stake.each { |s| loot.delete_one!(s) } unless stake.nil? # Remove
from the loot what has been found
end until stake.nil? || loot.empty? # Loop until the loot is empty,
or the algorithm found no valid solution
if loot.empty? # The whole loot is empty, a fair split has been found
return stakes
else
if current_loot == loot # The algorithm splitted nothing, it’s not
possible to fairly split the loot
return nil
else # The algorithm splitted something, but it wasn’t correct. Try
again avoiding the already found solutions
return find_split(fair_split,current_loot,stakes+avoid)
end
end
end

adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }

fair_split = loot.sum/adventures
stakes = (loot.sum%adventures).zero? ? find_split(fair_split,loot) : nil

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


#2

On 2/6/06, Patrick D. removed_email_address@domain.invalid wrote:

For example, my old version didn’t split

ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46

My turn to say ‘Doh!’
I found a case where the greedy algorithms failed and mine passed, but
now Patrick has found one that mine fails. But I have a simple 2 line
fix. I just need to move gems to my ‘pile2’ one at a time, instead of
a share-at-a-time. I had considered doing this before, but managed to
convince myself it was slower and not needed. Oops.

-Adam

##################################
#loot.rb
#Adam S.
#evenly splits an array into n sets of equal value

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

#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 gems
#5: repeat unitl you find all shares
#6: if you can’t find enough shares
#7: move one item from the first share to pile2
#8: repeat starting from step 2, include pile2 when searcing the
remainder in step 4

this serves to shuffle the possible combinations.

if all the gems are moved to pile2, there is no possible solution

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] ##This line changes to the following two
lines
pile2 << splits[0].shift
pile1 += splits[0]
end
return nil
end

if FILE == $0

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


#3

Adam S. wrote:

My turn to say ‘Doh!’

Yet again. Your new version doesn’t split

6-ways
26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52

possible solution:
1: [10, 39, 94]
2: [1, 52, 90]
3: [3, 51, 89]
4: [9, 20, 37, 77]
5: [15, 17, 34, 77]
6: [22, 22, 26, 26, 47]

Manuel K.


#4

On 2/8/06, Manuel K. removed_email_address@domain.invalid wrote:

Adam S. wrote:

My turn to say ‘Doh!’

Yet again. Your new version doesn’t split

6-ways
26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52

Aargh.
How about this one: here is a replacement splitter function - drop
into my last submission.
I added 2 more tests to detect unsplittable sets before I start
iterating, and I fixed the iterator to be sure it tests every
combination, and quits as soon as it finds a value which can not fit
into any fair share. Oh, and I added one helper to Integer:

######################
class Integer
def odd?
self % 2 != 0
end
end

def splitter n, loot
splits=[]
pile1,pile2=loot.dup.sort.reverse,[]
total = loot.sum
share = total/n
num_odd = loot.inject(0){|s,g| g.odd? ? s+1 : s}

lots of ways to fail early:

doesn’t divide evenly; not enough items; one item bigger than share

size;

the number of items worth more than 1/2 share must be < number of

shares

if the share size is even, there must be an even number of items

with odd values

if the share size is odd, there must be an even number plus one

for every share

return nil if total%n != 0 || loot.size < n || loot.max > share
return nil if loot.find_all{|g| g>share/2}.size > n
num_odd-=n if share.odd?
return nil if num_odd < 0 || num_odd.odd?

#pile1 holds all the items we haven’t tried to make a share with.
#take a candidate from the pile.
#if you can’t make a share using that one, it is impossible to
divide the loot.
#othewise, keep trying to make shares.
#if you get stuck, move the candidate to pile2, and start again.
#if pile1 becomes empty, give up

until pile1.empty?
candidate = pile1.shift
remaining = (pile1+pile2)
splits[0] = remaining.find_subset_with_sum(share - candidate)
break if !splits[0]
splits[0].unshift candidate
(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].shift
end
nil
end

######################
-Adam


#5

Adam S. wrote:

Aargh.
How about this one: here is a replacement splitter function - drop
into my last submission.
I added 2 more tests to detect unsplittable sets before I start
iterating, and I fixed the iterator to be sure it tests every
combination, and quits as soon as it finds a value which can not fit
into any fair share. Oh, and I added one helper to Integer:

It doesn’t split (46 69 88 119 130 159 208 233 242 396) 2-ways:

1: 88 119 242 396
2: 46 69 130 159 208 233

Manuel