I had a small chat with Manuel K., who found out that my version can't split all loots correctly. For example, my old version didn't split ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46 But it's possible to split this loot to: 1: 7 78 80 2: 30 45 90 3: 19 70 76 4: 46 54 65 5: 21 34 43 67 6: 19 20 56 70 Here's my second attempt. It should now split all loots correctly. It now remembers splits that didn't result in a complete solution and trys again. I also added some comments, so it's easier to understand the code I use. And because I had problems with Thunderbird wrapping the lines wrong I attached my program to the email, too. Just in case ;) ---------------- class Array def sum inject { |s,x| s + x } end def delete_one! n (i = index(n)) ? delete_at(i) : nil end def count n inject(0) { |c,x| x == n ? c+1 : c } end end class Knapsack def initialize target, numbers, avoid=Array.new @target,@numbers,@avoid = target, numbers,avoid.compact.uniq end def solve solver @numbers.map { |n| [n] } end def solver paths new_paths = Array.new # New paths will be stored here paths.uniq.each do |path| # For each path do return path if path.sum == @target && (!@avoid.include?path) # If it's a valid soulution and shouldn't be avoided return in @numbers.uniq.each do |n| # Add each number to the path # If we have numbers left to add to the path and the sum will not get greater then the target we want if (path.count(n)<@numbers.count(n)) && (path.sum+n <= @target) # Store the new path in our new new_path array if it shouldn't be avoided new_path = path.dup new_path << n unless @avoid.include?new_path new_paths << new_path unless new_path.sum == @target return new_path if new_path.sum == @target end end end end return nil if new_paths.empty? # We walked the whole tree and no new path has been found, return nil solver new_paths # Launch again with the new paths end end def find_split fair_split,loot,avoid=Array.new current_loot = loot.dup # Remember the loot before a split has been made stakes = Array.new # Try splitting the loot begin stake = Knapsack.new(fair_split,loot,avoid).solve stakes << stake stake.each { |s| loot.delete_one!(s) } unless stake.nil? # Remove from the loot what has been found end until stake.nil? || loot.empty? # Loop until the loot is empty, or the algorithm found no valid solution if loot.empty? # The whole loot is empty, a fair split has been found return stakes else if current_loot == loot # The algorithm splitted nothing, it's not possible to fairly split the loot return nil else # The algorithm splitted something, but it wasn't correct. Try again avoiding the already found solutions return find_split(fair_split,current_loot,stakes+avoid) end end end adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i } fair_split = loot.sum/adventures stakes = (loot.sum%adventures).zero? ? find_split(fair_split,loot) : nil if stakes.nil? puts "It is not possible to fairly split this treasure #{adventures} ways." else stakes.size.times { |i| puts "#{i+1}: " + stakes[i].sort.join(" ") } end

on 2006-02-06 16:20

on 2006-02-06 21:00

On 2/6/06, Patrick D. <removed_email_address@domain.invalid> wrote: > For example, my old version didn't split > > ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46 My turn to say 'Doh!' I found a case where the greedy algorithms failed and mine passed, but now Patrick has found one that mine fails. But I have a simple 2 line fix. I just need to move gems to my 'pile2' one at a time, instead of a share-at-a-time. I had considered doing this before, but managed to convince myself it was slower and not needed. Oops. -Adam ################################## #loot.rb #Adam S. #evenly splits an array into n sets of equal value 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 #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 gems #5: repeat unitl you find all shares #6: if you can't find enough shares #7: move one item from the first share to pile2 #8: repeat starting from step 2, include pile2 when searcing the remainder in step 4 # this serves to shuffle the possible combinations. # if all the gems are moved to pile2, there is no possible solution 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] ##This line changes to the following two lines pile2 << splits[0].shift pile1 += splits[0] end return nil end if __FILE__ == $0 n = ARGV.shift.to_i if ARGV.size < 2 || n < 1 puts "Usage: #{$0} partners item1 item2 ..." else shares = splitter(n, ARGV.map{|a| a.to_i }) if !shares puts "This loot can not be evenly divided into #{n} parts!" else shares.sort_by{|a|[a.size,-a.max]}.each_with_index{|share,i| puts "#{i}: #{share.sort.reverse.join(' ')}"} puts "everyone gets #{shares[0].sum}" end end end

on 2006-02-08 15:44

```
Adam S. wrote:
> My turn to say 'Doh!'
Yet again. Your new version doesn't split
6-ways
26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52
possible solution:
1: [10, 39, 94]
2: [1, 52, 90]
3: [3, 51, 89]
4: [9, 20, 37, 77]
5: [15, 17, 34, 77]
6: [22, 22, 26, 26, 47]
Manuel K.
```

on 2006-02-09 03:22

On 2/8/06, Manuel K. <removed_email_address@domain.invalid> wrote: > Adam S. wrote: > > My turn to say 'Doh!' > > Yet again. Your new version doesn't split > > 6-ways > 26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52 > Aargh. How about this one: here is a replacement splitter function - drop into my last submission. I added 2 more tests to detect unsplittable sets before I start iterating, and I fixed the iterator to be sure it tests every combination, and quits as soon as it finds a value which can not fit into any fair share. Oh, and I added one helper to Integer: ###################### class Integer def odd? self % 2 != 0 end end def splitter n, loot splits=[] pile1,pile2=loot.dup.sort.reverse,[] total = loot.sum share = total/n num_odd = loot.inject(0){|s,g| g.odd? ? s+1 : s} # lots of ways to fail early: # doesn't divide evenly; not enough items; one item bigger than share size; # the number of items worth more than 1/2 share must be < number of shares # if the share size is even, there must be an even number of items with odd values # if the share size is odd, there must be an even number plus one for every share return nil if total%n != 0 || loot.size < n || loot.max > share return nil if loot.find_all{|g| g>share/2}.size > n num_odd-=n if share.odd? return nil if num_odd < 0 || num_odd.odd? #pile1 holds all the items we haven't tried to make a share with. #take a candidate from the pile. #if you can't make a share using that one, it is impossible to divide the loot. #othewise, keep trying to make shares. #if you get stuck, move the candidate to pile2, and start again. #if pile1 becomes empty, give up until pile1.empty? candidate = pile1.shift remaining = (pile1+pile2) splits[0] = remaining.find_subset_with_sum(share - candidate) break if !splits[0] splits[0].unshift candidate (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].shift end nil end ###################### -Adam

on 2006-02-09 14:28

Adam S. wrote: >> > > > Aargh. > How about this one: here is a replacement splitter function - drop > into my last submission. > I added 2 more tests to detect unsplittable sets before I start > iterating, and I fixed the iterator to be sure it tests every > combination, and quits as soon as it finds a value which can not fit > into any fair share. Oh, and I added one helper to Integer: It doesn't split (46 69 88 119 130 159 208 233 242 396) 2-ways: 1: 88 119 242 396 2: 46 69 130 159 208 233 Manuel