# Splitting the Loot (#65)

**URL:** <https://www.ruby-forum.com/t/splitting-the-loot-65/65031>\
**Category:** Ruby\
**Created:** [February 9, 2006, 2:50pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031 "2006-02-09T14:50:52Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 9, 2006, 2:50pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/1 "2006-02-09T14:50:52Z")

</div>

There was some debate on the list about which NP-complete problem this  
actually  
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 K. 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:

```
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!')

```

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…

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 10, 2006, 12:23am UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/2 "2006-02-10T00:23:31Z")

</div>

Ruby Q. schrieb:

> (…)
> 
> (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
```

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 10, 2006, 1:52am UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/3 "2006-02-10T01:52:29Z")

</div>

On Feb 9, 2006, at 5:23 PM, Manuel K. wrote:

> 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 G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 10, 2006, 2:26am UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/4 "2006-02-10T02:26:44Z")

</div>

Manuel K. wrote:

> 

Thanks, Manuel. Since it was 4:00 AM when I wrote the email wrapping  
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 B.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 10, 2006, 4:15am UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/5 "2006-02-10T04:15:49Z")

</div>

On Feb 9, 2006, at 7:26 PM, Luke B. wrote:

> 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 G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 11, 2006, 2:24pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/6 "2006-02-11T14:24:48Z")

</div>

Aha. You need to be using my _second_ solution, cleverly named  
“loot2.rb”. Though actually, when I tested them with your example, they  
both worked. Can you give more detail?

Luke

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 10, 2006, 5:05pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/7 "2006-02-10T17:05:06Z")

</div>

One group of combinations I found that Luke’s solution didn’t work  
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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 11, 2006, 4:20pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/8 "2006-02-11T16:20:52Z")

</div>

Sorry. Wrong example. It won’t split for things including 2 values  
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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [February 11, 2006, 5:30pm UTC](https://www.ruby-forum.com/t/splitting-the-loot-65/65031/9 "2006-02-11T17:30:42Z")

</div>

Wow, right you are. I guess this 3AM coding thing has its down side.