Bill Dolinar
2/10/2006 12:36:00 AM
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:
> 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
>
=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