Design an Expense Splitter

from __future__ import annotations

import threading
from typing import Protocol


class SplitError(Exception):
    pass


def spread(amount: int, people: list[str], weights: list[int]) -> dict[str, int]:
    """Divide by weights, rounding down; leftover taka go one by one to the first people."""
    total = sum(weights)
    shares = {p: amount * w // total for p, w in zip(people, weights)}
    given, i = sum(shares.values()), 0
    while given < amount:
        shares[people[i % len(people)]] += 1
        given, i = given + 1, i + 1
    return shares


class Split(Protocol):
    """The Strategy: each way of dividing an expense turns (amount, people) into shares."""
    def shares(self, amount: int, people: list[str]) -> dict[str, int]: ...
    def describe(self) -> str: ...


class Equal:
    def describe(self) -> str:
        return "split equally"

    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        if not people:
            raise SplitError("no one to split with")
        return spread(amount, people, [1] * len(people))


class Exact:
    def __init__(self, shares: dict[str, int]):
        self._shares = shares

    def describe(self) -> str:
        return "exact split"

    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        total = sum(self._shares.values())
        if total != amount:
            raise SplitError(f"exact shares add up to {total}, not {amount}")
        return dict(self._shares)


class Percent:
    def __init__(self, people: list[str], pct: list[int]):
        self.people, self.pct = people, pct

    def describe(self) -> str:
        return "percent split"

    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        if sum(self.pct) != 100:
            raise SplitError(f"percentages add up to {sum(self.pct)}, not 100")
        return spread(amount, self.people, self.pct)


class Group:
    """Net balance per member: positive = others owe them. Balances always add up to 0."""

    def __init__(self, *members: str):
        self._lock = threading.Lock()
        self.members = list(members)
        self._balance = {m: 0 for m in members}

    def add_expense(self, payer: str, amount: int, people: list[str], split: Split) -> None:
        with self._lock:
            if amount <= 0:
                raise SplitError("amount must be positive")
            if payer not in self._balance:
                raise SplitError(f"{payer} is not in the group")
            shares = split.shares(amount, people)
            for p in shares:
                if p not in self._balance:
                    raise SplitError(f"{p} is not in the group")
            self._balance[payer] += amount  # only now, when everything is valid
            for p, share in shares.items():
                self._balance[p] -= share

    def balances(self) -> list[tuple[str, int]]:
        with self._lock:
            return [(m, self._balance[m]) for m in self.members]

    def settle_up(self) -> list[tuple[str, str, int]]:
        """Biggest debtor pays biggest creditor, repeatedly. Ties go to the earlier member."""
        with self._lock:
            left = dict(self._balance)
        pays = []
        while True:
            debtors = [m for m in self.members if left[m] < 0]
            creditors = [m for m in self.members if left[m] > 0]
            if not debtors or not creditors:
                return pays
            d = min(debtors, key=lambda m: left[m])  # min() keeps the first of equals
            c = max(creditors, key=lambda m: left[m])
            amt = min(-left[d], left[c])
            pays.append((d, c, amt))
            left[d] += amt
            left[c] -= amt


g = Group("Rahim", "Nadia", "Tania", "Sabbir")
everyone = ["Rahim", "Nadia", "Tania", "Sabbir"]
expenses = [
    ("Rahim", "hotel", 4000, everyone, Equal()),
    ("Nadia", "dinner", 1200, [], Exact({"Rahim": 300, "Nadia": 400, "Tania": 500})),
    ("Tania", "boat", 1000, [], Percent(["Rahim", "Sabbir"], [40, 60])),
    ("Sabbir", "tea", 100, ["Rahim", "Tania", "Sabbir"], Equal()),
    ("Rahim", "taxi", 1200, [], Exact({"Rahim": 600, "Nadia": 500})),
]
for i, (payer, what, amount, people, split) in enumerate(expenses, 1):
    try:
        g.add_expense(payer, amount, people, split)
        print(f"expense {i}: {payer} paid {amount} for {what}, {split.describe()}")
    except SplitError as e:
        print(f"expense {i} refused: {e}")

print("balances:")
for m, b in g.balances():
    print(f"  {m:<6} {b:+6d}")
pays = g.settle_up()
print(f"settle up ({len(pays)} payments):")
for frm, to, amt in pays:
    print(f"  {frm} pays {to} {amt}")

// Divide by weights, rounding down; leftover taka go one by one to the first people.
function spread(amount: number, people: string[], weights: number[]): Map<string, number> {
  const total = weights.reduce((a, b) => a + b, 0);
  const shares = new Map(people.map((p, i) => [p, Math.floor((amount * weights[i]!) / total)] as [string, number]));
  let given = [...shares.values()].reduce((a, b) => a + b, 0);
  for (let i = 0; given < amount; i++, given++) {
    const p = people[i % people.length]!;
    shares.set(p, shares.get(p)! + 1);
  }
  return shares;
}

// The Strategy: each way of dividing an expense turns (amount, people) into shares.
interface Split {
  shares(amount: number, people: string[]): Map<string, number>;
  describe(): string;
}

class Equal implements Split {
  describe() {
    return "split equally";
  }
  shares(amount: number, people: string[]) {
    if (people.length === 0) throw new Error("no one to split with");
    return spread(amount, people, people.map(() => 1));
  }
}

class Exact implements Split {
  readonly given: Map<string, number>;
  constructor(given: Record<string, number>) {
    this.given = new Map(Object.entries(given));
  }
  describe() {
    return "exact split";
  }
  shares(amount: number) {
    const total = [...this.given.values()].reduce((a, b) => a + b, 0);
    if (total !== amount) throw new Error(`exact shares add up to ${total}, not ${amount}`);
    return new Map(this.given);
  }
}

class Percent implements Split {
  readonly people: string[];
  readonly pct: number[];
  constructor(people: string[], pct: number[]) {
    this.people = people;
    this.pct = pct;
  }
  describe() {
    return "percent split";
  }
  shares(amount: number) {
    const total = this.pct.reduce((a, b) => a + b, 0);
    if (total !== 100) throw new Error(`percentages add up to ${total}, not 100`);
    return spread(amount, this.people, this.pct);
  }
}

// Net balance per member: positive = others owe them. Balances always add up to 0.
// No lock: one thread, and nothing here awaits.
class Group {
  readonly members: string[];
  readonly #balance: Map<string, number>;
  constructor(...members: string[]) {
    this.members = members;
    this.#balance = new Map(members.map((m) => [m, 0]));
  }
  addExpense(payer: string, amount: number, people: string[], split: Split): void {
    if (amount <= 0) throw new Error("amount must be positive");
    if (!this.#balance.has(payer)) throw new Error(`${payer} is not in the group`);
    const shares = split.shares(amount, people);
    for (const p of shares.keys()) if (!this.#balance.has(p)) throw new Error(`${p} is not in the group`);
    this.#balance.set(payer, this.#balance.get(payer)! + amount); // only now, when everything is valid
    for (const [p, s] of shares) this.#balance.set(p, this.#balance.get(p)! - s);
  }
  balances(): [string, number][] {
    return this.members.map((m) => [m, this.#balance.get(m)!]);
  }
  // Biggest debtor pays biggest creditor, repeatedly. Ties go to the earlier member.
  settleUp(): [string, string, number][] {
    const left = new Map(this.#balance);
    const pays: [string, string, number][] = [];
    for (;;) {
      let debtor = "";
      let creditor = "";
      for (const m of this.members) {
        if (left.get(m)! < 0 && (debtor === "" || left.get(m)! < left.get(debtor)!)) debtor = m;
        if (left.get(m)! > 0 && (creditor === "" || left.get(m)! > left.get(creditor)!)) creditor = m;
      }
      if (debtor === "" || creditor === "") return pays;
      const amt = Math.min(-left.get(debtor)!, left.get(creditor)!);
      pays.push([debtor, creditor, amt]);
      left.set(debtor, left.get(debtor)! + amt);
      left.set(creditor, left.get(creditor)! - amt);
    }
  }
}

const g = new Group("Rahim", "Nadia", "Tania", "Sabbir");
const everyone = ["Rahim", "Nadia", "Tania", "Sabbir"];
const expenses: [string, string, number, string[], Split][] = [
  ["Rahim", "hotel", 4000, everyone, new Equal()],
  ["Nadia", "dinner", 1200, [], new Exact({ Rahim: 300, Nadia: 400, Tania: 500 })],
  ["Tania", "boat", 1000, [], new Percent(["Rahim", "Sabbir"], [40, 60])],
  ["Sabbir", "tea", 100, ["Rahim", "Tania", "Sabbir"], new Equal()],
  ["Rahim", "taxi", 1200, [], new Exact({ Rahim: 600, Nadia: 500 })],
];
expenses.forEach(([payer, what, amount, people, split], i) => {
  try {
    g.addExpense(payer, amount, people, split);
    console.log(`expense ${i + 1}: ${payer} paid ${amount} for ${what}, ${split.describe()}`);
  } catch (e) {
    console.log(`expense ${i + 1} refused: ${(e as Error).message}`);
  }
});

console.log("balances:");
for (const [m, b] of g.balances()) console.log(`  ${m.padEnd(6)} ${(b >= 0 ? "+" + b : String(b)).padStart(6)}`);
const pays = g.settleUp();
console.log(`settle up (${pays.length} payments):`);
for (const [from, to, amt] of pays) console.log(`  ${from} pays ${to} ${amt}`);

use std::collections::HashMap;
use std::sync::Mutex;

// Divide by weights, rounding down; leftover taka go one by one to the first people.
fn spread(amount: i64, people: &[&'static str], weights: &[i64]) -> HashMap<&'static str, i64> {
    let total: i64 = weights.iter().sum();
    let mut shares: HashMap<_, _> = people.iter().zip(weights).map(|(&p, &w)| (p, amount * w / total)).collect();
    let mut given: i64 = shares.values().sum();
    let mut i = 0;
    while given < amount {
        *shares.get_mut(people[i % people.len()]).unwrap() += 1;
        given += 1;
        i += 1;
    }
    shares
}

// The Strategy: each way of dividing an expense turns (amount, people) into shares.
trait Split {
    fn shares(&self, amount: i64, people: &[&'static str]) -> Result<HashMap<&'static str, i64>, String>;
    fn describe(&self) -> &str;
}

struct Equal;
impl Split for Equal {
    fn describe(&self) -> &str { "split equally" }
    fn shares(&self, amount: i64, people: &[&'static str]) -> Result<HashMap<&'static str, i64>, String> {
        if people.is_empty() { return Err("no one to split with".into()); }
        Ok(spread(amount, people, &vec![1; people.len()]))
    }
}

struct Exact(Vec<(&'static str, i64)>);
impl Split for Exact {
    fn describe(&self) -> &str { "exact split" }
    fn shares(&self, amount: i64, _: &[&'static str]) -> Result<HashMap<&'static str, i64>, String> {
        let total: i64 = self.0.iter().map(|(_, v)| v).sum();
        if total != amount { return Err(format!("exact shares add up to {total}, not {amount}")); }
        Ok(self.0.iter().copied().collect())
    }
}

struct Percent { people: Vec<&'static str>, pct: Vec<i64> }
impl Split for Percent {
    fn describe(&self) -> &str { "percent split" }
    fn shares(&self, amount: i64, _: &[&'static str]) -> Result<HashMap<&'static str, i64>, String> {
        let total: i64 = self.pct.iter().sum();
        if total != 100 { return Err(format!("percentages add up to {total}, not 100")); }
        Ok(spread(amount, &self.people, &self.pct))
    }
}

// Net balance per member: positive = others owe them. Balances always add up to 0.
struct Group { members: Vec<&'static str>, balance: Mutex<HashMap<&'static str, i64>> }

impl Group {
    fn new(members: &[&'static str]) -> Self {
        Group { members: members.to_vec(), balance: Mutex::new(members.iter().map(|&m| (m, 0)).collect()) }
    }

    fn add_expense(&self, payer: &str, amount: i64, people: &[&'static str], split: &dyn Split) -> Result<(), String> {
        let mut bal = self.balance.lock().unwrap();
        if amount <= 0 { return Err("amount must be positive".into()); }
        if !bal.contains_key(payer) { return Err(format!("{payer} is not in the group")); }
        let shares = split.shares(amount, people)?;
        if let Some(p) = shares.keys().find(|p| !bal.contains_key(*p)) { return Err(format!("{p} is not in the group")); }
        *bal.get_mut(payer).unwrap() += amount; // only now, when everything is valid
        for (p, s) in shares { *bal.get_mut(p).unwrap() -= s; }
        Ok(())
    }

    fn balances(&self) -> Vec<(&'static str, i64)> {
        let bal = self.balance.lock().unwrap();
        self.members.iter().map(|&m| (m, bal[m])).collect()
    }

    // Biggest debtor pays biggest creditor, repeatedly. Ties go to the earlier member.
    fn settle_up(&self) -> Vec<(&'static str, &'static str, i64)> {
        let mut left = self.balance.lock().unwrap().clone();
        let mut pays = vec![];
        loop {
            let (mut debtor, mut creditor): (Option<&'static str>, Option<&'static str>) = (None, None);
            for &m in &self.members {
                if left[m] < 0 && debtor.map_or(true, |d| left[m] < left[d]) { debtor = Some(m); }
                if left[m] > 0 && creditor.map_or(true, |c| left[m] > left[c]) { creditor = Some(m); }
            }
            let (Some(d), Some(c)) = (debtor, creditor) else { return pays };
            let amt = (-left[d]).min(left[c]);
            pays.push((d, c, amt));
            *left.get_mut(d).unwrap() += amt;
            *left.get_mut(c).unwrap() -= amt;
        }
    }
}

fn main() {
    let everyone = ["Rahim", "Nadia", "Tania", "Sabbir"];
    let g = Group::new(&everyone);
    let expenses: Vec<(&str, &str, i64, Vec<&'static str>, Box<dyn Split>)> = vec![
        ("Rahim", "hotel", 4000, everyone.to_vec(), Box::new(Equal)),
        ("Nadia", "dinner", 1200, vec![], Box::new(Exact(vec![("Rahim", 300), ("Nadia", 400), ("Tania", 500)]))),
        ("Tania", "boat", 1000, vec![], Box::new(Percent { people: vec!["Rahim", "Sabbir"], pct: vec![40, 60] })),
        ("Sabbir", "tea", 100, vec!["Rahim", "Tania", "Sabbir"], Box::new(Equal)),
        ("Rahim", "taxi", 1200, vec![], Box::new(Exact(vec![("Rahim", 600), ("Nadia", 500)]))),
    ];
    for (i, (payer, what, amount, people, split)) in expenses.iter().enumerate() {
        match g.add_expense(payer, *amount, people, split.as_ref()) {
            Ok(()) => println!("expense {}: {payer} paid {amount} for {what}, {}", i + 1, split.describe()),
            Err(e) => println!("expense {} refused: {e}", i + 1),
        }
    }
    println!("balances:");
    for (m, b) in g.balances() { println!("  {m:<6} {b:+6}"); }
    let pays = g.settle_up();
    println!("settle up ({} payments):", pays.len());
    for (from, to, amt) in pays { println!("  {from} pays {to} {amt}"); }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static final class SplitException extends Exception {
        private static final long serialVersionUID = 1L;
        SplitException(String msg) { super(msg); }
    }

    // Divide by weights, rounding down; leftover taka go one by one to the first people.
    static Map<String, Integer> spread(int amount, List<String> people, List<Integer> weights) {
        int total = weights.stream().mapToInt(Integer::intValue).sum();
        Map<String, Integer> shares = new LinkedHashMap<>();
        int given = 0;
        for (int i = 0; i < people.size(); i++) {
            int s = amount * weights.get(i) / total;
            shares.put(people.get(i), s);
            given += s;
        }
        for (int i = 0; given < amount; i++, given++) shares.merge(people.get(i % people.size()), 1, Integer::sum);
        return shares;
    }

    // The Strategy: each way of dividing an expense turns (amount, people) into shares.
    interface Split {
        Map<String, Integer> shares(int amount, List<String> people) throws SplitException;
        String describe();
    }

    static final class Equal implements Split {
        public String describe() { return "split equally"; }
        public Map<String, Integer> shares(int amount, List<String> people) throws SplitException {
            if (people.isEmpty()) throw new SplitException("no one to split with");
            return spread(amount, people, people.stream().map(p -> 1).toList());
        }
    }

    record Exact(Map<String, Integer> given) implements Split {
        public String describe() { return "exact split"; }
        public Map<String, Integer> shares(int amount, List<String> people) throws SplitException {
            int total = given.values().stream().mapToInt(Integer::intValue).sum();
            if (total != amount) throw new SplitException("exact shares add up to " + total + ", not " + amount);
            return new HashMap<>(given);
        }
    }

    record Percent(List<String> people, List<Integer> pct) implements Split {
        public String describe() { return "percent split"; }
        public Map<String, Integer> shares(int amount, List<String> ignored) throws SplitException {
            int total = pct.stream().mapToInt(Integer::intValue).sum();
            if (total != 100) throw new SplitException("percentages add up to " + total + ", not 100");
            return spread(amount, people, pct);
        }
    }

    record Payment(String from, String to, int amount) {}

    // Net balance per member: positive = others owe them. Balances always add up to 0.
    static final class Group {
        final List<String> members;
        private final Map<String, Integer> balance = new HashMap<>();

        Group(String... members) {
            this.members = List.of(members);
            for (String m : members) balance.put(m, 0);
        }

        synchronized void addExpense(String payer, int amount, List<String> people, Split split) throws SplitException {
            if (amount <= 0) throw new SplitException("amount must be positive");
            if (!balance.containsKey(payer)) throw new SplitException(payer + " is not in the group");
            Map<String, Integer> shares = split.shares(amount, people);
            for (String p : shares.keySet()) if (!balance.containsKey(p)) throw new SplitException(p + " is not in the group");
            balance.merge(payer, amount, Integer::sum); // only now, when everything is valid
            shares.forEach((p, s) -> balance.merge(p, -s, Integer::sum));
        }

        synchronized int balanceOf(String m) { return balance.get(m); }

        // Biggest debtor pays biggest creditor, repeatedly. Ties go to the earlier member.
        List<Payment> settleUp() {
            Map<String, Integer> left;
            synchronized (this) { left = new HashMap<>(balance); }
            List<Payment> pays = new ArrayList<>();
            while (true) {
                String debtor = null, creditor = null;
                for (String m : members) {
                    if (left.get(m) < 0 && (debtor == null || left.get(m) < left.get(debtor))) debtor = m;
                    if (left.get(m) > 0 && (creditor == null || left.get(m) > left.get(creditor))) creditor = m;
                }
                if (debtor == null || creditor == null) return pays;
                int amt = Math.min(-left.get(debtor), left.get(creditor));
                pays.add(new Payment(debtor, creditor, amt));
                left.merge(debtor, amt, Integer::sum);
                left.merge(creditor, -amt, Integer::sum);
            }
        }
    }

    record Expense(String payer, String what, int amount, List<String> people, Split split) {}

    public static void main(String[] args) {
        Group g = new Group("Rahim", "Nadia", "Tania", "Sabbir");
        List<String> everyone = List.of("Rahim", "Nadia", "Tania", "Sabbir");
        List<Expense> expenses = List.of(
            new Expense("Rahim", "hotel", 4000, everyone, new Equal()),
            new Expense("Nadia", "dinner", 1200, List.of(), new Exact(Map.of("Rahim", 300, "Nadia", 400, "Tania", 500))),
            new Expense("Tania", "boat", 1000, List.of(), new Percent(List.of("Rahim", "Sabbir"), List.of(40, 60))),
            new Expense("Sabbir", "tea", 100, List.of("Rahim", "Tania", "Sabbir"), new Equal()),
            new Expense("Rahim", "taxi", 1200, List.of(), new Exact(Map.of("Rahim", 600, "Nadia", 500))));
        for (int i = 0; i < expenses.size(); i++) {
            Expense e = expenses.get(i);
            try {
                g.addExpense(e.payer(), e.amount(), e.people(), e.split());
                System.out.printf("expense %d: %s paid %d for %s, %s%n", i + 1, e.payer(), e.amount(), e.what(), e.split().describe());
            } catch (SplitException ex) {
                System.out.printf("expense %d refused: %s%n", i + 1, ex.getMessage());
            }
        }
        System.out.println("balances:");
        for (String m : g.members) System.out.printf("  %-6s %+6d%n", m, g.balanceOf(m));
        List<Payment> pays = g.settleUp();
        System.out.printf("settle up (%d payments):%n", pays.size());
        for (Payment p : pays) System.out.printf("  %s pays %s %d%n", p.from(), p.to(), p.amount());
    }
}

#include <algorithm>
#include <cstdio>
#include <map>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>

using Shares = std::map<std::string, int>;

struct SplitError : std::runtime_error {
    using std::runtime_error::runtime_error;
};

// Divide by weights, rounding down; leftover taka go one by one to the first people.
Shares spread(int amount, const std::vector<std::string>& people, const std::vector<int>& weights) {
    int total = 0, given = 0;
    for (int w : weights) total += w;
    Shares shares;
    for (size_t i = 0; i < people.size(); i++) given += shares[people[i]] = amount * weights[i] / total;
    for (size_t i = 0; given < amount; i++, given++) shares[people[i % people.size()]]++;
    return shares;
}

// The Strategy: each way of dividing an expense turns (amount, people) into shares.
class Split {
public:
    virtual ~Split() = default;
    virtual Shares shares(int amount, const std::vector<std::string>& people) const = 0;
    virtual std::string describe() const = 0;
};

class Equal : public Split {
public:
    std::string describe() const override { return "split equally"; }
    Shares shares(int amount, const std::vector<std::string>& people) const override {
        if (people.empty()) throw SplitError("no one to split with");
        return spread(amount, people, std::vector<int>(people.size(), 1));
    }
};

class Exact : public Split {
public:
    explicit Exact(Shares given) : given_(std::move(given)) {}
    std::string describe() const override { return "exact split"; }
    Shares shares(int amount, const std::vector<std::string>&) const override {
        int total = 0;
        for (const auto& [p, v] : given_) total += v;
        if (total != amount)
            throw SplitError("exact shares add up to " + std::to_string(total) + ", not " + std::to_string(amount));
        return given_;
    }

private:
    Shares given_;
};

class Percent : public Split {
public:
    Percent(std::vector<std::string> people, std::vector<int> pct) : people_(std::move(people)), pct_(std::move(pct)) {}
    std::string describe() const override { return "percent split"; }
    Shares shares(int amount, const std::vector<std::string>&) const override {
        int total = 0;
        for (int p : pct_) total += p;
        if (total != 100) throw SplitError("percentages add up to " + std::to_string(total) + ", not 100");
        return spread(amount, people_, pct_);
    }

private:
    std::vector<std::string> people_;
    std::vector<int> pct_;
};

// Net balance per member: positive = others owe them. Balances always add up to 0.
class Group {
public:
    explicit Group(std::vector<std::string> members) : members(std::move(members)) {
        for (const auto& m : this->members) balance_[m] = 0;
    }
    const std::vector<std::string> members;

    void addExpense(const std::string& payer, int amount, const std::vector<std::string>& people, const Split& split) {
        std::lock_guard lock(mu_);
        if (amount <= 0) throw SplitError("amount must be positive");
        if (!balance_.count(payer)) throw SplitError(payer + " is not in the group");
        Shares shares = split.shares(amount, people);
        for (const auto& [p, s] : shares)
            if (!balance_.count(p)) throw SplitError(p + " is not in the group");
        balance_[payer] += amount;  // only now, when everything is valid
        for (const auto& [p, s] : shares) balance_[p] -= s;
    }

    int balanceOf(const std::string& m) {
        std::lock_guard lock(mu_);
        return balance_.at(m);
    }

    // Biggest debtor pays biggest creditor, repeatedly. Ties go to the earlier member.
    std::vector<std::tuple<std::string, std::string, int>> settleUp() {
        Shares left;
        {
            std::lock_guard lock(mu_);
            left = balance_;
        }
        std::vector<std::tuple<std::string, std::string, int>> pays;
        for (;;) {
            std::string debtor, creditor;
            for (const auto& m : members) {
                if (left[m] < 0 && (debtor.empty() || left[m] < left[debtor])) debtor = m;
                if (left[m] > 0 && (creditor.empty() || left[m] > left[creditor])) creditor = m;
            }
            if (debtor.empty() || creditor.empty()) return pays;
            int amt = std::min(-left[debtor], left[creditor]);
            pays.emplace_back(debtor, creditor, amt);
            left[debtor] += amt;
            left[creditor] -= amt;
        }
    }

private:
    std::mutex mu_;
    Shares balance_;
};

int main() {
    std::vector<std::string> everyone{"Rahim", "Nadia", "Tania", "Sabbir"};
    Group g(everyone);
    struct Expense {
        std::string payer, what;
        int amount;
        std::vector<std::string> people;
        std::unique_ptr<Split> split;
    };
    std::vector<Expense> expenses;
    expenses.push_back({"Rahim", "hotel", 4000, everyone, std::make_unique<Equal>()});
    expenses.push_back({"Nadia", "dinner", 1200, {}, std::make_unique<Exact>(Shares{{"Rahim", 300}, {"Nadia", 400}, {"Tania", 500}})});
    expenses.push_back({"Tania", "boat", 1000, {}, std::make_unique<Percent>(std::vector<std::string>{"Rahim", "Sabbir"}, std::vector<int>{40, 60})});
    expenses.push_back({"Sabbir", "tea", 100, {"Rahim", "Tania", "Sabbir"}, std::make_unique<Equal>()});
    expenses.push_back({"Rahim", "taxi", 1200, {}, std::make_unique<Exact>(Shares{{"Rahim", 600}, {"Nadia", 500}})});
    for (size_t i = 0; i < expenses.size(); i++) {
        const auto& e = expenses[i];
        try {
            g.addExpense(e.payer, e.amount, e.people, *e.split);
            std::printf("expense %zu: %s paid %d for %s, %s\n", i + 1, e.payer.c_str(), e.amount, e.what.c_str(), e.split->describe().c_str());
        } catch (const SplitError& err) {
            std::printf("expense %zu refused: %s\n", i + 1, err.what());
        }
    }
    std::printf("balances:\n");
    for (const auto& m : g.members) std::printf("  %-6s %+6d\n", m.c_str(), g.balanceOf(m));
    auto pays = g.settleUp();
    std::printf("settle up (%zu payments):\n", pays.size());
    for (const auto& [from, to, amt] : pays) std::printf("  %s pays %s %d\n", from.c_str(), to.c_str(), amt);
}