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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-03 16:21
(Received via mailing list)
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
C5ae4f9aa0d3a9bd5376e92b322c3e50?d=identicon&s=25 Aditya Mahajan (Guest)
on 2006-02-05 07: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
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-05 14:01
(Received via mailing list)
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.
2c51fec8183a5d21c4e11b430beabb47?d=identicon&s=25 Patrick Hurley (Guest)
on 2006-02-05 15:46
(Received via mailing list)
On 2/5/06, Luke Blanshard <luke@blanshard.us> 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.
7264fb16beeea92b89bb42023738259d?d=identicon&s=25 Christian Neukirchen (Guest)
on 2006-02-05 16:05
(Received via mailing list)
Patrick Hurley <phurley@gmail.com> 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?
6111b4012d1401ca83fdcea6b1d71237?d=identicon&s=25 Antonio Cangiano (Guest)
on 2006-02-05 16:29
(Received via mailing list)
Patrick Hurley 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
64b06c594bfa93f0326ba39a8c5538b4?d=identicon&s=25 Patrick Deuster (Guest)
on 2006-02-05 16: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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-05 16:59
(Received via mailing list)
On Feb 5, 2006, at 9:04 AM, Christian Neukirchen 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:

   suggestion@rubyquiz.com

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 Gray II

P.S.  Last week's quiz was not an NP-complete problem.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-05 17:02
(Received via mailing list)
On Feb 5, 2006, at 12:09 AM, Aditya Mahajan 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 Gray II
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-05 17:17
(Received via mailing list)
Patrick Deuster 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 Blanshard
0bd11e9521d2d8fc840d0b7e17ac7cd3?d=identicon&s=25 Manuel Kasten (Guest)
on 2006-02-05 17:54
(Received via mailing list)
=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
036384a0bea8469d33c24e5f3a50dab6?d=identicon&s=25 soxinbox (Guest)
on 2006-02-05 20: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 Quiz" <james@grayproductions.net> wrote in message
news:20060203152022.EJEN8318.centrmmtao04.cox.net@localhost.localdomain...
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-02-05 23:05
(Received via mailing list)
"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
E88cf6bd21b2ee52e271a44003312942?d=identicon&s=25 Chris Parker (Guest)
on 2006-02-06 00: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
Ff0452b8a10b2b671bbe9f788c20f84e?d=identicon&s=25 Stu Glaser (Guest)
on 2006-02-06 00: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
12271b6df73fe29930d65586be5a4a70?d=identicon&s=25 Dave Howell (Guest)
on 2006-02-06 00:57
(Received via mailing list)
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. :)
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-06 01:06
(Received via mailing list)
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. :)

The submission message you quoted explained the change.  :)

James Edward Gray II
6111b4012d1401ca83fdcea6b1d71237?d=identicon&s=25 Antonio Cangiano (Guest)
on 2006-02-06 02: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
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2006-02-06 04: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
64b06c594bfa93f0326ba39a8c5538b4?d=identicon&s=25 Patrick Deuster (Guest)
on 2006-02-06 07:19
(Received via mailing list)
Luke Blanshard 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 Deuster
A59b0b2fec8ccb513b2cf97f2d7659ac?d=identicon&s=25 Niklas Frykholm (Guest)
on 2006-02-06 10: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
82e62c756d89bc6fa0a0a2d7f2b1e617?d=identicon&s=25 Ross Bamford (Guest)
on 2006-02-06 10:20
(Received via mailing list)
On Mon, 06 Feb 2006 06:16:39 -0000, Patrick Deuster <pdeuster@gmx.net>
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...
6d5939d00e737621dad4582579780c6c?d=identicon&s=25 avi.bryant@gmail.com (Guest)
on 2006-02-06 11: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
7264fb16beeea92b89bb42023738259d?d=identicon&s=25 Christian Neukirchen (Guest)
on 2006-02-06 14:31
(Received via mailing list)
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. :)

But pirates are the chosen ones!
229d6af6e462c2a0caf445e0e92bfbd2?d=identicon&s=25 0x002A@gmail.com (Guest)
on 2006-02-06 16: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(" ")}"
	}
}
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-06 16:20
(Received via mailing list)
On Feb 6, 2006, at 3:18 AM, Ross Bamford 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 Gray 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
A9c4658e9e475e13d790ae419acf01b6?d=identicon&s=25 Simon Kröger (Guest)
on 2006-02-06 22: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
0bd11e9521d2d8fc840d0b7e17ac7cd3?d=identicon&s=25 Manuel Kasten (Guest)
on 2006-02-07 11:40
(Received via mailing list)
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.
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-07 13:28
(Received via mailing list)
Patrick Deuster wrote:
> 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".
>>> 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 Blanshard
64b06c594bfa93f0326ba39a8c5538b4?d=identicon&s=25 Patrick Deuster (Guest)
on 2006-02-07 14:45
(Received via mailing list)
Luke Blanshard 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 Blanshard
>
>
>
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
81d609425e306219d54d793a0ad98bce?d=identicon&s=25 Matthew Moss (Guest)
on 2006-02-07 16:39
(Received via mailing list)
On 2/7/06, Manuel Kasten <kasten.m@gmx.de> wrote:
> 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.

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....
0bd11e9521d2d8fc840d0b7e17ac7cd3?d=identicon&s=25 Manuel Kasten (Guest)
on 2006-02-08 18: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 Kasten
18ca239ffade6df0b839d26062f173fb?d=identicon&s=25 Dominik Bathon (Guest)
on 2006-02-08 23: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.