Expense Splitter
Build the money engine of a Splitwise-style app for one group of friends. Every expense is paid by one member and shared among some members, in one of four ways. Money is always integer cents, so shares must add up to the bill exactly. The four split types are the part that changes the most, so each should be its own rule that the rest of the code treats the same way: adding a fifth later must not mean editing the four that already work. That is the Strategy pattern, sitting on top of a small ledger of who owes whom.
Implement the class Splitwise:
Splitwise(members): a group with the given member names (strings).addExpense(payer, amount, type, users, data):payerpaidamountcents, shared amongusers(a list, in the order given). Returns"OK"and records it, or"INVALID"and changes nothing. Thetypedecides howdata(a list aligned withusers) is used:"equal": everyone pays the same.datais ignored (it is[])."exact":data[i]is the cents thatusers[i]pays. Each must be a whole number of at least 0, and they must add up toamount."percent":data[i]is the whole percent thatusers[i]pays. Each must be a whole number of at least 1, and they must add up to 100."shares":data[i]is a weight, a whole number of at least 1. People pay in proportion to their weights.
settle(from, to, amount):frompaystobackamountcents of what they owe. Returns"OK", or"INVALID"(and changes nothing) unless both are members, they are different,amountis a positive whole number, andfromcurrently owestoat leastamount.owes(from, to): the centsfromcurrently owesto. It is never negative, and at most one ofowes(a, b)andowes(b, a)is above 0.balance(user): net cents foruser: what others owe them minus what they owe others. Positive means they are owed money. A name that is not a member gives0.simplify(): a short list of payments[from, to, cents]that would settle everyone, worked out from the net balances (see below).expenseCount(): how many expenses have been accepted so far.
Valid expenses. addExpense is "INVALID" unless: payer and every user are members; users is not empty and has no repeats; amount is a positive whole number; type is one of the four; and the data rules above hold. The payer does not have to be one of the users.
Whole cents. For equal, percent and shares, first give each person the floor of amount * weight / total weight (for equal every weight is 1). The cents left over, always fewer than the number of people, are then handed out one each to the first people in users, in the order given. For example, 1001 cents split equally among [a, b, c] is 334, 334, 333.
Debts. Each user owes the payer their share (the payer owes nothing for their own share). A debt in one direction cancels a debt in the other direction between the same two people, so for each pair only the difference is kept.
Simplify. Compute every member's net balance, then repeat until nobody owes anything: take the member who owes the most and the member who is owed the most (ties: the name that comes first alphabetically), and record one payment from the first to the second for the smaller of the two amounts. Return the payments in the order produced. Members whose balance is 0 never appear. (Finding the fewest possible payments is NP-hard in general; this greedy method needs at most one fewer payment than there are people.)
Notes
- Nothing throws; every failure is the string
"INVALID". simplifyonly reads the books. It does not change what anyone owes.
Examples
Example 1
Input: ["Splitwise","addExpense","owes","owes","balance","balance","expenseCount"]
[[["ann","ben","cam"]],["ann",3000,"equal",["ann","ben","cam"],[]],["ben","ann"],["ann","ben"],["ann"],["ben"],[]]
Output: [null,"OK",1000,0,2000,-1000,1]3000 split three ways is 1000 each. Ben and Cam each owe Ann 1000, and Ann's own share creates no debt, so she is owed 2000 in total.
Example 2
Input: ["Splitwise","addExpense","owes","owes","balance"]
[[["ann","ben","cam"]],["ben",1000,"equal",["ann","ben","cam"],[]],["ann","ben"],["cam","ben"],["ben"]]
Output: [null,"OK",334,333,667]1000 among three: floors are 333, with 1 cent left over. It goes to the first user in the list, Ann, so Ann owes 334 and Cam 333. Ben is owed 334 + 333 = 667.
Example 3
Input: ["Splitwise","addExpense","addExpense","addExpense","addExpense","addExpense","addExpense","addExpense","addExpense","expenseCount"]
[[["ann","ben","cam"]],["zed",100,"equal",["ann"],[]],["ann",100,"equal",["ann","zed"],[]],["ann",100,"equal",["ann","ann"],[]],["ann",100,"equal",[],[]],["ann",0,"equal",["ann"],[]],["ann",-5,"equal",["ann"],[]],["ann",10.5,"equal",["ann"],[]],["ann",100,"weird",["ann"],[]],[]]
Output: [null,"INVALID","INVALID","INVALID","INVALID","INVALID","INVALID","INVALID","INVALID",0]Unknown payer, unknown user, a repeated user, no users, a zero, negative or fractional amount, and an unknown split type are all INVALID, and nothing is recorded.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
class Splitwise {
/** @param {string[]} members */
constructor(members) {
}
/** Share `amount` cents paid by `payer` among `users`. @return {string} "OK" or "INVALID" */
addExpense(payer, amount, type, users, data) {
}
/** `from` pays `to` back part or all of a debt. @return {string} "OK" or "INVALID" */
settle(from, to, amount) {
}
/** @return {number} cents `from` currently owes `to` (never negative) */
owes(from, to) {
}
/** @return {number} cents owed to `user` minus cents `user` owes; 0 for a non-member */
balance(user) {
}
/** @return {Array<[string, string, number]>} payments [from, to, cents] that settle everyone */
simplify() {
}
/** @return {number} how many expenses have been accepted */
expenseCount() {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.