Adam Shelly
2/5/2006 10:03:00 PM
"Ruby Quiz" <james@grayproductions.net> wrote in message
> This week's Ruby Quiz is to write a program that fairly divides treasures,
> based on worth.
Here's mine. I reused several methods from the wierd numbers quiz.
#############################################
#loot.rb
#Adam Shelly
#evenly splits an array into N parts with equal value , if possible
class Array
def sum
inject(0){|s,v| s+v}
end
def subtract arr
return clear if arr==self
arr.each{|e| if (n=index(e)) then delete_at(n); end }
self
end
#fast version which misses some subsets.
#useful as a rough filter.
def quick_find_subset_with_sum n
a = self.sort.reverse
sum,set = 0,[]
a.each {|e|
if (sum+e <= n)
sum+=e
set<<e
return set if sum == n
end
}
nil
end
def find_subset_with_sum n
s = quick_find_subset_with_sum n
return s if s
possibilities, seen = [self.select{|e| e<=n}],{}
until possibilities.empty?
candidate = possibilities.pop
diff = candidate.sum - n
return candidate if diff == 0
break if diff < 0
candidate.each_with_index{|e,i|
break if e > diff
new_cand = (candidate.dup)
new_cand.delete_at(i)
return new_cand if e == diff
possibilities << new_cand if !seen[new_cand]
seen[new_cand]=true
}
end
nil
end
end
# Splitter algorithm
#1: put all loot in pile 1
#2: find a share from pile 1
#3: if you can't find one, it can't be split
#4: find a share in the remaining pile
#5: repeat unitl you find all shares
#6: if you can't find enough shares
#7: move the first share to pile2
#8: repeat from step 2, but add pile2 to the remainder in step 4
# this serves to shuffle the possible combinations, until you find one
that works.
def splitter n, loot
splits=[]
pile1,pile2=loot.dup.sort.reverse,[]
total = loot.sum
share = total/n
return nil if total%n != 0 || loot.size < n || loot.max > share
until pile1.empty?
splits[0] = pile1.find_subset_with_sum(share)
break if !splits[0]
remaining = pile1.subtract(splits[0])+pile2
(1...n).each do |i|
break if nil == (splits[i] = remaining.find_subset_with_sum(share))
remaining.subtract(splits[i])
end
return splits if splits[n-1]
pile2 += splits[0]
end
return nil
end
if __FILE__ == $0
if ARGV.size < 2 || ARGV[0].to_i < 1
puts "Usage: #{$0} partners item1 item2 ..."
else
shares = splitter(ARGV.shift.to_i, ARGV.map{|a| a.to_i })
if !shares
puts "This loot can not be evenly divided into #{n} parts!"
else
shares.each_with_index{|share,i| puts "#{i}: #{share.join(' ')}"}
puts "everyone gets #{shares[0].sum}"
end
end
end
#############################################
-Adam