[SUMMARY] Splitting the Loot (#65)

[James_Edward_Gray_II]

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

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

[Manuel_Kasten]

Ruby Quiz 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

[James_Edward_Gray_II]

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

···

On Feb 9, 2006, at 5:23 PM, Manuel Kasten 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.

[Luke_Blanshard]

Manuel Kasten wrote:

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

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 Blanshard

[Bill_Dolinar]

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

···

On Feb 9, 2006, at 4:23 PM, Manuel Kasten wrote:

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.

[James_Edward_Gray_II]

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

···

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

Isn't that cool?

[Luke_Blanshard]

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

Bill Dolinar wrote:

···

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

On Feb 9, 2006, at 4:23 PM, Manuel Kasten wrote:

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.

[Bill_Dolinar]

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

···

On Feb 11, 2006, at 6:24 AM, Luke Blanshard wrote:

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

Bill Dolinar wrote:

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

On Feb 9, 2006, at 4:23 PM, Manuel Kasten wrote:

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.

[Luke_Blanshard]

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

Bill Dolinar wrote:

···

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

On Feb 11, 2006, at 6:24 AM, Luke Blanshard wrote:

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

Bill Dolinar wrote:

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

On Feb 9, 2006, at 4:23 PM, Manuel Kasten wrote:

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.