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

on 2006-02-03 16:21

on 2006-02-05 07:10

> 1: 9 12 32 34 49 > 2: 14 17 23 40 42 Can one assume that the treasure values are only integers? Aditya

on 2006-02-05 14:01

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.

on 2006-02-05 15:46

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.

on 2006-02-05 16:05

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?

on 2006-02-05 16:29

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

on 2006-02-05 16:41

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

on 2006-02-05 16:59

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.

on 2006-02-05 17:02

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

on 2006-02-05 17:17

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

on 2006-02-05 17:54

=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

on 2006-02-05 20:31

#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...

on 2006-02-05 23:05

"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

on 2006-02-06 00:35

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

on 2006-02-06 00:47

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

on 2006-02-06 00:57

```
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. :)
```

on 2006-02-06 01:06

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

on 2006-02-06 02:15

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

on 2006-02-06 04:39

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

on 2006-02-06 07:19

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

on 2006-02-06 10:08

> 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

on 2006-02-06 10:20

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...

on 2006-02-06 11:54

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

on 2006-02-06 14:31

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!

on 2006-02-06 16:08

=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(" ")}" } }

on 2006-02-06 16:20

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

on 2006-02-06 22:50

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

on 2006-02-07 11:40

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.

on 2006-02-07 13:28

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

on 2006-02-07 14:45

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

on 2006-02-07 16:39

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....

on 2006-02-08 18:33

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

on 2006-02-08 23:46

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