From: Levin Alexander <levin@...>
Date: 2006-02-06T19:13:21+09:00
Subject: Re: [/QUIZ] #65: Splitting the Loot

------=_Part_30716_27334839.1139220787641
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: base64
Content-Disposition: inline

T24gMi81LzA2LCBMZXZpbiBBbGV4YW5kZXIgPGxldmluQGdydW5kZWlzLm5ldD4gd3JvdGU6Cj4g
TXkgc29sdXRpb24gaXMgYXR0YWNoZWQuICBJdCBzb2x2ZXMgdmlhIHJlY3Vyc2lvbiB3aXRoIGEg
ZmV3Cj4gb3B0aW1pemF0aW9ucyAoaXQgaXMgc3RpbGwgcmVhbGx5IHNsb3csIHRob3VnaCkKCkhl
cmUgaXMgYW4gdXBkYXRlZCB2ZXJzaW9uIHRoYXQgc3RvcHMgcmVjdXJzaW5nLCBpZiBzb21lb25l
IGdldHMKYXNzaWduZWQgbW9yZSB0aGFuIGhpcyBzaGFyZS4gIChJIGNhbiBub3QgKmJlbGlldmUq
IHRoYXQgSSBkaWQgbm90CnRoaW5rIG9mIHRoaXMgZWFybGllcikgIFRoaXMgc3BlZWRzIGV2ZXJ5
dGhpbmcgdXAgcXVpdGUgYSBsb3QuCgotTGV2aW4K
------=_Part_30716_27334839.1139220787641
Content-Type: application/octet-stream; name=q65_levin_alexander.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_ejcmjehn
Content-Disposition: attachment; filename="q65_levin_alexander.rb"

# 
# Rubyquiz #65 (Splitting the Loot)
# Levin Alexander <levin@grundeis.net>
#

module Enumerable
  def sum; inject { |a,b| a+b } end

  def all_equal?
    inject { |a,b| break false unless a == b; b } != false
  end
end

class Object
  def if_false
    self ? self : yield
  end
end

class Symbol
  def to_proc; proc { |obj| obj.send(self) }; end
end

class Array
  def rest; self[1..-1]; end
end

class Distributor
  include Enumerable

  def initialize(persons, pieces)
    @pieces = pieces.sort.reverse # distribute big pieces first
    @persons = persons
  end

  def each(&blk)
    dist = Array.new(@persons) { [] }
    sums = Array.new(@persons) { 0 } # avoid recalculating the sums

    # special case
    return unless (@pieces.sum % @persons) == 0
    
    @expected = @pieces.sum / @persons
    
    distribute(0, sums, dist, @pieces, &blk)
  end
  
  private
  
  def distribute(depth, sums,dist,pieces,&blk)
    if pieces.empty? 
      yield dist if sums.all_equal?
    else
      first_piece, rest = pieces.first, pieces.rest
        
      (0...@persons).each { |p|
        # start with a different person at every turn so that we 
        # don't end up giving everything to the first guy
        # in the beginning
        # 
        p = (p+depth) % @persons

        dist[p].push first_piece
        sums[p] += first_piece

        # recursively distribute the rest
        # 
        distribute(depth+1, sums, dist, rest, &blk) unless sums[p] > @expected
  
        # undo everything.  This avoids having to duplicate the arrays
        # 
        dist[p].pop
        sums[p] -= first_piece
      }
    end
  end
end

if __FILE__ == $0
  
  persons = ARGV.shift.to_i
  loot = ARGV.map(&:to_i)

  Distributor.new(persons, loot).find { |dist|
      dist.each_with_index { |pieces,person|
      puts "#{person+1}: #{pieces.join(' ')}"
    }
  }.if_false {
    warn "It is not possible to fairly split this treasure #{persons} ways"
  }

end

------=_Part_30716_27334839.1139220787641--