Forum: Ruby 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.
James G. (Guest)
on 2006-02-03 17:21
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. 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 T. 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 Q. 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
Aditya M. (Guest)
on 2006-02-05 08:10
(Received via mailing list)
> 	1:  9 12 32 34 49
> 	2:  14 17 23 40 42

Can one assume that the treasure values are only integers?

Aditya
Luke B. (Guest)
on 2006-02-05 15:01
(Received via mailing list)
Aditya M. 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.
Patrick H. (Guest)
on 2006-02-05 16:46
(Received via mailing list)
On 2/5/06, Luke B. <removed_email_address@domain.invalid> wrote:
> > Can one assume that the treasure values are only integers?
> I certainly hope so.
>
>

I just certainly hope there is not too many treasures, I am pretty
sure this is NP complete.
Christian N. (Guest)
on 2006-02-05 17:05
(Received via mailing list)
Patrick H. <removed_email_address@domain.invalid> writes:

>> >> ...
>> > Can one assume that the treasure values are only integers?
>> I certainly hope so.
>
> I just certainly hope there is not too many treasures, I am pretty
> sure this is NP complete.

Trying not to criticize the Quiz too harsh, but I think the amount of
NP-complete quizzes got pretty high... couldn't we have some quizzes
that can be solved without brute-forcing or heuristics?
Antonio C. (Guest)
on 2006-02-05 17:29
(Received via mailing list)
Patrick H. wrote:
> I just certainly hope there is not too many treasures, I am pretty
> sure this is NP complete.

It's the famous Subset Sum Problem (a special case of the knapsack
problem), and generally it's an NP-Complete problem.

Cheers,
Antonio
Patrick D. (Guest)
on 2006-02-05 17:41
(Received via mailing list)
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".
http://en.wikipedia.org/wiki/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
James G. (Guest)
on 2006-02-05 17:59
(Received via mailing list)
On Feb 5, 2006, at 9:04 AM, Christian N. wrote:

> Trying not to criticize the Quiz too harsh, but I think the amount of
> NP-complete quizzes got pretty high... couldn't we have some quizzes
> that can be solved without brute-forcing or heuristics?

Luckily, you, as a community, are 100% in control of this.  It's your
quiz, I just manage it:

   removed_email_address@domain.invalid

Personally, I agree with you, but it's hard to deny what is popular.
Take a look through the past quizzes and see what people tend to
submit most for...  ;)

James Edward G. II

P.S.  Last week's quiz was not an NP-complete problem.
James G. (Guest)
on 2006-02-05 18:02
(Received via mailing list)
On Feb 5, 2006, at 12:09 AM, Aditya M. wrote:

>> 	$ 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?

Yes, they are.

James Edward G. II
Luke B. (Guest)
on 2006-02-05 18:17
(Received via mailing list)
Patrick D. wrote:
> ...
> The splitting the loot problem is actually a problem known as the
> "Knapsack problem" or the "Subset sum problem".
> http://en.wikipedia.org/wiki/Subset_sum_problem
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 B.
Manuel K. (Guest)
on 2006-02-05 18:54
(Received via mailing list)
=begin ############################################################

Hello,
this is my first participation in a Ruby Q.. 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 K.

=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
soxinbox (Guest)
on 2006-02-05 21:31
(Received via mailing list)
#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 Q." <removed_email_address@domain.invalid> wrote in message
news:removed_email_address@domain.invalid...
Adam S. (Guest)
on 2006-02-06 00:05
(Received via mailing list)
"Ruby Q." <removed_email_address@domain.invalid> wrote in message
> This week's Ruby Q. 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 S.
#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
Chris Parker (Guest)
on 2006-02-06 01:35
(Received via mailing list)
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
Stu Glaser (Guest)
on 2006-02-06 01:47
(Received via mailing list)
Actually, it's more closely related to the Partition problem (which is
also NP-Complete).  (In fact, the 2-person instance is the Partition
problem).

Translation for the non-Computer Science: the problem cannot be solved
(exactly) without using a brute-force (slow) recursive-like algorithm.

-Stu
Dave H. (Guest)
on 2006-02-06 01:57
(Received via mailing list)
On Feb 5, 2006, at 8:53, Manuel K. wrote:
>   def initialize pirates, treasure

I'll just note that the original posting never said anything about
pirates. :)
James G. (Guest)
on 2006-02-06 02:06
(Received via mailing list)
On Feb 5, 2006, at 5:56 PM, Dave H. wrote:

>
> On Feb 5, 2006, at 8:53, Manuel K. wrote:
>>   def initialize pirates, treasure
>
> I'll just note that the original posting never said anything about
> pirates. :)

The submission message you quoted explained the change.  :)

James Edward G. II
Antonio C. (Guest)
on 2006-02-06 03:15
(Received via mailing list)
Stu Glaser wrote:
> Actually, it's more closely related to the Partition problem (which is
> also NP-Complete).  (In fact, the 2-person instance is the Partition
> problem).

Subset Sum and Partition problem are similar, I agree that this quiz is
closer to a Partition problem. However, if we consider the Subset Sum
problem: given a set of integers and an integer k, find a subset whose
sum is k? We can apply a subset sum algorithm to find the possible
subset that sums to the fair share for the first "pirate", and then work
in the same way on the remaining elements for the other pirates.

Cheers,
Antonio
Matthew M. (Guest)
on 2006-02-06 05:39
(Received via mailing list)
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
Patrick D. (Guest)
on 2006-02-06 08:19
(Received via mailing list)
Luke B. wrote:
>
>
>
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>."

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

Patrick D.
Niklas Frykholm (Guest)
on 2006-02-06 11:08
(Received via mailing list)
> Subset Sum and Partition problem are similar, I agree that this quiz
> is closer to a Partition problem. However, if we consider the Subset
> Sum problem: given a set of integers and an integer k, find a subset
> whose sum is k? We can apply a subset sum algorithm to find the
> possible subset that sums to the fair share for the first "pirate",
> and then work in the same way on the remaining elements for the other
> pirates.

Not without backtracking... suppose you have the treasures [1 2 3 4 5 6]
to be split among three pirates. If the subset sum algorithm finds the
treasures [1 2 4] for the first pirate it is impossible to divide the
remaining treasures [3 5 6] among the remaining two pirates even though
there exists a valid solution [1 6] [2 5] [3 4].

// Niklas
Ross B. (Guest)
on 2006-02-06 11:20
(Received via mailing list)
On Mon, 06 Feb 2006 06:16:39 -0000, Patrick D. 
<removed_email_address@domain.invalid>
wrote:

> 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>."
>
> I've solved this problem before, so I'm sure it's the subset sum problem.
>

(Total non-mathematician about to butt in)

I had a look at this quiz but didn't get chance to have a go, and
although
I originally figured it'd be a subset-sum thing, I realised that
everyone's share will be one of the partitions of (total / number of
guys), right? I ported a fast partition algorithm and was going to try
attacking it that way but I just didn't get the chance.

Something like,

	+ Quit if treasure_sum % guys != 0
	+ each = treasure_sum / guys
	+ parts = partition(each)
	+ have each guy try to take a partition from the treasure,
	  removing the taken treasure.

I think it gets problematic at that last step, because I think it's
possible for the first guy to take a combination that makes sure the
second guy can't be satisfied, while if the first guy had taken a
different combination (say, a 2 instead of two 1s) then guy two (needing
a
1) could have been satisfied. Maybe sorting the treasure would fix that
but I can't be certain.

Maybe not a good plan but it'd have been interesting to see if it
worked...
(Guest)
on 2006-02-06 12:54
(Received via mailing list)
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
Christian N. (Guest)
on 2006-02-06 15:31
(Received via mailing list)
Dave H. <removed_email_address@domain.invalid> writes:

> On Feb 5, 2006, at 8:53, Manuel K. wrote:
>>   def initialize pirates, treasure
>
> I'll just note that the original posting never said anything about
> pirates. :)

But pirates are the chosen ones!
(Guest)
on 2006-02-06 17:08
(Received via mailing list)
=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... :-)
=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(" ")}"
	}
}
James G. (Guest)
on 2006-02-06 17:20
(Received via mailing list)
On Feb 6, 2006, at 3:18 AM, Ross B. wrote:

> 	+ each = treasure_sum / guys
> 	+ parts = partition(each)
> 	+ have each guy try to take a partition from the treasure,
> 	  removing the taken treasure.

That's pretty much how I handled it.  Mine is really just an unrolled
recursive solution.

James Edward G. II

#!/usr/local/bin/ruby -w

class Array
   def without( other )
     result = dup
     other.each do |value|
       i = result.index(value) or next
       result.delete_at(i)
     end
     result
   end

   def sum
     inject { |sum, value| sum + value }
   end
end

def find_shares( target, treasures )
   shares = target.zero? ? [[target, Array.new, Array.new]] :
                           [[target, treasures.dup, Array.new]]

   until shares.empty?
     goal, pool, share = shares.pop
     first             = pool.shift

     shares << [goal, pool.dup, share.dup] unless pool.empty?
     if goal == first
       yield share + [first]
     elsif goal > first and not pool.empty?
       shares << [goal - first, pool.dup, share + [first]]
     end
   end
end

def divide_loot( target, treasures )
   total = treasures.sum

   return [treasures] if total == target

   unless (total % target).nonzero?
     loot = [[treasures.dup, Array.new]]

     until loot.empty?
       rest, divided = loot.pop

       find_shares(target, rest) do |share|
         new_rest  = rest.without(share)
         new_total = new_rest.sum

         if new_total == target
           return divided + [share, new_rest]
         elsif (new_total % target).zero?
           loot << [new_rest, divided.dup << share]
         end
       end
     end
   end

   nil
end

unless ARGV.size >= 2
   puts "Usage:  #{File.basename($PROGRAM_NAME)} ADVENTURERS TREASURES"
   exit
end
adventurers, *treasures = ARGV.map { |n| n.to_i }
target                  = treasures.sum / adventurers

if loot = divide_loot(target, treasures)
   loot.each_with_index do |share, index|
     puts "#{index + 1}: #{share.join(' ')}"
   end
else
   puts "It is not possible to fairly split this treasure #
{adventurers} ways."
end
Simon Kröger (Guest)
on 2006-02-06 23:50
(Received via mailing list)
Hi,

this is my solution. It first creates every possible combination of gems
that sums up to the right value in split_loot (multiplying the gems,
hehe, the magic of ruby?). choose_bags looks for a combination of bags
where each gem is only used once afterwards (discarding all the
multiplied gems - oooooh). choose_bags is recursive but has to deal only
with valid combinations of gems so i hope it is fast.

Ok, here it is:

--------------------------------------------------------------------
require 'set'

def choose_bags nr, bags, choice = Set[]
   return [] if choice.size == nr
   bags.each_with_index do |b, i|
     c = (choice & b).empty? && choose_bags(nr, bags, choice | b)
     return [i] + c if c
   end && nil
end

def split_loot  nr, *treasures
   each = (sum = treasures.sort!.reverse!.inject{|s, t| s + t}) / nr
   return nil if (sum % nr).nonzero?

   piles = Hash.new([]).merge!({0 => [[]]})
   treasures.each_with_index do |t, i|
     piles.dup.each do |k, v|
       if k + t <= each && k + sum >= each
         v.each{|a| piles[k + t] += [a + [i]]}
       end
     end
     sum -= t
   end
   return nil if piles[each].empty?
   return nil if !bags = choose_bags(treasures.size, piles[each])

   piles[each].values_at(*bags).map{|b| b.map{|t| treasures[t]}}
end

loot = split_loot(*ARGV.map{|p| p.to_i})
puts(loot ? loot.map{|a| a.join(' ')} : 'impossible!')
--------------------------------------------------------------------

cheers

Simon
Manuel K. (Guest)
on 2006-02-07 12:40
(Received via mailing list)
Matthew M. 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.
Luke B. (Guest)
on 2006-02-07 14:28
(Received via mailing list)
Patrick D. wrote:
> Luke B. wrote:
>> Patrick D. wrote:
>>> ...
>>> The splitting the loot problem is actually a problem known as the
>>> "Knapsack problem" or the "Subset sum problem".
>>> http://en.wikipedia.org/wiki/Subset_sum_problem
>> I don't believe that this problem is equivalent to the subset sum
>> problem, because all of the numbers involved are positive.  Different
>> animal.
> It is the subset sum problem. Read the description on the site:
Why yes, I did read it, thank you very much.  And of course you're
correct that it bears a strong resemblance to subset sum, and indeed
overlaps a special case of it.  However, I still say it's a different
animal, for two reasons:

1. The special case it overlaps with is not NP-complete.  If you have
all positive numbers, you can find a subset sum in O(n^2).

2. You aren't just finding a single subset.  You are partitioning the
set into a collection of equal subsets.  And since the special case is
not NP-complete, it is this partitioning that makes this problem hard.

Seems to me that this is a variant of a bin-packing problem with no
allowance for leftover space.

Luke B.
Patrick D. (Guest)
on 2006-02-07 15:45
(Received via mailing list)
Luke B. wrote:
>> It is the subset sum problem. Read the description on the site:
> not NP-complete, it is this partitioning that makes this problem hard.
>
> Seems to me that this is a variant of a bin-packing problem with no
> allowance for leftover space.
>
> Luke B.
>
>
>
Yes, you're right.
I realized that a few days ago and recoded my solution, because my first
one did just solve a simple subset problem and not the problem you
explained. :-)

Patrick
Matthew M. (Guest)
on 2006-02-07 17:39
(Received via mailing list)
On 2/7/06, Manuel K. <removed_email_address@domain.invalid> wrote:
> Matthew M. 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.

Yup, yer right, I noticed that couple of days ago, but I haven't had a
chance yet to make it work right.  Maybe later today....
Manuel K. (Guest)
on 2006-02-08 19:33
(Received via mailing list)
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.


Hi.

It doesn't split

72, 49, 83, 74, 65, 81, 92, 27, 58, 12, 97, 5, 8, 1, 38, 73, 6, 13, 29,
36, 83, 65, 95, 96, 89, 55, 43, 91

8-ways


nor


62, 93, 97, 85, 31, 2, 80, 83, 76, 54, 71, 70, 74, 42, 79, 7, 14, 66, 7,
100, 88, 68, 37, 99, 47, 51, 66, 23, 80

8-ways


Manuel K.
Dominik B. (Guest)
on 2006-02-09 00:46
(Received via mailing list)
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
This topic is locked and can not be replied to.