[QUIZ] Splitting the Loot (#65)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

You, and your trusty band of adventurers, have stumbled upon a hidden cache of
rubies! (What luck, eh?) Not all gems are created equal, so you sneak them
home and take your time evaluating the stones. The find was an equal effort,
and you're all horribly greedy, so you must find a fair system for dividing up
the gems.

This week's Ruby Quiz is to write a program that fairly divides treasures, based
on worth.

The first command-line argument to the program will be the number of adventures.
All other arguments are the numerical values of treasures found. You're program
should output a fair split of the treasures, if possible, or a warning message
if a fair split cannot be found.

Examples:

  $ ruby loot.rb 3 1 2 3 4
  It is not possible to fairly split this treasure 3 ways.
  $ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
  1: 9 12 32 34 49
  2: 14 17 23 40 42

2

The first command-line argument to the program will be the number of adventures.
All other arguments are the numerical values of treasures found. You're program
should output a fair split of the treasures, if possible, or a warning message
if a fair split cannot be found.

Examples:

  $ ruby loot.rb 3 1 2 3 4
  It is not possible to fairly split this treasure 3 ways.
  $ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
  1: 9 12 32 34 49
  2: 14 17 23 40 42

Can one assume that the treasure values are only integers?

Aditya

···

--
Aditya Mahajan, EECS Systems, University of Michigan
http://www.eecs.umich.edu/~adityam || Ph: 7342624008

3

Ok, the 48 hours passed just now and as I have to leave for a day or two I post my solution early.

The splitting the loot problem is actually a problem known as the "Knapsack problem" or the "Subset sum problem".

I solved the problem how I learned it at university, by walking through a tree.
I hand the loot and the target value over to the knapsack solver and remove the result from the loot until either the loot is empty or solving the problem failed.

Here's my complete solution:

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
    @target,@numbers = target, numbers
  end
  def solve
    solver @numbers.map { |n| [n] }
  end
  def solver paths
    new_paths = Array.new
    paths.each do |path|
      return path if path.sum == @target
      @numbers.each do |n|
        unless path.count(n)>=@numbers.count(n) || path.sum+n > @target
          new_path = path.dup
          new_path << n
          new_paths << new_path
          return new_path if new_path.sum == @target
        end
      end
    end
    return nil if new_paths.empty?
    solver new_paths
  end
end

adventures,loot = ARGV.shift.to_i,ARGV.map { |a| a.to_i }
fair_split,stakes = loot.sum/adventures,Array.new

begin
  stake = Knapsack.new(fair_split,loot).solve
  stakes << stake
  stake.each { |s| loot.delete_one!(s) } unless stake.nil?
end until stake.nil? || loot.empty?

if stakes.include?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

4

=begin ############################################################

Hello,
this is my first participation in a Ruby Quiz. I used a simple
recursive algorithm, so don't expect speed wonders from this one.
I'm sure there are faster and more elegant solutions out there.
Nevertheless, I had fun implementing this.
Oh, and I swapped the adventurers for pirates, because they gave
me a headache spelling them. (adventurerers, adventurererer.. ?)

Manuel Kasten

=end ############################################################

class SplitIt
   def initialize pirates, treasure
     @pirates = pirates
     @treasure = treasure
     @bags = []
     (0...@pirates).each{ |pirate| @bags[pirate] = [[], 0] }
     loot = @treasure.inject(0){ |res, gem| res + gem }
     done unless loot % @pirates == 0
     @share = loot/@pirates
   end
   def go
     done if @treasure.length == 0
     gem = @treasure.pop
     (0...@pirates).each do |pirate|
       if @bags[pirate][1] + gem <= @share
         @bags[pirate][1] += gem
         @bags[pirate][0].push gem
         go
         @bags[pirate][0].pop
         @bags[pirate][1] -= gem
         # it doesn't matter which pirate is which,
         # as long as their bags are empty
         break if @bags[pirate][1] == 0
       end
     end
     @treasure.push gem
   end
   def done
     puts
     if (@treasure.length == 0)
       @bags.each_with_index do |bag, pirate|
         puts "#{pirate+1}: #{bag[0].sort.inspect}"
       end
     else
       puts "The #{@pirates} pirates won't be able to " +
            "split their loot fairly. Take cover!"
     end
     exit
   end
end

if $0 == __FILE__
   pirates = ARGV.shift.to_i
   treasure = ARGV.map{ |gem| gem.to_i }.sort
   si = SplitIt.new(pirates, treasure)
   si.go
   si.done
end

5

#booty
class Array
  def sum
    inject(0){|v,e| v += e.to_i}
  end
end
class PileOfBooty
  attr :sum
  def initialize
    @sum = 0
    @pile =
  end
  def add(i)
    @sum += i.to_i
    @pile << i.to_i
  end
  def rem
    r = @pile.pop
    @sum -= r
    r
  end
  def sort!
    @pile.sort!
  end
end

def sumit(piles,treasure,divy)
  if treasure.sum == 0
    return piles
  else
    ruby = treasure.rem
    piles.size.times{|i| #try adding the ruby to each pirate's pile in
turn
      piles[i].add ruby #add the ruby to the this pile
      if piles[i].sum <= divy and sumit(piles,treasure,divy) != nil
        return (piles) #that worked ok, now divy up the rest of the booty
      else
        piles[i].rem #that didn't work, take the ruby back
      end
    }
    treasure.add ruby #couldn't find a soultion from here, put the ruby
back in the booty pile and return nil
    return nil
  end
end
def dumpit ( piles,n )
    print "\n\n"
  if piles == nil
    print "It bees not possible to divy the booty amongst #{n} pirates,
ARRRGH!\n"
  else
    piles.each_index{|i|
      piles[i].sort!
      print "#{i}:"
      print " #{piles[i].rem}" while piles[i].sum != 0
      print "\n"
    }
  end
end

n=ARGV.shift.to_i #number of pirates
treasure = PileOfBooty.new
ARGV.each{|e| treasure.add e} #collection of rubys to divy up
divy = treasure.sum/n #each pirate's share
piles =
n.times{piles << PileOfBooty.new} #a pile of booty for each pirate
dumpit( sumit(piles,treasure,divy) ,n)

"Ruby Quiz" <james@grayproductions.net> wrote in message
news:20060203152022.EJEN8318.centrmmtao04.cox.net@localhost.localdomain...

···

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

You, and your trusty band of adventurers, have stumbled upon a hidden
cache of
rubies! (What luck, eh?) Not all gems are created equal, so you sneak
them
home and take your time evaluating the stones. The find was an equal
effort,
and you're all horribly greedy, so you must find a fair system for
dividing up
the gems.

This week's Ruby Quiz is to write a program that fairly divides treasures,
based
on worth.

The first command-line argument to the program will be the number of
adventures.
All other arguments are the numerical values of treasures found. You're
program
should output a fair split of the treasures, if possible, or a warning
message
if a fair split cannot be found.

Examples:

$ ruby loot.rb 3 1 2 3 4
It is not possible to fairly split this treasure 3 ways.
$ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
1: 9 12 32 34 49
2: 14 17 23 40 42

6

My solution... very simple, recursive, no optimizations...

class Numeric
   def positive?
      self > 0
   end
end

class Array
   def tail
      self[1..-1]
   end

   def sum
      inject { |s, k| s + k }
   end

   def find_sum(n)
      if not empty? and n.positive?
         if n == first
            return [first]
         else
            sub = tail.find_sum(n - first)
            return [first] + sub unless sub.nil?
            return tail.find_sum(n)
         end
      end
      nil
   end
end

guys = ARGV.shift.to_i
loot = ARGV.map { |i| i.to_i }.sort

total = loot.sum

unless (total % guys).zero?
   puts "It is not possible to fairly split this treasure #{guys} ways."
else
   share = total / guys

   shares = []
   guys.times do |i|
      mine = loot.find_sum(share)
      unless mine.nil?
         mine.each { |k| loot.delete_at(loot.index(k)) }
         shares << mine
      end
   end

   if shares.size == guys
      shares.each_with_index do |s, i|
         puts "#{i}: #{s.join(' ')}"
      end
   else
      puts "It is not possible to fairly split this treasure #{guys} ways."
   end
end

7

=begin
my solution was inspired by a lecture about scheme/lisp streams. the
possible-solution space is searched in a quite stupid manner which
makes it kind of slow... :slight_smile:
=end

require 'lazylist'

pirates = ARGV.shift.to_i
loot = ARGV.map {|x| x.to_i}

# this computes _all_ solutions (but does so lazyly)
# also this doesn't check for equivalent solutions, but we don't care
# since only the first solution is computed and printed
LazyList[1 ... pirates**loot.size].map {|owners|
  # owners encodes a way to give each pirate a subset of the loot
  # (as a number of base "pirates")
  bags = Array.new(pirates) {[]}
  idx = loot.size - 1
  begin
    owners, owner = owners.divmod(pirates)
    bags[owner] << loot[idx]
    idx -= 1
  end while owners > 0
  idx.downto(0) do |i|
    bags[0] << loot[i]
  end
  bags
}.map {|splitting|
  # now map to the sums
  puts "computed sums for #{splitting.inspect}"
  [splitting, splitting.map {|pieces| pieces.inject(0) {|s,p| s +
  p}}]
}.select {|splitting, sums|
  # are all sums the same?
  sums.uniq.length == 1
}.map {|splitting, sums|
  # forget the sums
  splitting
}.take.each {|splitting|
  # take the first solution and just output it
  splitting.each_with_index {|pieces, owner|
    puts " #{owner+1}: #{pieces.sort.join(" ")}"
  }
}

8

Here is my solution.

It first sorts the gems by value and then, tries to split them recursively. The sorting is not necessary for split_loot to work, but it works much faster on sorted sets.

If only a number of adventurers and no loot is given, then a random loot is generated.

Dominik

def split_loot(cnt, gems, first_call = true)
   return [gems] if cnt == 1
   sum = gems.inject(0) { |s, n| s + n }
   share = sum / cnt
   if first_call
     # only do these checks once
     if sum % share != 0 || gems.max > share || gems.empty?
       raise "impossible"
     end
   end
   # search all subsets of the gems whose sum is share, for each try to
   # split the remaining loot into cnt - 1 parts
   choose_stack = [0]
   share_sum = gems.first
   last = gems.size - 1
   until choose_stack.empty?
     while share_sum < share && choose_stack.last < last
       choose_stack << choose_stack.last + 1
       share_sum += gems[choose_stack.last]
     end
     if share_sum == share
       # recursive call
       rest_gems = gems.values_at(*((0...gems.size).to_a - choose_stack))
       if (res = split_loot(cnt - 1, rest_gems, false) rescue nil)
         return (res << gems.values_at(*choose_stack))
       end
     end
     if choose_stack.last == last
       share_sum -= gems[last]
       choose_stack.pop
     end
     unless choose_stack.empty?
       share_sum -= gems[choose_stack.last]
       choose_stack << choose_stack.pop + 1
       share_sum += gems[choose_stack.last]
     end
   end
   raise "impossible"
end

if $0 == __FILE__
   begin
     if ARGV.size >= 2
       cnt, *gems = ARGV.map { |s| Integer(s) }
     else
       # generate a test
       cnt = ARGV.shift.to_i
       share_sum = rand(1000)
       gems = []
       cnt.times {
         rest = share_sum
         while rest > 0
           cur = rand(rest) + 1
           gems << cur
           rest -= cur
         end
       }
     end
     split_loot(cnt, gems.sort.reverse).each_with_index { |s, i|
       puts "#{i+1}: #{s.join(' ')}"
     }
   rescue => e
     puts e
   end
end

9

Aditya Mahajan wrote:

The first command-line argument to the program will be the number of adventures.
All other arguments are the numerical values of treasures found. You're program
should output a fair split of the treasures, if possible, or a warning message
if a fair split cannot be found.

...

Can one assume that the treasure values are only integers?

I certainly hope so.

10

Yes, they are.

James Edward Gray II

···

On Feb 5, 2006, at 12:09 AM, Aditya Mahajan wrote:

The first command-line argument to the program will be the number of adventures.
All other arguments are the numerical values of treasures found. You're program
should output a fair split of the treasures, if possible, or a warning message
if a fair split cannot be found.

Examples:

  $ ruby loot.rb 3 1 2 3 4
  It is not possible to fairly split this treasure 3 ways.
  $ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
  1: 9 12 32 34 49
  2: 14 17 23 40 42

Can one assume that the treasure values are only integers?

11

Patrick Deuster wrote:

...
The splitting the loot problem is actually a problem known as the "Knapsack problem" or the "Subset sum problem".
Subset sum problem - Wikipedia

I don't believe that this problem is equivalent to the subset sum problem, because all of the numbers involved are positive. Different animal.

Luke Blanshard

12

"Ruby Quiz" <james@grayproductions.net> wrote in message

This week's Ruby Quiz is to write a program that fairly divides treasures,
based on worth.

Here's mine. I reused several methods from the wierd numbers quiz.

···

#############################################
#loot.rb
#Adam Shelly
#evenly splits an array into N parts with equal value , if possible

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

# Splitter algorithm
#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 pile
#5: repeat unitl you find all shares
#6: if you can't find enough shares
#7: move the first share to pile2
#8: repeat from step 2, but add pile2 to the remainder in step 4
# this serves to shuffle the possible combinations, until you find one
that works.

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]
  end
  return nil
end

if __FILE__ == $0

  if ARGV.size < 2 || ARGV[0].to_i < 1
    puts "Usage: #{$0} partners item1 item2 ..."
  else
    shares = splitter(ARGV.shift.to_i, ARGV.map{|a| a.to_i })
    if !shares
      puts "This loot can not be evenly divided into #{n} parts!"
    else
      shares.each_with_index{|share,i| puts "#{i}: #{share.join(' ')}"}
      puts "everyone gets #{shares[0].sum}"
    end
  end

end

#############################################

-Adam

13

Here is my solution. It is short and simple. I take advantage of the
fact that for there to be an answer, every treasure must be used, so a
greedy algorithm that tries the highest valued treasures first works
well.

···

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

class Array
  def delete_one(item)
    return unless include?(item)
    index = nil
    self.each_with_index{|elem,index|break if elem == item}
    delete_at(index)
  end

  def delete_set(arry_to_delete)
    arry_to_delete.each{|elem| self.delete_one(elem)}
  end
end

def subset_sum(set, goal)
  return nil if set == [] and goal != 0
  return [] if goal == 0
  if goal >= set[0]
    ret_val = subset_sum(set[1..-1],goal - set[0])
    return ret_val << set[0] if ret_val != nil
  end
  return subset_sum(set[1..-1],goal)
end

if ARGV.length < 2
  print "Invalid arguments\n#{__FILE__} #adventurers list of booty\n"
  exit
end

num_people = ARGV[0].to_i

treasures = []
ARGV[1..-1].each do |num_string|
  treasures << num_string.to_i
end

total_treasure = treasures.inject(0){|sum, i| sum + i}

if total_treasure % num_people != 0 || num_people > treasures.length ||
treasures.max > total_treasure / num_people
  print "impossible to split treasure equally"
  exit
end

treasures = treasures.sort.reverse
num_people.times do |i|
  subset = subset_sum(treasures, total_treasure / num_people)
  if subset == nil
    print "can't split treasure evenly\n"
    exit
  else
    print "pirate #{i}: got #{subset.inject(""){|string, num|string
+num.to_s+" "}}\n"
  end
  treasures.delete_set(subset)
end

14

I'll just note that the original posting never said anything about pirates. :slight_smile:

···

On Feb 5, 2006, at 8:53, Manuel Kasten wrote:

  def initialize pirates, treasure

15

Matthew Moss wrote:
> My solution... very simple, recursive, no optimizations...

Hello.
Well, your solution doesn't split [34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46] 6-ways. The problem is that you can find a combination of gems that sum up to the correct value, but make it impossible to complete the split, whereas if you had chosen another combination, the split would have been possible.

  Manuel

···

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

madonion@gentoo $ ruby Matthew\ Moss.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46

It is not possible to fairly split this treasure 6 ways.

16

I just certainly hope there is not too many treasures, I am pretty
sure this is NP complete.

···

On 2/5/06, Luke Blanshard <luke@blanshard.us> wrote:

Aditya Mahajan wrote:
>> The first command-line argument to the program will be the number of
>> adventures.
>> All other arguments are the numerical values of treasures found.
>> You're program
>> should output a fair split of the treasures, if possible, or a
>> warning message
>> if a fair split cannot be found.
>>
>> ...
> Can one assume that the treasure values are only integers?
I certainly hope so.

17

The submission message you quoted explained the change. :slight_smile:

James Edward Gray II

···

On Feb 5, 2006, at 5:56 PM, Dave Howell wrote:

On Feb 5, 2006, at 8:53, Manuel Kasten wrote:

  def initialize pirates, treasure

I'll just note that the original posting never said anything about pirates. :slight_smile:

18

Luke Blanshard wrote:

Patrick Deuster wrote:

...
The splitting the loot problem is actually a problem known as the "Knapsack problem" or the "Subset sum problem".
Subset sum problem - Wikipedia

I don't believe that this problem is equivalent to the subset sum problem, because all of the numbers involved are positive. Different animal.

Luke Blanshard

It is the subset sum problem. Read the description on the site:

"An equivalent problem is this: given a set of integers and an integer /s/, does any subset sum to /s/? Subset sum can also be thought of as a special case of the knapsack problem <http://en.wikipedia.org/wiki/Knapsack_problem&gt;\.&quot;

I've solved this problem before, so I'm sure it's the subset sum problem.

Patrick Deuster

19

Chris Parker wrote:

Here is my solution. It is short and simple. I take advantage of the
fact that for there to be an answer, every treasure must be used, so a
greedy algorithm that tries the highest valued treasures first works
well.

Unfortunately there are cases where the greedy algorithm fails. Try
this set of arguments:

3 3 3 3 2 2 2 2 2 2 2 2 2

The correct answer is:

1: 3 2 2 2
2: 3 2 2 2
3: 3 2 2 2

But the greedy algorithm get stuck at:

1: 3 3 3

Cheers,
Avi

20

Dave Howell <groups@grandfenwick.net> writes:

···

On Feb 5, 2006, at 8:53, Manuel Kasten wrote:

  def initialize pirates, treasure

I'll just note that the original posting never said anything about
pirates. :slight_smile:

But pirates are the chosen ones!

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org