Re: [QUIZ][SOLUTION] Splitting the Loot (#65)

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



.

Relevant Pages