Settle Debts

Friends on a trip pay for each other. Payments are recorded as {payer, amount, payees}: the amount is split equally among the payees (the payer may be a payee). Amounts are integer cents; when the split isn't exact, the first amount mod len(payees) payees owe one cent extra.

Part 1 — settle(payments)

Compute everyone's net balance and return a list of transfers [from, to, amount] that settles all debts. Any valid settlement is accepted, but it must use at most n − 1 transfers for n people with a nonzero balance.

[ {payer: "alice", amount: 4000, payees: ["bob", "jess", "alice", "sam"]},
  {payer: "bob",   amount: 1000, payees: ["alice"]},
  {payer: "sam",   amount: 1000, payees: ["alice"]} ]
=> [["jess", "alice", 1000]]

Part 2 — minTransfers(debts)

Debts arrive as (debtor, creditor, amount) triples. Return the minimum number of transfers that settles everyone — around 20 people can carry a nonzero balance, and the general problem is NP-hard, so search with pruning is expected.

debts = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
=> 1

Worth asking out loud

Do the net balances have to sum to zero? (Yes — otherwise the input is inconsistent.) Who eats the remainder cent on an uneven split? Concrete transfers or just the count?