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


#1

=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
@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


#2

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 K.


#3

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

Thanks,
Bill


#4

Bill Dolinar wrote:

So it doesn’t. But it says it won’t split quickly! :slight_smile: 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 :slight_smile:

cheers

Simon


#5

On Feb 8, 2006, at 3:19 PM, Simon Kröger wrote:

If my solution is correct :slight_smile:

I believe it is. I couldn’t break it while writing the summary
anyway. :wink:

James Edward G. II


#6

Thanks. Helped me track down a fix… I think. :slight_smile: 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 K.'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
@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