+ settle_list = []
+
+ while len(owes_list) > 0 and len(owed_list) > 0:
+ owes_list.sort(reverse=True, key=(lambda x: abs(x['amount'])))
+ owed_list.sort(reverse=True, key=(lambda x: abs(x['amount'])))
+
+ owes = owes_list[0]
+ owed = owed_list[0]
+
+ sum = owes['amount'] + owed['amount']
+ if sum == 0:
+ # Perfect balance!
+ owes_list.pop(0)
+ owed_list.pop(0)
+ val = owes['amount']
+ elif sum > 0:
+ # person in owes still owes money
+ owes['amount'] += owed['amount']
+ owed_list.pop(0)
+ val = -owed['amount']
+ else:
+ # person in owed is owed more than owes has to give
+ owed['amount'] += owes['amount']
+ owes_list.pop(0)
+ val = owes['amount']
+
+ settle_list.append((owes['who'], owed['who'], val))
+
+ if len(owes_list) > 0:
+ raise DirtyBooks, ("People still owe money", owes_list)
+ if len(owed_list) > 0:
+ raise DirtyBooks, ("People are still owed money", owed_list)
+
+ return settle_list
+
+__all__ = ['debts', 'settle']