Forum: Ruby [SOLUTION] Splitting the Loot (#65) (My second attempt)

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.
64b06c594bfa93f0326ba39a8c5538b4?d=identicon&s=25 Patrick Deuster (Guest)
on 2006-02-06 15:20
(Received via mailing list)
I had a small chat with Manuel Kasten, who found out that my version
can't split all loots correctly.
For example, my old version didn't split

ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56
46

But it's possible to split this loot to:
1: 7 78 80
2: 30 45 90
3: 19 70 76
4: 46 54 65
5: 21 34 43 67
6: 19 20 56 70

Here's my second attempt. It should now split all loots correctly.
It now remembers splits that didn't result in a complete solution and
trys again.
I also added some comments, so it's easier to understand the code I use.

And because I had problems with Thunderbird wrapping the lines wrong I
attached my program to the email, too. Just in case ;)

----------------

class Array
  def sum
    inject { |s,x| s + x }
  end
  def delete_one! n
    (i = index(n)) ? delete_at(i) : nil
  end
  def count n
    inject(0) { |c,x| x == n ? c+1 : c }
  end
end

class Knapsack
   def initialize target, numbers, avoid=Array.new
     @target,@numbers,@avoid = target, numbers,avoid.compact.uniq
   end
   def solve
     solver @numbers.map { |n| [n] }
   end
   def solver paths
     new_paths = Array.new # New paths will be stored here
     paths.uniq.each do |path| # For each path do
       return path if path.sum == @target && (!@avoid.include?path) # If
it's a valid soulution and shouldn't be avoided return in
       @numbers.uniq.each do |n| # Add each number to the path
         # If we have numbers left to add to the path and the sum will
not get greater then the target we want
         if (path.count(n)<@numbers.count(n)) && (path.sum+n <= @target)
           # Store the new path in our new new_path array if it
shouldn't be avoided
           new_path = path.dup
           new_path << n
           unless @avoid.include?new_path
             new_paths << new_path unless new_path.sum == @target
             return new_path if new_path.sum == @target
           end
         end
       end
     end
     return nil if new_paths.empty? # We walked the whole tree and no
new path has been found, return nil
     solver new_paths # Launch again with the new paths
   end
end

def find_split fair_split,loot,avoid=Array.new
   current_loot = loot.dup # Remember the loot before a split has been
made
   stakes = Array.new
   # Try splitting the loot
   begin
     stake = Knapsack.new(fair_split,loot,avoid).solve
     stakes << stake
     stake.each { |s| loot.delete_one!(s) } unless stake.nil? # Remove
from the loot what has been found
   end until stake.nil? || loot.empty? # Loop until the loot is empty,
or the algorithm found no valid solution
   if loot.empty? # The whole loot is empty, a fair split has been found
     return stakes
   else
     if current_loot == loot # The algorithm splitted nothing, it's not
possible to fairly split the loot
       return nil
     else # The algorithm splitted something, but it wasn't correct. Try
again avoiding the already found solutions
      return find_split(fair_split,current_loot,stakes+avoid)
     end
   end
end

adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }

fair_split = loot.sum/adventures
stakes = (loot.sum%adventures).zero? ? find_split(fair_split,loot) : nil

if stakes.nil?
   puts "It is not possible to fairly split this treasure #{adventures}
ways."
else
   stakes.size.times { |i| puts "#{i+1}: " + stakes[i].sort.join(" ") }
end
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-02-06 20:00
(Received via mailing list)
On 2/6/06, Patrick Deuster <pdeuster@gmx.net> wrote:
> For example, my old version didn't split
>
> ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46

My turn to say 'Doh!'
I found a case where the greedy algorithms failed and mine passed, but
now Patrick has found one that mine fails.  But I have a simple 2 line
fix. I just need to move gems to my 'pile2' one at a time, instead of
a share-at-a-time.  I had considered doing this before, but managed to
convince myself it was slower and not needed.  Oops.

-Adam

##################################
#loot.rb
#Adam Shelly
#evenly splits an array into n sets of equal value

class Array
  def sum
    inject(0){|s,v| s+v}
  end
  def subtract arr
    return clear if arr==self
    arr.each{|e| if (n=index(e)) then delete_at(n); end }
    self
  end
 #fast version which misses some subsets.
  #useful as a rough filter.
  def quick_find_subset_with_sum n
    a = self.sort.reverse
    sum,set = 0,[]
    a.each {|e|
      if (sum+e <= n)
        sum+=e
        set<<e
        return set if sum == n
      end
    }
    nil
  end
  def find_subset_with_sum n
    s = quick_find_subset_with_sum n
    return s if s
    possibilities, seen  = [self.select{|e| e<=n}],{}
    until possibilities.empty?
      candidate = possibilities.pop
      diff = candidate.sum - n
      return candidate if diff == 0
      break if diff < 0
      candidate.each_with_index{|e,i|
        break if e > diff
        new_cand = (candidate.dup)
        new_cand.delete_at(i)
        return new_cand if e == diff
        possibilities << new_cand if !seen[new_cand]
        seen[new_cand]=true
      }
    end
    nil
  end
end


#1: put all loot in pile 1
#2: find  a share from pile 1
#3: if you can't find one, it can't be split
#4: find a share in the remaining gems
#5: repeat unitl you find all shares
#6: if you can't find enough shares
#7: move one item from the first share to pile2
#8: repeat starting from step 2,  include pile2 when searcing the
remainder in step 4
# this serves to shuffle the possible combinations.
# if all the gems are moved to pile2, there is no possible solution

def splitter n, loot
  splits=[]
  pile1,pile2=loot.dup.sort.reverse,[]
  total = loot.sum
  share = total/n
  return nil if total%n != 0 || loot.size < n || loot.max > share

  until pile1.empty?
    splits[0] = pile1.find_subset_with_sum(share)
    break if !splits[0]
    remaining = pile1.subtract(splits[0])+pile2
    (1...n).each do |i|
      break if nil == (splits[i] =
remaining.find_subset_with_sum(share))
      remaining.subtract(splits[i])
    end
    return splits if splits[n-1]
    #~ pile2 += splits[0]     ##This line changes to the following two
lines
    pile2 << splits[0].shift
    pile1 += splits[0]
  end
  return nil
end

if __FILE__ == $0

n = ARGV.shift.to_i
  if ARGV.size < 2 || n < 1
    puts "Usage: #{$0} partners item1 item2 ..."
  else
    shares = splitter(n, ARGV.map{|a| a.to_i })
    if !shares
      puts  "This loot can not be evenly divided into #{n} parts!"
    else
      shares.sort_by{|a|[a.size,-a.max]}.each_with_index{|share,i|
puts "#{i}: #{share.sort.reverse.join(' ')}"}
      puts "everyone gets #{shares[0].sum}"
    end
  end
end
0bd11e9521d2d8fc840d0b7e17ac7cd3?d=identicon&s=25 Manuel Kasten (Guest)
on 2006-02-08 14:44
(Received via mailing list)
Adam Shelly wrote:
> My turn to say 'Doh!'

Yet again. Your new version doesn't split

6-ways
26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52

possible solution:
1: [10, 39, 94]
2: [1, 52, 90]
3: [3, 51, 89]
4: [9, 20, 37, 77]
5: [15, 17, 34, 77]
6: [22, 22, 26, 26, 47]


Manuel Kasten
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-02-09 02:22
(Received via mailing list)
On 2/8/06, Manuel Kasten <kasten.m@gmx.de> wrote:
> Adam Shelly wrote:
> > My turn to say 'Doh!'
>
> Yet again. Your new version doesn't split
>
> 6-ways
> 26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52
>

Aargh.
How about this one:  here is a replacement splitter function - drop
into my last submission.
I added 2 more tests to detect unsplittable sets before I start
iterating, and I fixed the iterator to be sure it tests every
combination, and quits as soon as it finds a value which can not fit
into any fair share.  Oh, and I added one helper to Integer:

######################
class Integer
  def odd?
      self % 2 != 0
  end
end

def splitter n, loot
  splits=[]
  pile1,pile2=loot.dup.sort.reverse,[]
  total = loot.sum
  share = total/n
  num_odd = loot.inject(0){|s,g| g.odd? ? s+1 : s}

  # lots of ways to fail early:
  # doesn't divide evenly; not enough items; one item bigger than share
size;
  # the number of items worth more than 1/2 share must be < number of
shares
  # if the share size is even, there must be an even number of items
with odd values
  # if the share size is odd, there must be an even number plus one
for every share

  return nil if total%n != 0 || loot.size < n || loot.max > share
  return nil if loot.find_all{|g| g>share/2}.size > n
  num_odd-=n if share.odd?
  return nil if num_odd < 0 || num_odd.odd?

  #pile1 holds all the items we haven't tried to make a share with.
  #take a candidate from the pile.
  #if you can't make a share using that one, it is impossible to
divide the loot.
  #othewise, keep trying to make shares.
  #if you get stuck, move the candidate to pile2, and start again.
  #if pile1 becomes empty, give up

  until pile1.empty?
    candidate = pile1.shift
    remaining = (pile1+pile2)
    splits[0] = remaining.find_subset_with_sum(share - candidate)
    break if !splits[0]
    splits[0].unshift candidate
    (1...n).each do |i|
        break if nil == (splits[i] =
remaining.find_subset_with_sum(share))
        remaining.subtract(splits[i])
      end
      return splits if splits[n-1]
      pile2 << splits[0].shift
  end
  nil
end

######################
-Adam
0bd11e9521d2d8fc840d0b7e17ac7cd3?d=identicon&s=25 Manuel Kasten (Guest)
on 2006-02-09 13:28
(Received via mailing list)
Adam Shelly wrote:
>>
>
>
> Aargh.
> How about this one:  here is a replacement splitter function - drop
> into my last submission.
> I added 2 more tests to detect unsplittable sets before I start
> iterating, and I fixed the iterator to be sure it tests every
> combination, and quits as soon as it finds a value which can not fit
> into any fair share.  Oh, and I added one helper to Integer:

It doesn't split (46 69 88 119 130 159 208 233 242 396) 2-ways:

1: 88 119 242 396
2: 46 69 130 159 208 233

Manuel
This topic is locked and can not be replied to.