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

I wrote:
> ...
> Technically, this is not so much an insight as an intuition.  It might 
> not be true in all cases...
D'oh!  Here's my second solution, which does backtrack if necessary.  It 
handles Adam's example, and a shorter example I found:


$ ruby loot.rb 3   3 3 2 2 2 2 2 2 2 1
This loot can't be evenly split 3 ways

$ ruby loot2.rb 3   3 3 2 2 2 2 2 2 2 1
1: 2 2 3
2: 2 2 3
3: 1 2 2 2


$ ruby loot.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86 
91 96
This loot can't be evenly split 5 ways

$ ruby loot2.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86 
91 96
1: 4 8 9 86 96
2: 6 39 67 91
3: 18 26 76 83
4: 55 66 82
5: 34 36 40 43 50


This one uses recursive yielding to manage the search space.  It should 
be close to the first solution in speed for cases where the heuristic 
applies, except for the array duping.

Luke Blanshard

--------------020308050602040408010501
Content-Type: text/plain;
 nameoot2.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filenameoot2.rb"

#!/usr/bin/ruby -w

# Ruby quiz #65, splitting the loot, take 2
# Usage: loot2.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

class Array
  # Returns a new array consisting of the elements of this array at
  # the given indices.
  def subscript indices
    indices.inject([]){|answer, i| answer << self[i]}
  end

  # Deletes all given indices from self, returns self.  Assumes
  # indices are in reverse order.
  def delete_at_all! indices
    indices.each{|i| delete_at i}
    self
  end
end

# Splits the given array of values up into count equal arrays, or nil.
def split values, count
  total  alues.inject(0){|s,v|return nil if v<0;s+v}
  return nil if count <  or total % count ! 
  find_split values.sort.reverse!, count, total/count
end

# Recursively picks sublists of "values" that sum to "sum", returns a
# list of them or nil.
def find_split values, count, sum
  return [values.reverse!] if count 1
  pick values, sum do |indices|
    return nil if indices[-1] !   # If we can't consume the first element, give up
    result  ind_split( values.dup.delete_at_all!(indices), count-1, sum )
    return result.unshift(values.subscript(indices)) if result
  end
  return nil
end

# Continuously picks values from the given array totaling sum,
# yielding a list of indices for each sublist found.  Assumes values
# is sorted highest first.
def pick values, sum, lo  # Skip past elements bigger than sum
  i  o
  i +  while i < values.size && values[i] > um
  yield [i-1] if i>lo && values[i-1] sum

  cutoff  um
  while i < values.size
    value  alues[i]
    if value < cutoff
      pick( values, sum-value, i+1 ){|indices| yield indices << i}
      cutoff  alue # Try the next unique value
    end
    i + 
  end
end

# Main program
if $0 __FILE__
  count, *values  RGV.map {|arg| Integer(arg)}
  if result  plit( 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

--------------020308050602040408010501--