CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 6 min read

The code

Cent-exact splits and the ledger.

The equal split. An amount of 100.00 shared by three is 3333 cents each with 1 cent left over. The leftover cents are handed out one each to the first people, so the shares are 3334, 3333 and 3333, and they add up to 10000.

class Equal implements Split {
    public Map<String, Long> shares(long total, List<String> p, Map<String, Long> d) {
        Map<String, Long> r = new LinkedHashMap<>();
        long base = total / p.size(), rem = total % p.size();
        for (int i = 0; i < p.size(); i++) r.put(p.get(i), base + (i < rem ? 1 : 0));
        return r;
    }
}

The exact split checks that the given amounts add up to the total, and refuses otherwise. The percent split checks that the percentages add up to 100. Each share is the total times the percentage divided by 100, rounded down, and the leftover cents go to the last person so nothing is lost.

class Exact implements Split {
    public Map<String, Long> shares(long total, List<String> p, Map<String, Long> d) {
        long sum = 0; for (long v : d.values()) sum += v;
        if (sum != total) throw new IllegalArgumentException("amounts add to " + sum + ", not " + total);
        return new LinkedHashMap<>(d);
    }
}

The ledger records an expense in three moves: validate, compute shares, update balances. The payer is credited the whole total. Each sharer is debited their share. The payer may also be a sharer, and then the two moves net out.

void expense(String payer, long total, List<String> people, Split rule, Map<String, Long> detail) {
    if (total <= 0) throw new IllegalArgumentException("amount must be positive");
    for (String p : people) if (!members.contains(p)) throw new IllegalArgumentException("unknown member " + p);
    if (!members.contains(payer)) throw new IllegalArgumentException("unknown member " + payer);
    Map<String, Long> sh = rule.shares(total, people, detail);
    long check = 0; for (long v : sh.values()) check += v;
    if (check != total) throw new IllegalStateException("shares do not add up");
    net.merge(payer, total, Long::sum);
    for (var e : sh.entrySet()) net.merge(e.getKey(), -e.getValue(), Long::sum);
}

All checks come before any change to a balance, so a refused expense leaves the books untouched (the validate-then-act habit of Level 5, module 1). Since the payer gains total and the sharers lose exactly total between them, the sum of all balances stays zero after every expense.

Simplifying the debts. Put everyone who is owed money into one list and everyone who owes into another. Take the biggest creditor and the biggest debtor. The debtor pays the smaller of the two amounts to the creditor. One of them is then cleared, and the other stays in the list with a smaller amount. Repeat until both lists are empty. Each payment clears at least one person, so with n people with non-zero balances there are at most n - 1 payments.

List<String> simplify() {
    PriorityQueue<Map.Entry<String, Long>> cred = new PriorityQueue<>((x, y) -> Long.compare(y.getValue(), x.getValue()));
    PriorityQueue<Map.Entry<String, Long>> debt = new PriorityQueue<>((x, y) -> Long.compare(x.getValue(), y.getValue()));
    for (var e : net.entrySet()) {
        if (e.getValue() > 0) cred.add(new AbstractMap.SimpleEntry<>(e));
        else if (e.getValue() < 0) debt.add(new AbstractMap.SimpleEntry<>(e));
    }
    List<String> out = new ArrayList<>();
    while (!cred.isEmpty() && !debt.isEmpty()) {
        var c = cred.poll(); var d = debt.poll();
        long pay = Math.min(c.getValue(), -d.getValue());
        out.add(d.getKey() + " pays " + c.getKey() + " " + pay / 100 + "." + String.format("%02d", pay % 100));
        c.setValue(c.getValue() - pay); d.setValue(d.getValue() + pay);
        if (c.getValue() > 0) cred.add(c);
        if (d.getValue() < 0) debt.add(d);
    }
    return out;
}

This greedy method gives a small number of payments, at most n - 1, though it does not always find the absolute minimum. Finding the true minimum is a harder problem. Say that if asked.

A run with four members, Asha, Ben, Chen and Dev. Amounts are shown in cents.

Step Balances after the step
Asha pays 100.00 for Asha, Ben and Chen, equal split Asha 6666, Ben -3333, Chen -3333, Dev 0
Ben pays 60.00 for the same three, equal split Asha 4666, Ben 667, Chen -5333, Dev 0
Simplify Chen pays Asha 46.66, Chen pays Ben 6.67
Chen pays 30.00 for Chen (25.00) and Dev (5.00), exact split Chen -4833, Dev -500
Dev pays 10.01 for Asha and Dev, 50 per cent each Asha 4166, Dev 0
Sum of all balances 0

The percent step shows the leftover rule. 50 per cent of 1001 is 500 with 1 cent lost to rounding down, for both people. The last person, Dev, takes the extra cent, so the shares are 500 and 501 and add up to 1001. Dev paid 1001 and owes 501, plus the earlier 500 owed to Chen, which returns Dev to zero. Both bad inputs are refused: an exact split of 4.00 and 5.00 for a 10.00 expense reports "amounts add to 900, not 1000", and an unknown member gives "unknown member Zed".

A settlement is two balance changes. If Dev pays Chen 1.00, Dev's balance rises by 100 and Chen's falls by 100, and the total is still zero.

Check yourself: 1. Why do the first people get the leftover cents in the equal split? 2. Why are checks done before changing any balance? 3. Why are there at most n - 1 payments when simplifying?