How to simplify debt among a bunch of users within a group

simplify_debt.ts

class Ledger {
	users = new Set<string>(); // Holds unique users
	balances: Record<string, number> = {}; // Balance of each user
	transactions: Record<`${string}:${string}`, number> = {}; // person1:person2 -> amount
	simplified = false;

	#results: Record<
		'simplified' | 'non_simplified',
		{
			payer_user_id: string;
			payee_user_id: string;
			amount: number;
		}[]
	> = {
		simplified: [],
		non_simplified: [],
	};

	constructor(simplified: boolean) {
		this.simplified = simplified;
	}

	add({
		payer_user_id,
		payee_user_id,
		amount,
	}: {
		payer_user_id: string;
		payee_user_id: string;
		amount: number;
	}) {
		if (payer_user_id === payee_user_id) {
			return;
		}

		this.users.add(payer_user_id);
		this.users.add(payee_user_id);

		this.balances[payer_user_id] = (this.balances[payer_user_id] || 0) + amount;
		this.balances[payee_user_id] = (this.balances[payee_user_id] || 0) - amount;

		const payer_bias = `${payer_user_id}:${payee_user_id}` as const;
		const payee_bias = `${payee_user_id}:${payer_user_id}` as const;

		// Update transactions
		if (payer_bias in this.transactions) {
			this.transactions[payer_bias] += amount;
		} else if (payee_bias in this.transactions) {
			this.transactions[payee_bias] -= amount;

			if (this.transactions[payee_bias] < 0) {
				// if the balance tips in the other direction, flip the transaction
				this.transactions[payer_bias] = -this.transactions[payee_bias];
				delete this.transactions[payee_bias];
			}
		} else {
			this.transactions[payer_bias] = amount;
		}
	}

	get_transactions(simplified: boolean = this.simplified) {
		let transactions: {
			payer_user_id: string;
			payee_user_id: string;
			amount: number;
		}[] = [];

		if (simplified) {
			const balances_arr = Object.entries(this.balances).map(([userId, amount]) => ({
				userId,
				amount,
			}));

			// Sort the balances: creditors at the start (descending), debtors at the end (ascending)
			balances_arr.sort((a, b) => b.amount - a.amount);

			let i = 0; // Start pointer for creditors
			let j = balances_arr.length - 1; // Start pointer for debtors

			// Loop until all debts are settled
			while (i < j) {
				// The amount to be settled is the smaller of the two opposite balances
				const settleAmount = Math.min(balances_arr[i].amount, -balances_arr[j].amount);

				// Add the transaction
				transactions.push({
					payer_user_id: balances_arr[j].userId,
					payee_user_id: balances_arr[i].userId,
					amount: settleAmount,
				});

				// Adjust the balances
				balances_arr[i].amount -= settleAmount;
				balances_arr[j].amount += settleAmount;

				// Move the pointers
				if (balances_arr[i].amount === 0) {
					i++;
				}
				if (balances_arr[j].amount === 0) {
					j--;
				}
			}
		} else {
			transactions = Object.entries(this.transactions).map(([key, value]) => {
				const [payer, payee] = key.split(':');
				return {
					payer_user_id: payer,
					payee_user_id: payee,
					amount: -value,
				};
			});
		}

		// Centify
		for (const transaction of transactions) {
			transaction.amount = centify(transaction.amount);
		}

		this.#results[simplified ? 'simplified' : 'non_simplified'] = transactions;

		return transactions;
	}

	get_ui() {
		let transactions = this.simplified ? this.#results.simplified : this.#results.non_simplified;
		if (!transactions.length) transactions = this.get_transactions(this.simplified);

		const ui = new Map<string, { owes: Map<string, number>; owed_by: Map<string, number> }>();

		for (const { payer_user_id, payee_user_id, amount } of transactions) {
			if (!ui.has(payer_user_id)) ui.set(payer_user_id, { owes: new Map(), owed_by: new Map() });
			if (!ui.has(payee_user_id)) ui.set(payee_user_id, { owes: new Map(), owed_by: new Map() });

			if (amount > 0) {
				ui.get(payer_user_id)!.owes.set(payee_user_id, amount);
				ui.get(payee_user_id)!.owed_by.set(payer_user_id, amount);
			} else {
				ui.get(payer_user_id)!.owed_by.set(payee_user_id, -amount);
				ui.get(payee_user_id)!.owes.set(payer_user_id, -amount);
			}
		}

		const owed_by_sorted = Array.from(ui.entries()).sort(
			([, a], [, b]) => -a.owed_by.size + b.owed_by.size,
		);

		const owes_sorted = Array.from(ui.entries()).sort(([, a], [, b]) => -a.owes.size + b.owes.size);

		if (owes_sorted[0][1].owes.size > owed_by_sorted[0][1].owed_by.size) {
			return new Map(owes_sorted);
		} else {
			return new Map(owed_by_sorted);
		}
	}

	get_saved() {
		let simplified = this.#results.simplified;
		let non_simplified = this.#results.non_simplified;

		if (!simplified.length) simplified = this.get_transactions(true);
		if (!non_simplified.length) non_simplified = this.get_transactions(false);

		return non_simplified.length - simplified.length;
	}
}

const dummy = [
  {
    amount: 300000,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'rb9rts552oya2ni'
  },
  {
    amount: 100000,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: '8l0z7sgnjawlen6'
  },
  {
    amount: 100000,
    payer_user_id: 'afsjr5daudcmyic',
    payee_user_id: 'rb9rts552oya2ni'
  },
  {
    amount: 300000,
    payer_user_id: 'afsjr5daudcmyic',
    payee_user_id: 'ff4zrxv88p3ev90'
  },
  {
    amount: 100000,
    payer_user_id: 'afsjr5daudcmyic',
    payee_user_id: '8l0z7sgnjawlen6'
  },
  {
    amount: 100000,
    payer_user_id: 'afsjr5daudcmyic',
    payee_user_id: 'k6ehx0g4ypvg0lt'
  },
  {
    amount: 400000,
    payer_user_id: 'rb9rts552oya2ni',
    payee_user_id: 'ff4zrxv88p3ev90'
  },
  {
    amount: 200000,
    payer_user_id: 'ff4zrxv88p3ev90',
    payee_user_id: '8l0z7sgnjawlen6'
  },
  {
    amount: 500000,
    payer_user_id: '8l0z7sgnjawlen6',
    payee_user_id: 'k6ehx0g4ypvg0lt'
  },
  {
    amount: 666667,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'gnhbpv70frh3pb6'
  },
  {
    amount: 666667,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'afsjr5daudcmyic'
  },
  {
    amount: 666667,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'rb9rts552oya2ni'
  },
  {
    amount: 666667,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'ff4zrxv88p3ev90'
  },
  {
    amount: 666666,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: '8l0z7sgnjawlen6'
  },
  {
    amount: 666666,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'k6ehx0g4ypvg0lt'
  },
  {
    amount: 4000000,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'afsjr5daudcmyic'
  },
  {
    amount: 1000000,
    payer_user_id: 'gnhbpv70frh3pb6',
    payee_user_id: 'rb9rts552oya2ni'
  }
]

// We want simplify debts to be on
const ledger = new Ledger(true);

// Add all entries to ledger
for (const row of rows) ledger.add(row);

console.log('balances', ledger.balances);

// Get the final transactions as array
console.log(ledger.get_transactions())

// Get the final transactions for UI, in form of who pays who
console.log('UI', ledger.get_ui())