=begin Here's my solution. It uses recursion and doesn't check unnecessary combinations. I don't think it misses any, but that seems pretty hard to test. It checks for a valid combination by looking for the smallest number of items in a set first since it's faster to rule out. It uses a Combinations class to iterate through the possible combinations. The class also keeps a running sum of the current combination to reduce the number of additions/subtractions. =end def split_equally(partners, a) a.sort! total = a.inject {|sum, n| sum + n} # check for sum not multiple of partners return nil if total % partners != 0 split = total/partners # check for largest greater than split return nil if a.last > split if a.last == split # solution with last item return check_solution(partners, [a.pop], a) else min_elements = split/a.last + 1 max_elements = a.size/partners # search for solution with combinations of valid # elements (min_elements..max_elements).each do |items| combo = Combinations.new(a, a.size - items) solution, leftover = find_one_split(split, combo, a) while solution != nil solution = check_solution(partners, solution, leftover) if solution != nil return solution end solution, leftover = find_one_split(split, combo, a) end end end nil end # return solution for two partners or recurse back # to split_equally for more def check_solution(partners, solution, leftover) if partners == 2 return [leftover] + [solution] else leftover_solution = split_equally(partners - 1, leftover) if leftover_solution != nil return leftover_solution << solution end end nil end # look for one split by beginning with passed combination (missing # one item) and then working down def find_one_split(sum, combo, a) finished = false until finished first_item = combo.index_of(1) if first_item > 0 leftover = sum - combo.sum if leftover > a[first_item-1] combo.skip_smallest elsif a.first <= leftover matching = a[0..first_item].index(leftover) if matching != nil combo[matching] = 1 return combo.split(a) end end end finished = !combo.next_smaller end nil end class Combinations attr_accessor :bits attr_accessor :sum def initialize(a, max_zero) @bits = Array.new(a.size) {|i| i > max_zero ? 1 : 0} @a = a @sum = find_sum end def [](i) @bits[i] end def []=(i, value) if @bits[i] == 1 && value == 0 @sum -= @a[i] elsif @bits[i] == 0 && value == 1 @sum += @a[i] end @bits[i] = value end def index_of(value) i = @bits.index(value) end # next smaller combination with same number of items def next_smaller first_item = @bits.index(1) if first_item == 0 skipped = 0 @bits.each_with_index do |n, i| if n == 1 self[i] = 0 if i <= skipped skipped += 1 else self[i] = 0 (i-1).downto(i-1-skipped) {|i| self[i] = 1} return true end end end else self[first_item - 1] = 1 self[first_item] = 0 return true end return false end def skip_smallest first_item = @bits.index(1) self[first_item] = 0 self[0] = 1 end def split(a) i = -1 a.partition {|n| i += 1; @bits[i] == 1;} end private def find_sum total = 0 @a.each_with_index {|n, i| total += n if @bits[i] != 0} total end end if __FILE__ == $0 a = ARGV.collect {|n| n.to_i} partners = a.shift split = split_equally(partners, a) if split == nil print "It is not possible to fairly split this treasure " print "#{partners} ways.\n" else split.each_with_index do |n,i| print "#{i}: ", n.join(" "), "\n" end end end

on 2006-02-08 08:31

on 2006-02-08 18:39

Bill Dolinar wrote: > =begin > Here's my solution. It uses recursion and doesn't check unnecessary > combinations. I don't think it misses any, but that seems pretty > hard to test. It checks for a valid combination by looking for the > smallest number of items in a set first since it's faster to rule > out. It uses a Combinations class to iterate through the > possible combinations. The class also keeps a running sum of the > current combination to reduce the number of additions/subtractions. > =end Hi. It doesn't split 61, 63, 21, 87, 64, 84, 96, 35, 14, 74, 20, 62, 36, 64, 6, 14, 54, 53, 46, 84, 62, 10, 64, 33, 32, 24, 89 8-ways nor 7, 21, 30, 54, 52, 99, 77, 85, 56, 28, 80, 17, 60, 60, 38, 68, 53, 80, 75, 85, 9 7-ways Manuel Kasten

on 2006-02-08 22:08

So it doesn't. But it says it won't split quickly! :) Do you have a solutions for these and list of other tests I could throw at it? Thanks, Bill

on 2006-02-08 22:19

Bill Dolinar wrote: > So it doesn't. But it says it won't split quickly! :) Do you have a > solutions for these and list of other tests I could throw at it? > >> 61, 63, 21, 87, 64, 84, 96, 35, 14, 74, 20, 62, 36, 64, 6, 14, 54, >> 53, 46, 84, 62, 10, 64, 33, 32, 24, 89 >> >> 8-ways 64 64 35 6 96 63 10 89 32 20 14 14 84 64 21 84 61 24 74 62 33 87 46 36 62 54 53 >> 7, 21, 30, 54, 52, 99, 77, 85, 56, 28, 80, 17, 60, 60, 38, 68, 53, >> 80, 75, 85, 9 >> >> 7-ways 80 75 7 99 54 9 85 60 17 60 53 28 21 80 52 30 68 56 38 85 77 If my solution is correct :) cheers Simon

on 2006-02-08 22:42

```
On Feb 8, 2006, at 3:19 PM, Simon Kröger wrote:
> If my solution is correct :)
I believe it is. I couldn't break it while writing the summary
anyway. ;)
James Edward Gray II
```

on 2006-02-10 01:35

Thanks. Helped me track down a fix... I think. :) How did you guys came up with all these difficult tests? Thanks, Bill On Feb 8, 2006, at 2:19 PM, Simon Kröger wrote: > 96 63 10 >>> 7-ways > > cheers > > Simon > =begin Here's my 2nd try. My last try missed one combination when backtracking. This time I tested it by writing code to go through all the possible combinations adding up to a given sum and number of partners, but it seems like it's the larger summed tests that find the bugs. I also changed the part that calculates the minimum number of elements in a combination to check, which made it faster than before. It's still lags a bit behind the speed of Manuel Kasten's solution. =end def split_equally(partners, a) a = a.sort total = a.inject {|sum, n| sum + n} # check for sum not multiple of partners return nil if total % partners != 0 split = total/partners # check for largest greater than split return nil if a.last > split if a.last == split # solution with last item return split_subset(partners, [a.last], a[0...(a.size-1)]) else sum = 0 min_elements = 2 (a.size-1).downto(0) do |i| sum += a[i] if sum >= split min_elements = [a.size - i, 2].max break end end max_elements = a.size/partners # search for solution with combinations of valid # elements (min_elements..max_elements).each do |items| combo = Combinations.new(a, a.size - items) begin more_combos, solution, leftover = find_one_split(split, combo, a) if (solution != nil && solution.compact != []) solution = split_subset(partners, solution, leftover) end if solution != nil && solution.compact != [] return solution end end while more_combos end end nil end # return solution for two partners or recurse back # to split_equally for more def split_subset(partners, solution, leftover) if partners == 2 return [leftover] + [solution] else leftover_solution = split_equally(partners - 1, leftover) if leftover_solution != nil return leftover_solution << solution end end nil end # look for one split by beginning with passed combination (missing # one item) and then working down def find_one_split(sum, combo, a) finished = false until finished first_item = combo.index_of(1) if first_item > 0 leftover = sum - combo.sum if leftover > a[first_item-1] combo.skip_smallest elsif a.first <= leftover matching = a[0..first_item].index(leftover) if matching != nil solution, leftover = combo.split(a, matching) more_combos = combo.next_smaller return more_combos, solution, leftover end end end finished = !combo.next_smaller end return false end class Combinations attr_accessor :bits attr_accessor :sum def initialize(a, max_zero) @bits = Array.new(a.size) {|i| i > max_zero ? 1 : 0} @a = a @sum = find_sum end def [](i) @bits[i] end def []=(i, value) if @bits[i] == 1 && value == 0 @sum -= @a[i] elsif @bits[i] == 0 && value == 1 @sum += @a[i] end @bits[i] = value end def index_of(value) i = @bits.index(value) end # next smaller combination with same number of items def next_smaller first_item = @bits.index(1) if first_item == 0 skipped = 0 @bits.each_with_index do |n, i| if n == 1 self[i] = 0 if i <= skipped skipped += 1 else self[i] = 0 (i-1).downto(i-1-skipped) {|i| self[i] = 1} return true end end end else self[first_item - 1] = 1 self[first_item] = 0 return true end return false end def skip_smallest first_item = @bits.index(1) self[first_item] = 0 self[0] = 1 end def split(a, index) i = -1 a.partition {|n| i += 1; @bits[i] == 1 || i == index;} end private def find_sum total = 0 @a.each_with_index {|n, i| total += n if @bits[i] != 0} total end end if __FILE__ == $0 a = ARGV.collect {|n| n.to_i} partners = a.shift split = split_equally(partners, a) if split == nil print "It is not possible to fairly split this treasure " print "#{partners} ways.\n" else split.each_with_index do |n,i| print "#{i}: ", n.join(" "), "\n" end end end