# Re: \[SOLUTION\] Splitting the Loot (#65)

**URL:** <https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313>\
**Category:** Ruby\
**Created:** [February 8, 2006, 8:31am UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313 "2006-02-08T08:31:54Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 8, 2006, 8:31am UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/1 "2006-02-08T08:31:54Z")

</div>

=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

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

---

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 8, 2006, 6:39pm UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/2 "2006-02-08T18:39:20Z")

</div>

Bill Dolinar wrote:

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

---

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 8, 2006, 10:08pm UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/3 "2006-02-08T22:08:19Z")

</div>

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?

Thanks,  
Bill

---

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 8, 2006, 10:19pm UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/4 "2006-02-08T22:19:16Z")

</div>

Bill Dolinar wrote:

> 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

---

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 8, 2006, 10:42pm UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/5 "2006-02-08T22:42:32Z")

</div>

On Feb 8, 2006, at 3:19 PM, Simon Kröger wrote:

> If my solution is correct 🙂

I believe it is. I couldn’t break it while writing the summary  
anyway. 😉

James Edward G. II

---

<div class="post-metadata">

**Author:** ![Bill\_Dolinar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/f0a364/32.png) [@Bill\_Dolinar](https://www.ruby-forum.com/u/Bill_Dolinar)\
**Post date:** [February 10, 2006, 1:35am UTC](https://www.ruby-forum.com/t/re-solution-splitting-the-loot-65/102313/6 "2006-02-10T01:35:53Z")

</div>

Thanks. Helped me track down a fix… I think. 🙂 How did you guys  
came up with all these difficult tests?

Thanks,  
Bill

On Feb 8, 2006, at 2:19 PM, Simon Kröger wrote:

> 96 63 10
> 
> > > 7-ways
> 
> cheers
> 
> Simon

=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 K.'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

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   
@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, index)  
i = -1  
a.partition {|n| i += 1; @bits[i] == 1 || i == index;}  
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