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

**URL:** <https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456>\
**Category:** Ruby\
**Created:** [February 6, 2006, 3:20pm UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456 "2006-02-06T15:20:06Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![oldbug](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/c0e974/32.png) [@oldbug](https://www.ruby-forum.com/u/oldbug)\
**Post date:** [February 6, 2006, 3:20pm UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456/1 "2006-02-06T15:20:06Z")

</div>

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 😉

* * *

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

---

<div class="post-metadata">

**Author:** ![oldbug](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/c0e974/32.png) [@oldbug](https://www.ruby-forum.com/u/oldbug)\
**Post date:** [February 6, 2006, 8:00pm UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456/2 "2006-02-06T20:00:27Z")

</div>

On 2/6/06, Patrick D. [removed\_email\_address@domain.invalid](mailto: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

---

<div class="post-metadata">

**Author:** ![oldbug](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/c0e974/32.png) [@oldbug](https://www.ruby-forum.com/u/oldbug)\
**Post date:** [February 8, 2006, 2:44pm UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456/3 "2006-02-08T14:44:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![oldbug](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/c0e974/32.png) [@oldbug](https://www.ruby-forum.com/u/oldbug)\
**Post date:** [February 9, 2006, 2:22am UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456/4 "2006-02-09T02:22:03Z")

</div>

On 2/8/06, Manuel K. [removed\_email\_address@domain.invalid](mailto: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

---

<div class="post-metadata">

**Author:** ![oldbug](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/c0e974/32.png) [@oldbug](https://www.ruby-forum.com/u/oldbug)\
**Post date:** [February 9, 2006, 1:28pm UTC](https://www.ruby-forum.com/t/solution-splitting-the-loot-65-my-second-attempt/53456/5 "2006-02-09T13:28:32Z")

</div>

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