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.
on 2006-02-08 08:31
```=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 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```
This topic is locked and can not be replied to.