Skip to content

Instantly share code, notes, and snippets.

@branneman

branneman/splitser.js

Last active January 22, 2025 09:38
Show Gist options
  • Save branneman/5f63c900f7a2251e22a3d5e9ee5761e6 to your computer and use it in GitHub Desktop.
Save branneman/5f63c900f7a2251e22a3d5e9ee5761e6 to your computer and use it in GitHub Desktop.
Download ZIP
Splitser algorithm
Raw
splitser.js
export const getSettlement = (transactions) => {
const settlement = []
let recurProtection = 0
while (true) {
const balances = getBalances(transactions.concat(settlement))
if (allBalancesZero(balances)) break
if (recurProtection++ > 1e2) {
console.log({ settlement })
throw new Error('Infinite loop')
}
// find members with lowest & highest balance
const sortedBalances = Object.entries(balances).sort((a, z) => {
return a[1] - z[1]
})
const lowestMember = sortedBalances.at(0).at(0)
const highestMember = sortedBalances.at(-1).at(0)
// lowest pays to highest, up until the max amount highest needs
const amount = Math.min(
Math.abs(balances[lowestMember]),
balances[highestMember]
)
settlement.push({
member: lowestMember,
amount,
shares: { [highestMember]: 1 },
})
}
return settlement
}
export const getBalances = (transactions) => {
const balances = {}
transactions.forEach((transaction) => {
const totalShares = getTotalShares(transaction.shares)
const changePerShare = transaction.amount / totalShares
// Step 1: Calculate the change in balance for member who did transaction
if (!balances[transaction.member]) balances[transaction.member] = 0
balances[transaction.member] += transaction.amount
// Step 2: Calculate the change in balance for each member with shares
Object.entries(transaction.shares).forEach(([member, shares]) => {
// Add member to balances if they don't exist
if (!balances[member]) balances[member] = 0
// Calculate the change for amount of shares
let change = -changePerShare * shares
balances[member] += change
})
})
return balances
}
export const allBalancesZero = (balances) => {
// zero or near-zero, when rounded to 2 decimals
const isNearZero = (x) => x < 0.01 && x > -0.01
return Object.values(balances).every(
(balance) => balance === 0 || isNearZero(balance)
)
}
export const getTotalShares = (shares) => {
return Object.values(shares).reduce((a, b) => a + b, 0)
}
Raw
splitser.test.js
import { describe, it, expect } from 'vitest'
import {
getSettlement,
getBalances,
allBalancesZero,
getTotalShares,
} from './splitser.js'
/*
Expense - Person A pays €30 to a third party (for all)
-> an expense is a positive amount
{
member: 'Person A',
amount: 30,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
}
Income - Person A receives €20 from a third party (for all)
-> an income is a negative amount
{
member: 'Person A',
amount: -30,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
}
Transfer - Person A pays €30 to Person B
{
member: 'Person A',
amount: 30,
shares: { 'Person A': 0, 'Person B': 1, 'Person C': 0 },
}
*/
describe('getSettlement()', () => {
describe('only expenses', () => {
it('2p, 25-75, only 1 share', () => {
const transactions = [
{
member: 'Person A',
amount: 25,
shares: { 'Person A': 1, 'Person B': 1 },
},
{
member: 'Person B',
amount: 75,
shares: { 'Person A': 1, 'Person B': 1 },
},
]
const settlement = [
{
member: 'Person A',
amount: 25,
shares: { 'Person B': 1 },
},
]
expect(getSettlement(transactions)).toEqual(settlement)
})
it('3p, 30-50, varying shares', () => {
const transactions = [
{
member: 'Person A',
amount: 30, // 3 times 10
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
{
member: 'Person B',
amount: 50, // 5 times 10
shares: { 'Person A': 1, 'Person B': 2, 'Person C': 2 },
},
]
const settlement = [
{
member: 'Person C',
amount: 20,
shares: { 'Person B': 1 },
},
{
member: 'Person C',
amount: 10,
shares: { 'Person A': 1 },
},
]
expect(getSettlement(transactions)).toEqual(settlement)
})
it('3p, 30-50, varying shares, takes 3 steps to settle', () => {
const transactions = [
{
member: 'Person A',
amount: 40,
shares: {
'Person A': 1,
'Person B': 1,
'Person C': 1,
'Person D': 1,
},
},
{
member: 'Person B',
amount: 60,
shares: {
'Person A': 1,
'Person B': 2,
'Person C': 2,
'Person D': 1,
},
},
{
member: 'Person C',
amount: 20,
shares: {
'Person A': 1,
'Person B': 1,
'Person C': 1,
'Person D': 1,
},
},
]
const settlement = [
{
member: 'Person D',
amount: 25,
shares: { 'Person B': 1 },
},
{
member: 'Person C',
amount: 15,
shares: { 'Person A': 1 },
},
]
expect(getSettlement(transactions)).toEqual(settlement)
})
it.skip('real-life and complex: 13p, many transactions, varying shares', () => {
const transactions = [
{
member: 'PersonA',
amount: 45,
shares: { PersonB: 1, PersonA: 1, PersonC: 1 },
},
{
member: 'PersonC',
amount: 83.95,
shares: { PersonB: 1, PersonA: 1, PersonC: 1 },
},
{
member: 'PersonA',
amount: 18.98,
shares: { PersonA: 1, PersonC: 1 },
},
{
member: 'PersonA',
amount: 37.4,
shares: { PersonB: 1, PersonA: 1, PersonC: 1 },
},
{
member: 'PersonD',
amount: 50,
shares: { PersonE: 1, PersonF: 1, PersonG: 1, PersonD: 1 },
},
{
member: 'PersonG',
amount: 9.7,
shares: { PersonF: 1, PersonG: 1, PersonD: 1 },
},
{
member: 'PersonC',
amount: 469.7,
shares: {
PersonB: 1,
PersonH: 1,
PersonI: 1,
PersonJ: 3,
PersonC: 1,
PersonE: 1,
PersonF: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonD: 1,
},
},
{
member: 'PersonB',
amount: 17.1,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonA',
amount: 35.4,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonE',
amount: 70,
shares: { PersonE: 1, PersonD: 1 },
},
{
member: 'PersonD',
amount: 46,
shares: { PersonB: 1, PersonH: 1, PersonJ: 1, PersonD: 1 },
},
{
member: 'PersonG',
amount: 87,
shares: {
PersonI: 1,
PersonF: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonH',
amount: 39,
shares: { PersonH: 1, PersonI: 1, PersonG: 1, PersonD: 1 },
},
{
member: 'PersonH',
amount: 30.2,
shares: { PersonB: 1, PersonH: 1, PersonJ: 1, PersonD: 1 },
},
{
member: 'PersonH',
amount: 35.2,
shares: { PersonB: 1, PersonH: 1, PersonJ: 1, PersonD: 1 },
},
{
member: 'PersonH',
amount: 25,
shares: { PersonB: 1, PersonH: 2, PersonG: 3 },
},
{
member: 'PersonB',
amount: 58,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonB',
amount: 200,
shares: {
PersonB: 3,
PersonH: 3,
PersonI: 1,
PersonJ: 3,
PersonC: 1,
PersonM: 1,
PersonE: 3,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonD: 3,
PersonL: 1,
},
},
{
member: 'PersonG',
amount: 56,
shares: {
PersonI: 1,
PersonM: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonI',
amount: 255,
shares: {
PersonI: 1,
PersonC: 1,
PersonM: 1,
PersonF: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonL',
amount: 42,
shares: {
PersonI: 1,
PersonF: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonL',
amount: 30.6,
shares: {
PersonI: 1,
PersonF: 1,
PersonA: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonD',
amount: 51.9,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonE',
amount: 125,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonB',
amount: 152,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonF',
amount: 98,
shares: {
PersonI: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonL: 1,
},
},
{
member: 'PersonH',
amount: 37.6,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonD',
amount: 50,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonM: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonE',
amount: 95,
shares: {
PersonB: 1,
PersonH: 1,
PersonJ: 1,
PersonM: 1,
PersonE: 1,
PersonD: 1,
},
},
{
member: 'PersonM',
amount: 35,
shares: {
PersonB: 1,
PersonH: 1,
PersonM: 1,
PersonK: 1,
PersonD: 1,
},
},
{
member: 'PersonD',
amount: 365,
shares: {
PersonB: 1,
PersonH: 1,
PersonI: 1,
PersonJ: 1,
PersonC: 1,
PersonM: 1,
PersonE: 1,
PersonA: 1,
PersonK: 1,
PersonG: 1,
PersonD: 1,
PersonL: 1,
},
},
{
member: 'PersonA',
amount: 65,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonA',
amount: 65.12,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonA',
amount: 82.51,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonE',
amount: 54.8,
shares: { PersonE: 1, PersonG: 1, PersonD: 1 },
},
{
member: 'PersonA',
amount: 53.3,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
{
member: 'PersonB',
amount: 14.5,
shares: { PersonB: 1, PersonC: 1, PersonA: 1 },
},
]
const settlement = [
{ member: 'PersonJ', amount: 270.2, shares: { PersonC: 1 } },
{ member: 'PersonD', amount: 123.45, shares: { PersonK: 1 } },
{ member: 'PersonM', amount: 68.98, shares: { PersonE: 1 } },
{ member: 'PersonG', amount: 67.62, shares: { PersonD: 1 } },
{ member: 'PersonH', amount: 55.56, shares: { PersonI: 1 } },
{ member: 'PersonL', amount: 55.35, shares: { PersonD: 1 } },
{ member: 'PersonK', amount: 41.5, shares: { PersonA: 1 } },
{ member: 'PersonH', amount: 33.27, shares: { PersonB: 1 } },
{ member: 'PersonJ', amount: 25.62, shares: { PersonI: 1 } },
{ member: 'PersonF', amount: 13.35, shares: { PersonA: 1 } },
{ member: 'PersonM', amount: 7.9, shares: { PersonA: 1 } },
{ member: 'PersonJ', amount: 7.18, shares: { PersonE: 1 } },
]
console.log(getSettlement(transactions))
expect(getSettlement(transactions)).toEqual(settlement)
})
})
})
describe('getBalances()', () => {
describe('only expenses', () => {
it('2p, self expense', () => {
const transactions = [
{
member: 'Person A',
amount: 50,
shares: { 'Person A': 1, 'Person B': 0 },
},
]
const balances = {
'Person A': 0,
'Person B': 0,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('2p, 50, only 1 share', () => {
const transactions = [
{
member: 'Person A',
amount: 50,
shares: { 'Person A': 1, 'Person B': 1 },
},
]
const balances = {
'Person A': 25,
'Person B': -25,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('3p, 50, extra non-participant', () => {
const transactions = [
{
member: 'Person A',
amount: 50,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 0 },
},
]
const balances = {
'Person A': 25,
'Person B': -25,
'Person C': 0,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('2p, 25-75, only 1 share', () => {
const transactions = [
{
member: 'Person A',
amount: 25,
shares: { 'Person A': 1, 'Person B': 1 },
},
{
member: 'Person B',
amount: 75,
shares: { 'Person A': 1, 'Person B': 1 },
},
]
const balances = {
'Person A': -25,
'Person B': 25,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('3p, 3x30, all equal amounts', () => {
const transactions = [
{
member: 'Person A',
amount: 30,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
{
member: 'Person B',
amount: 30,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
{
member: 'Person C',
amount: 30,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
]
const balances = {
'Person A': 0,
'Person B': 0,
'Person C': 0,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('3p, 25-75-10, with self expense', () => {
const transactions = [
{
member: 'Person A',
amount: 25,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 0 },
},
{
member: 'Person B',
amount: 75,
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 0 },
},
{
member: 'Person C',
amount: 10,
shares: { 'Person A': 0, 'Person B': 0, 'Person C': 1 },
},
]
const balances = {
'Person A': -25,
'Person B': 25,
'Person C': 0,
}
expect(getBalances(transactions)).toEqual(balances)
})
it('3p, 30-50, varying shares', () => {
const transactions = [
{
member: 'Person A',
amount: 30, // 3 times 10
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
{
member: 'Person B',
amount: 50, // 5 times 10
shares: { 'Person A': 1, 'Person B': 2, 'Person C': 2 },
},
]
const balances = {
'Person A': 10,
'Person B': 20,
'Person C': -30,
}
expect(getBalances(transactions)).toEqual(balances)
})
})
describe('income', () => {
it('2p, -50, only 1 share', () => {
const transactions = [
{
member: 'Person A',
amount: -50,
shares: { 'Person A': 1, 'Person B': 1 },
},
]
const balances = {
'Person A': -25,
'Person B': 25,
}
expect(getBalances(transactions)).toEqual(balances)
})
})
describe('transfer', () => {
it('2p, A transfers 50 to B', () => {
const transactions = [
{
member: 'Person A',
amount: 50,
shares: { 'Person A': 0, 'Person B': 1 },
},
]
const balances = {
'Person A': 50,
'Person B': -50,
}
expect(getBalances(transactions)).toEqual(balances)
})
})
describe('settlement transactions', () => {
it('3p, 30-50, varying shares', () => {
const transactions = [
// Expense transactions:
{
member: 'Person A',
amount: 30, // 3 times 10
shares: { 'Person A': 1, 'Person B': 1, 'Person C': 1 },
},
{
member: 'Person B',
amount: 50, // 5 times 10
shares: { 'Person A': 1, 'Person B': 2, 'Person C': 2 },
},
// Settlement transactions:
{
member: 'Person C',
amount: 20,
shares: { 'Person A': 0, 'Person B': 1, 'Person C': 0 },
},
{
member: 'Person C',
amount: 10,
shares: { 'Person A': 1, 'Person B': 0, 'Person C': 0 },
},
]
const balances = {
'Person A': 0,
'Person B': 0,
'Person C': 0,
}
expect(getBalances(transactions)).toEqual(balances)
})
})
})
describe('allBalancesZero()', () => {
it('rejects non zero', () => {
const balances = {
'Person A': 25,
'Person B': -25,
'Person C': 0,
}
expect(allBalancesZero(balances)).toBe(false)
})
it('accepts zero', () => {
const balances = {
'Person A': 0,
'Person B': 0,
'Person C': 0,
'Person D': 0,
}
expect(allBalancesZero(balances)).toBe(true)
})
it('accepts near-zero', () => {
const balances = {
'Person A': 0,
'Person B': 0.0001,
'Person C': 0,
'Person D': 0,
}
expect(allBalancesZero(balances)).toBe(true)
})
})
describe('getTotalShares()', () => {
it('sums all shares', () => {
expect(getTotalShares({ 'Person A': 1, 'Person B': 1 })).toBe(2)
expect(getTotalShares({ 'Person A': 1, 'Person B': 3 })).toBe(4)
})
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment