From: Luke Blanshard <luke@...>
Date: 2006-02-06T01:03:20+09:00
Subject: [/QUIZ] #65: Splitting the Loot

--------------030808070901020109060302
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

My submission is attached.  The key insight: if you start with the 
largest values you can divide the loot one gang member at a time without 
fear of getting wrongly stuck.  For an example of being wrongly stuck, 
consider:

% ruby loot.rb 3 1 1 1 2 2 2

The shares will all have to total 3, but if you start with the light end 
you might end up with (1, 1, 1) for the first guy, and then the rest of 
the loot can't be evenly split.  Starting with the heavy end, though, 
gets you to the right place.

Technically, this is not so much an insight as an intuition.  It might 
not be true in all cases.  But using it as a heuristic, we can cut the 
solution down to O(n^3).

The "split" function takes a list of values and the number of gang 
members and returns a list of sublists that all sum to the same amount, 
or nil if no solution is possible.  It works by sorting the list of 
values and calling "pick" once for each gang member to pick out that 
member's share from the remaining list.  Using our insight, we never 
backtrack in "split".  Once we've picked one member's share, we never go 
back to try a different combination.

"Pick" works recursively, walking from the high end of the list to the 
low end, until it finds a sublist that sums to the target amount or it 
runs off the end of the list.  This function waits to delete elements 
from the list until it finds a sublist that sums to the target amount.  
In this way, "pick" doesn't have to create any intermediate lists.


Luke Blanshard


--------------030808070901020109060302
Content-Type: text/plain;
 name="loot.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="loot.rb"

#!/usr/bin/ruby -w

# Ruby quiz #65, splitting the loot
# Usage: loot.rb <band-size> <values...>
#  where band-size is the number of adventurers in the band
#  and values is the list of numerical values of the rubies

# Splits the given array of values up into count equal arrays, or nil.
def split values, count
  total = values.inject(0){|s,v|return nil if v<0;s+v}
  return nil if count <= 0 or total % count != 0
  each   = total / count
  result = []
  values = values.sort
  until values.empty?
    share = pick values, each
    return nil unless share
    result << share
  end
  return result
end

# Picks values from the given array totaling sum, returns picked
# values and removes them from the argument.  Expects the array to be
# sorted.
def pick values, sum, hi=values.size
  cutoff = sum
  (hi-1).downto(0) do |i|
    value = values[i]
    if value == sum
      values.delete_at(i)
      return [sum]
    elsif value < cutoff
      if result = pick( values, sum - value, i )
        values.delete_at( i - result.size ) # Recursion already shifted us down
        return result << value
      end
      cutoff = value # Try the next unique value
    end
  end
  return nil # Nope, can't be done
end

# Main program
if $0 == __FILE__
  count, *values = ARGV.map {|arg| Integer(arg)}
  if result = split( values, count )
    $,, $\ = " ", "\n" # Set the field and record terminators
    count.times {|i| print "#{i+1}:", result[i]}
  else
    puts "This loot can't be evenly split #{count} ways"
  end
end

--------------030808070901020109060302--