Design a Bill-Splitting App (Splitwise).

# splitwise.py, part 1: people, groups and money (always integer paise, never floats)
from __future__ import annotations

import heapq
import itertools
import threading
from abc import ABC, abstractmethod
from collections import defaultdict
from dataclasses import dataclass, field
from decimal import ROUND_FLOOR, Decimal
from urllib.parse import quote


def rupees(paise: int) -> str:
    return f"₹{paise / 100:,.2f}"


@dataclass(frozen=True)
class User:
    user_id: str
    name: str
    upi_id: str  # the VPA a friend pays into, e.g. name@bank


@dataclass
class Group:
    group_id: str
    name: str
    members: dict[str, User] = field(default_factory=dict)


@dataclass(frozen=True)
class Split:
    user_id: str
    amount: int  # paise this person consumed


@dataclass(frozen=True)
class Expense:
    expense_id: str
    group_id: str
    paid_by: str
    amount: int
    splits: tuple[Split, ...]
    note: str


@dataclass(frozen=True)
class Transfer:  # "from_user pays to_user": a suggested or recorded settlement
    from_user: str
    to_user: str
    amount: int

# part 2: one interface, three ways to split; each one guarantees the parts add up exactly
class SplitStrategy(ABC):
    @abstractmethod
    def split(self, amount: int) -> list[Split]: ...


class EqualSplit(SplitStrategy):
    def __init__(self, user_ids: list[str]) -> None:
        self.user_ids = sorted(user_ids)

    def split(self, amount: int) -> list[Split]:
        base, extra = divmod(amount, len(self.user_ids))  # ₹100 / 3 = 33.34 + 33.33 + 33.33
        return [Split(u, base + (1 if i < extra else 0)) for i, u in enumerate(self.user_ids)]


class ExactSplit(SplitStrategy):
    def __init__(self, shares: dict[str, int]) -> None:
        self.shares = shares

    def split(self, amount: int) -> list[Split]:
        if sum(self.shares.values()) != amount:
            raise ValueError(f"exact shares add up to {rupees(sum(self.shares.values()))}, not {rupees(amount)}")
        return [Split(u, a) for u, a in sorted(self.shares.items())]


class PercentSplit(SplitStrategy):
    def __init__(self, percents: dict[str, str]) -> None:
        self.percents = {u: Decimal(p) for u, p in percents.items()}

    def split(self, amount: int) -> list[Split]:
        if sum(self.percents.values()) != 100:
            raise ValueError("percentages must add up to 100")
        raw = {u: amount * p / 100 for u, p in self.percents.items()}
        parts = {u: int(r.to_integral_value(ROUND_FLOOR)) for u, r in raw.items()}
        leftover = amount - sum(parts.values())  # hand the leftover paise to the largest remainders
        for u in sorted(raw, key=lambda u: (parts[u] - raw[u], u))[:leftover]:
            parts[u] += 1
        return [Split(u, a) for u, a in sorted(parts.items())]

# part 3: the ledger: net balances, and the pairwise view the simplifier saves you from
class Ledger:
    def __init__(self) -> None:
        self.net: dict[str, int] = defaultdict(int)  # > 0: the group owes you; < 0: you owe
        self._owes: dict[tuple[str, str], int] = defaultdict(int)  # (debtor, creditor) -> paise

    def apply(self, payer: str, splits: list[Split] | tuple[Split, ...], sign: int = 1) -> None:
        for s in splits:
            self.net[payer] += sign * s.amount
            self.net[s.user_id] -= sign * s.amount
            if s.user_id != payer:
                self._owes[(s.user_id, payer)] += sign * s.amount

    def pairwise(self) -> list[Transfer]:
        out = []
        for (a, b), amt in self._owes.items():
            back = self._owes.get((b, a), 0)
            if amt - back > 0:
                out.append(Transfer(a, b, amt - back))
        return out


class DebtSimplifier:
    """Greedy min cash flow: the biggest debtor pays the biggest creditor, repeat. At most n - 1 transfers."""

    def simplify(self, net: dict[str, int]) -> list[Transfer]:
        creditors = [(-amt, u) for u, amt in net.items() if amt > 0]
        debtors = [(amt, u) for u, amt in net.items() if amt < 0]
        heapq.heapify(creditors)
        heapq.heapify(debtors)
        out = []
        while creditors and debtors:
            c_amt, c = heapq.heappop(creditors)
            d_amt, d = heapq.heappop(debtors)
            pay = min(-c_amt, -d_amt)
            out.append(Transfer(d, c, pay))
            if -c_amt > pay:
                heapq.heappush(creditors, (c_amt + pay, c))
            if -d_amt > pay:
                heapq.heappush(debtors, (d_amt + pay, d))
        return out

# part 4: the service: every write is one atomic step per group (the "expense RPC")
class SplitService:
    def __init__(self) -> None:
        self.groups: dict[str, Group] = {}
        self.ledgers: dict[str, Ledger] = {}
        self.expenses: dict[str, Expense] = {}
        self._locks: dict[str, threading.Lock] = defaultdict(threading.Lock)
        self._ids = itertools.count(1)

    def create_group(self, group_id: str, name: str, members: list[User]) -> Group:
        g = Group(group_id, name, {m.user_id: m for m in members})
        self.groups[group_id], self.ledgers[group_id] = g, Ledger()
        return g

    def add_expense(self, group_id: str, paid_by: str, amount: int, how: SplitStrategy, note: str) -> Expense:
        g = self.groups[group_id]
        splits = how.split(amount)
        if amount <= 0 or paid_by not in g.members or any(s.user_id not in g.members for s in splits):
            raise ValueError("payer and everyone in the split must be in the group, and the amount > 0")
        with self._locks[group_id]:
            e = Expense(f"E{next(self._ids)}", group_id, paid_by, amount, tuple(splits), note)
            self.expenses[e.expense_id] = e
            self.ledgers[group_id].apply(paid_by, splits)
        return e

    def delete_expense(self, expense_id: str) -> None:
        e = self.expenses[expense_id]
        with self._locks[e.group_id]:
            del self.expenses[expense_id]
            self.ledgers[e.group_id].apply(e.paid_by, e.splits, sign=-1)  # reverse it exactly

    def settle_up(self, group_id: str, t: Transfer) -> None:
        with self._locks[group_id]:  # paying someone back is an expense the receiver "consumed"
            self.ledgers[group_id].apply(t.from_user, [Split(t.to_user, t.amount)])

    def suggested(self, group_id: str) -> list[Transfer]:
        with self._locks[group_id]:
            return DebtSimplifier().simplify(dict(self.ledgers[group_id].net))

    def upi_link(self, group_id: str, t: Transfer) -> str:
        payee = self.groups[group_id].members[t.to_user]
        q = {"pa": payee.upi_id, "pn": payee.name, "am": f"{t.amount / 100:.2f}", "cu": "INR", "tn": f"{self.groups[group_id].name} settle-up"}
        return "upi://pay?" + "&".join(f"{k}={quote(v, safe='@')}" for k, v in q.items())

# part 5: a Goa trip with four friends
if __name__ == "__main__":
    people = [User(u, u.title(), f"{u}.demo@upi") for u in ("aarav", "diya", "kabir", "meera")]
    app = SplitService()
    app.create_group("goa", "Goa trip", people)
    everyone = [p.user_id for p in people]
    app.add_expense("goa", "aarav", 1_200_000, EqualSplit(everyone), "hotel")
    app.add_expense("goa", "diya", 250_000, ExactSplit({"aarav": 70_000, "diya": 60_000, "kabir": 80_000, "meera": 40_000}), "dinner")
    app.add_expense("goa", "kabir", 100_000, PercentSplit({"aarav": "25", "diya": "25", "kabir": "10", "meera": "40"}), "cab")
    app.add_expense("goa", "meera", 10_000, EqualSplit(["aarav", "diya", "meera"]), "chai")
    app.add_expense("goa", "kabir", 600_000, EqualSplit(everyone), "petrol")

    ledger = app.ledgers["goa"]
    print({u: rupees(v) for u, v in ledger.net.items()})
    assert sum(ledger.net.values()) == 0  # money is conserved, to the paisa
    plan = app.suggested("goa")
    print(len(ledger.pairwise()), "pairwise debts ->", len(plan), "transfers")  # 6 -> 3
    for t in plan:
        print(f"  {t.from_user} pays {t.to_user} {rupees(t.amount)}")

    first = plan[0]
    print(app.upi_link("goa", first))
    app.settle_up("goa", first)  # Meera tapped the link and paid; record it
    print("after settle-up:", [(t.from_user, t.to_user, rupees(t.amount)) for t in app.suggested("goa")])

    try:
        app.add_expense("goa", "diya", 50_000, PercentSplit({"diya": "50", "kabir": "40"}), "snacks")
    except ValueError as e:
        print("rejected:", e)

{'aarav': '₹6,516.66', 'diya': '₹-2,883.33', 'kabir': '₹1,600.00', 'meera': '₹-5,233.33'}
6 pairwise debts -> 3 transfers
  meera pays aarav ₹5,233.33
  diya pays kabir ₹1,600.00
  diya pays aarav ₹1,283.33
upi://pay?pa=aarav.demo@upi&pn=Aarav&am=5233.33&cu=INR&tn=Goa%20trip%20settle-up
after settle-up: [('diya', 'kabir', '₹1,600.00'), ('diya', 'aarav', '₹1,283.33')]
rejected: percentages must add up to 100