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

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Bill Dolinar (Guest)
on 2006-02-08 09:31
(Received via mailing list)
=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
Manuel K. (Guest)
on 2006-02-08 19:39
(Received via mailing list)
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.
Bill Dolinar (Guest)
on 2006-02-08 23:08
(Received via mailing list)
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
Simon Kröger (Guest)
on 2006-02-08 23:19
(Received via mailing list)
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
James G. (Guest)
on 2006-02-08 23:42
(Received via mailing list)
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 G. II
Bill Dolinar (Guest)
on 2006-02-10 02:35
(Received via mailing list)
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 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 [](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
This topic is locked and can not be replied to.