algorithm.py

"""
algorithm.py — Settle-Kar Debt Simplification Engine
=====================================================

Uses a greedy algorithm to reduce the number of cash handovers needed
to settle a group's shared expenses.

Complexity: O(n log n) per iteration due to heap-based selection.
Worst-case transactions: n - 1  (always strictly fewer than naive pairwise).
"""

import heapq


def simplify_debts(net_balances: dict, user_names: dict) -> list[dict]:
    """
    Parameters
    ----------
    net_balances : dict  {user_id: float}
        Positive  → creditor (is owed money)
        Negative  → debtor   (owes money)
        Zero      → settled

    user_names : dict  {user_id: str}
        Human-readable names for output.

    Returns
    -------
    list of dicts:
        [
          {
            "from_id":   <int>,
            "from_name": <str>,
            "to_id":     <int>,
            "to_name":   <str>,
            "amount":    <float>   # rounded to 2 decimal places
          },
          ...
        ]
    """
    EPSILON = 1e-6  # ignore floating-point dust

    # Max-heaps via negation (Python's heapq is min-heap only)
    # creditors: (-balance, user_id)
    # debtors:   (-abs_balance, user_id)  i.e. (balance, user_id) since balance < 0
    creditors = []
    debtors   = []

    for uid, balance in net_balances.items():
        balance = round(balance, 6)
        if balance > EPSILON:
            heapq.heappush(creditors, (-balance, uid))   # largest credit first
        elif balance < -EPSILON:
            heapq.heappush(debtors,   (balance,  uid))   # largest debt first (most negative)

    transactions = []

    while creditors and debtors:
        # Pop largest creditor and largest debtor
        neg_credit, creditor_id = heapq.heappop(creditors)
        debt,       debtor_id   = heapq.heappop(debtors)

        credit    = -neg_credit        # positive
        debt_abs  = -debt              # positive

        # Amount transferred is the minimum of the two
        transfer = min(credit, debt_abs)
        transfer = round(transfer, 2)

        transactions.append({
            'from_id':   debtor_id,
            'from_name': user_names.get(debtor_id, f'User {debtor_id}'),
            'to_id':     creditor_id,
            'to_name':   user_names.get(creditor_id, f'User {creditor_id}'),
            'amount':    transfer,
        })

        # Update residual balances
        new_credit = round(credit   - transfer, 6)
        new_debt   = round(debt_abs - transfer, 6)

        if new_credit > EPSILON:
            heapq.heappush(creditors, (-new_credit, creditor_id))

        if new_debt > EPSILON:
            heapq.heappush(debtors, (-new_debt, debtor_id))

    return transactions


# ── Quick self-test ───────────────────────────────────────────────────────────
if __name__ == '__main__':
    # Classic chain:  A paid for B, B paid for C → A pays C directly
    net = {1: 300.0, 2: 0.0, 3: -300.0}
    names = {1: 'Ali', 2: 'Bilal', 3: 'Carla'}
    result = simplify_debts(net, names)
    print("Test 1 — simple chain:")
    for t in result:
        print(f"  {t['from_name']} → {t['to_name']}: {t['amount']} PKR")

    print()

    # Four people: mixed debts
    net2 = {1: 700, 2: -200, 3: -300, 4: -200}
    names2 = {1: 'Ali', 2: 'Bilal', 3: 'Carla', 4: 'Dawood'}
    result2 = simplify_debts(net2, names2)
    print("Test 2 — multi-person:")
    for t in result2:
        print(f"  {t['from_name']} → {t['to_name']}: {t['amount']} PKR")