Luke Blanshard
2/6/2006 9:58:00 AM
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
#!/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 = values.inject(0){|s,v|return nil if v<0;s+v}
return nil if count <= 0 or total % count != 0
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] != 0 # If we can't consume the first element, give up
result = find_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=0
# Skip past elements bigger than sum
i = lo
i += 1 while i < values.size && values[i] >= sum
yield [i-1] if i>lo && values[i-1] == sum
cutoff = sum
while i < values.size
value = values[i]
if value < cutoff
pick( values, sum-value, i+1 ){|indices| yield indices << i}
cutoff = value # Try the next unique value
end
i += 1
end
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