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

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

TXkgc29sdXRpb24gaXMgYXR0YWNoZWQuICBJdCBzb2x2ZXMgdmlhIHJlY3Vyc2lvbiB3aXRoIGEg
ZmV3Cm9wdGltaXphdGlvbnMgKGl0IGlzIHN0aWxsIHJlYWxseSBzbG93LCB0aG91Z2gpCgogKiBp
dCBjaGVja3MsIGlmIHRoZSBzdW0gb2YgYWxsIHBpZWNlcyBpcyBkaXZpc2FibGUgYnkgdGhlIG51
bWJlciBvZiBwZXJzb25zLAogICBpZiBub3QsIHRoZW4gdGhlcmUgaXMgbm8gc29sdXRpb24uCiAq
IGl0IGF2b2lkcyBnaXZpbmcgZXZlcnkgcGllY2UgdG8gdGhlIGZpcnN0IHBlcnNvbiBhdCB0aGUg
YmVnaW5uaW5nCgpUd28gaW50ZXJlc3RpbmcgbWV0aG9kcyBJIHVzZWQ6CgogIG1vZHVsZSBFbnVt
ZXJhYmxlCiAgICBkZWYgYWxsX2VxdWFsPwogICAgICBzZWxmLmluamVjdCB7IHxhLGJ8IGJyZWFr
IGZhbHNlIHVubGVzcyBhID09IGI7IGIgfSAhPSBmYWxzZSB9CiAgICBlbmQKICBlbmQKICBbMywz
LDMsM10uYWxsX2VxdWFsPyAjPT4gdHJ1ZQoKICBjbGFzcyBPYmplY3QKICAgIGRlZiBpZl9mYWxz
ZTsgc2VsZiA/IHNlbGYgOiB5aWVsZDsgZW5kOwogIGVuZAoKVGhpcyB3b3JrcyBuaWNlbHkgZm9y
IEVudW1lcmFibGUjZmluZDoKCiAgWzEsMiwzLDQsNV0uZmluZCB7fHh8IHggPiAxMH0uaWZfZmFs
c2UgeyB3YXJuICJub3RoaW5nIGZvdW5kIjsgLTEgfSAjPT4gLTEKCi1MZXZpbgo=
------=_Part_24293_8967625.1139164490340
Content-Type: application/octet-stream; name=q65_levin_alexander.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_ejboxomp
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 LootDistributor
  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
    
    distribute(0, sums, dist, @pieces, &blk)
  end
  
  private
  
  def distribute(depth, sums,dist,remaining_pieces,&blk)
    if remaining_pieces.empty? 
      yield dist if sums.all_equal?
    else
      first_piece, rest = remaining_pieces.first, remaining_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)
  
        # 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)

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

end


------=_Part_24293_8967625.1139164490340--