Redistribution of winnings

redistribute.py

# Redistribute the PolyHack winnings:


# Returns list of all the people who need money, and all who have too much
# in the form of (receivers, givers)
def findCreditorsDebtors(allocs, desiredAllocs):
  receivers, givers = [], []
  for person,amt in allocs.iteritems():
    desired = desiredAllocs[person]
    if amt < desired:
      receivers.append(person)
    elif amt > desired:
      givers.append(person)

  return receivers, givers

def redistribute(totalSum, initialAllocs, desiredAllocs):
  reapportionments = {} # source -> (dest -> amount) i.e. "source pays dest $amount"

  balances = dict(initialAllocs)

  receivers, givers = findCreditorsDebtors(initialAllocs, desiredAllocs)

  for person in givers: # Iterate over people who have too much money
    package = 1 
    targets = reapportionments.get(person, {})
    
    # while there's still money to reapportion and there are still people
    # needing money, reapportion that over the people
    while package > 0 and receivers:
      package = balances[person] - desiredAllocs[person]
      target = receivers.pop()

      delta = desiredAllocs[target] - balances[target]
      reapp = min(delta,package) # reapportion delta up to package
      balances[person] -= reapp
      balances[target] += reapp

      amt = targets.get(target, 0.0)
      targets[target] = amt + reapp

      # This should be equiv. to delta > package
      if balances[target] < desiredAllocs[target]:
        receivers.append(target) # we're not done yet with this guy

    reapportionments[person] = targets

  print balances
  return reapportionments

if __name__ == '__main__':
  winnings = 1000.0 # prize winnings
  desiredAllocs = {"Chris":275.0, "Arun":275.0, "Sam":125.0, "Josh":100.0, "Deanna":75.0, "Vincent":75.0, "Tony":75.0, "Lexie":0.0, "Tess":0.0}
  numPeople = len(desiredAllocs)

  initialAllocs = {}
  for name,_ in desiredAllocs.iteritems():
    initialAllocs[name] = winnings/numPeople

  reapps = redistribute(winnings, initialAllocs, desiredAllocs)

  for name,targets in reapps.iteritems():
    for target,amount in targets.iteritems():
      print name + " pays " + target + " $" + str(amount)