From: soxinbox <faker@...>
Date: 2006-02-06T04:28:20+09:00
Subject: Re: [QUIZ] Splitting the Loot (#65)


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

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

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



"Ruby Quiz" <james@grayproductions.net> wrote in message 
news:20060203152022.EJEN8318.centrmmtao04.cox.net@localhost.localdomain...
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz 
> until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps 
> everyone
> on Ruby Talk follow the discussion.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> You, and your trusty band of adventurers, have stumbled upon a hidden 
> cache of
> rubies!  (What luck, eh?)  Not all gems are created equal, so you sneak 
> them
> home and take your time evaluating the stones.  The find was an equal 
> effort,
> and you're all horribly greedy, so you must find a fair system for 
> dividing up
> the gems.
>
> This week's Ruby Quiz is to write a program that fairly divides treasures, 
> based
> on worth.
>
> The first command-line argument to the program will be the number of 
> adventures.
> All other arguments are the numerical values of treasures found.  You're 
> program
> should output a fair split of the treasures, if possible, or a warning 
> message
> if a fair split cannot be found.
>
> Examples:
>
> $ ruby loot.rb 3 1 2 3 4
> It is not possible to fairly split this treasure 3 ways.
> $ ruby loot.rb 2 9 12 14 17 23 32 34 40 42 49
> 1:  9 12 32 34 49
> 2:  14 17 23 40 42
>
>