Money has to balance first
This note covers CashFlow's optional balance-settlement solver. The newer clearing engine starts from the original obligation graph so it can distinguish loop cancellation from chain simplification; that is a different question from finding the fewest payments for an already reduced balance state.
The solver cannot repair bad accounting. With binary floating point, a balance that should be zero can end up as a collection of tiny residuals. I store every value as integer cents so equality and conservation checks stay exact at the stored currency precision.
After expenses are reduced, positive balances belong to creditors and negative balances to debtors. They must sum to zero. Every proposed payment moves value from one side to the other without changing that total.
const total = balances.reduce((sum, value) => sum + value, 0)
if (total !== 0) throw new Error("Balances must sum to zero")
// Values are integer cents: 1299 means 12.99 in the base currency.Decide what ‘minimum’ means
A settlement could minimize the money moved, the number of payments, the largest payment, or some measure of fairness. Once balances sum to zero, every valid plan clears the same net obligation. CashFlow therefore defines the target as the fewest payments for that balance state.
A greedy debtor-to-creditor match is quick and often good enough, but it can use more transactions than necessary. The exact path explores valid transfers, prunes equivalent states, and remembers the best remaining count.
Cap exact search at 12 balances
The search space grows combinatorially with the number of non-zero balances. I cap exact minimum-payment search at 12 rather than pretend it stays practical for groups of any size.
- Remove zero balances before selecting a strategy.
- Choose one unsettled participant and pair it with compatible opposite-sign balances.
- Apply a transfer, recurse, then restore the previous state.
- Memoize normalized balance states and prune branches that cannot beat the best plan.
- Use stable participant ordering so equal inputs produce equal outputs.
function settle(balances) {
const active = balances.filter(({ cents }) => cents !== 0)
return active.length <= 12
? exactMinimumPayments(active)
: deterministicGreedy(active)
}Use a predictable fallback
Above the limit, the fallback repeatedly matches a debtor and creditor in a stable order. It settles every balance and returns the same plan for the same input, but it does not promise the global minimum.
That repeatability matters to both tests and users. Two people refreshing the same group should not get different recommendations just because a map or database returned its members in another order.
Why I keep WebAssembly optional
The repository includes a matching C++ implementation that compiles to WebAssembly. I use it for runtime comparisons and parity tests, but changing languages does not change the combinatorial cost of exact search. The hosted application currently uses the tested TypeScript solver; WASM is not always running in production.
The interface reports which strategy and runtime produced a plan. Both implementations have to satisfy the same accounting invariants.