Splitwise

public final class Money implements Comparable<Money> {
    private final long cents;
    private final Currency currency;

    public Money(long cents, Currency c) { this.cents = cents; this.currency = c; }

    public Money plus(Money other) {
        check(other);
        return new Money(cents + other.cents, currency);
    }
    public Money minus(Money other) {
        check(other);
        return new Money(cents - other.cents, currency);
    }

    private void check(Money m) {
        if (!currency.equals(m.currency)) throw new IllegalArgumentException();
    }

    public long cents() { return cents; }
    // hashCode, equals, compareTo, toString
}

public interface SplitStrategy {
    Map<User, Money> split(Money total, List<Participant> participants);
}

public class EqualSplit implements SplitStrategy {
    public Map<User, Money> split(Money total, List<Participant> ps) {
        long perHead = total.cents() / ps.size();
        long remainder = total.cents() % ps.size();
        Map<User, Money> result = new HashMap<>();
        for (int i = 0; i < ps.size(); i++) {
            // First `remainder` people pay an extra cent to absorb rounding
            long share = perHead + (i < remainder ? 1 : 0);
            result.put(ps.get(i).user, new Money(share, total.currency()));
        }
        return result;
    }
}

public class ExactSplit implements SplitStrategy {
    public Map<User, Money> split(Money total, List<Participant> ps) {
        long sum = ps.stream().mapToLong(p -> p.exactAmount.cents()).sum();
        if (sum != total.cents()) throw new IllegalArgumentException("Shares must sum to total");
        return ps.stream().collect(Collectors.toMap(p -> p.user, p -> p.exactAmount));
    }
}

public class PercentSplit implements SplitStrategy {
    public Map<User, Money> split(Money total, List<Participant> ps) {
        double sum = ps.stream().mapToDouble(p -> p.percent).sum();
        if (Math.abs(sum - 100.0) > 0.001) throw new IllegalArgumentException("Percents must sum to 100");

        Map<User, Money> result = new HashMap<>();
        long allocated = 0;
        for (int i = 0; i < ps.size() - 1; i++) {
            long share = Math.round(total.cents() * ps.get(i).percent / 100.0);
            result.put(ps.get(i).user, new Money(share, total.currency()));
            allocated += share;
        }
        // Last person absorbs rounding
        result.put(ps.get(ps.size() - 1).user, new Money(total.cents() - allocated, total.currency()));
        return result;
    }
}

public class Expense {
    private final String id;
    private final String description;
    private final Money amount;
    private final User paidBy;
    private final Map<User, Money> shares;
    private final LocalDateTime date;

    public Expense(String desc, Money amount, User paidBy,
                   List<Participant> participants, SplitStrategy strategy) {
        this.id = UUID.randomUUID().toString();
        this.description = desc;
        this.amount = amount;
        this.paidBy = paidBy;
        this.shares = strategy.split(amount, participants);
        this.date = LocalDateTime.now();
    }
}

public class BalanceSheet {
    // balances[A][B] = amount A owes B (negative = B owes A)
    private final Map<User, Map<User, Money>> balances = new ConcurrentHashMap<>();

    public synchronized void apply(Expense e) {
        User payer = e.getPaidBy();
        for (Map.Entry<User, Money> entry : e.getShares().entrySet()) {
            User u = entry.getKey();
            Money owed = entry.getValue();
            if (u.equals(payer)) continue;   // payer doesn't owe themselves

            adjust(u, payer, owed);
        }
    }

    private void adjust(User from, User to, Money delta) {
        Money current = get(from, to);
        Money updated = current.plus(delta);
        balances.computeIfAbsent(from, k -> new HashMap<>()).put(to, updated);

        // Mirror: to -> from is the negation
        Money mirror = get(to, from).minus(delta);
        balances.computeIfAbsent(to, k -> new HashMap<>()).put(from, mirror);
    }

    public Money get(User from, User to) {
        return balances.getOrDefault(from, Map.of())
                       .getOrDefault(to, Money.zero(USD));
    }

    /** Net amount user owes everyone else (positive = owes, negative = is owed). */
    public Money netOwed(User user) {
        return balances.getOrDefault(user, Map.of()).values().stream()
            .reduce(Money.zero(USD), Money::plus);
    }
}

public List<Transaction> settle(BalanceSheet sheet, List<User> users) {
    Map<User, Long> net = new HashMap<>();
    for (User u : users) net.put(u, sheet.netOwed(u).cents());

    List<Transaction> result = new ArrayList<>();
    PriorityQueue<Map.Entry<User, Long>> debtors = new PriorityQueue<>(
        Map.Entry.<User, Long>comparingByValue());        // most negative first
    PriorityQueue<Map.Entry<User, Long>> creditors = new PriorityQueue<>(
        Map.Entry.<User, Long>comparingByValue().reversed());   // most positive first

    for (var entry : net.entrySet()) {
        if (entry.getValue() < 0) creditors.add(entry);
        else if (entry.getValue() > 0) debtors.add(entry);
    }

    while (!debtors.isEmpty() && !creditors.isEmpty()) {
        var debtor = debtors.poll();
        var creditor = creditors.poll();
        long pay = Math.min(debtor.getValue(), -creditor.getValue());
        result.add(new Transaction(debtor.getKey(), creditor.getKey(),
                                   new Money(pay, USD)));
        if (debtor.getValue() - pay > 0) debtors.add(Map.entry(debtor.getKey(), debtor.getValue() - pay));
        if (creditor.getValue() + pay < 0) creditors.add(Map.entry(creditor.getKey(), creditor.getValue() + pay));
    }
    return result;
}

public class SplitwiseService {
    private final Map<String, Group> groups = new ConcurrentHashMap<>();

    public Expense addExpense(String groupId, String desc, Money amount,
                              User payer, List<Participant> participants,
                              SplitStrategy strategy) {
        Group g = groups.get(groupId);
        Expense e = new Expense(desc, amount, payer, participants, strategy);
        synchronized (g) {
            g.addExpense(e);
            g.getBalanceSheet().apply(e);
        }
        return e;
    }

    public List<Transaction> settleGroup(String groupId) {
        Group g = groups.get(groupId);
        synchronized (g) {
            return MinCashFlow.compute(g.getBalanceSheet(), g.getMembers());
        }
    }
}