Match payments to invoices by memo and amount

A billing system has to match incoming payments to open invoices. Both arrive as comma-separated strings.

• Invoice: invoice_id,amount,due_date. The amount is an integer in cents. The due date is YYYY-MM-DD.
• Payment: payment_id,amount,memo. The memo is free text written by the customer. It may be empty, and it may contain commas. When the customer names an invoice, the memo contains Paying off: <invoice_id>. Match the phrase in any letter case, with optional spaces around the colon.

Implement Reconciler(invoice_lines, tolerance=0) with match(payment_line) -> str and reconcile(payment_lines) -> list[str]. Process payments in order. Each invoice can be paid only once. Return "<payment_id> pays <invoice_id> (paid <payment amount>, invoiced <invoice amount>, due <due_date>, by <rule>)" or "<payment_id> unmatched".

Interviewers usually add the rules one part at a time:

1. Memo (by memo): if the memo names an invoice, the payment pays that invoice. If the named invoice does not exist or is already paid, the payment is unmatched. Do not fall back to the other rules.
2. Exact amount (by amount): if the memo names no invoice, pay the open invoice whose amount equals the payment. If several match, choose the earliest due date, then the smallest invoice id.
3. Tolerance (by tolerance): if there is still no match and tolerance > 0, pay the open invoice within tolerance cents of the payment. Choose the smallest difference, then the earliest due date, then the smallest invoice id.

Constraints

• Up to 10^5 invoices and 10^5 payments.
• Invoice ids are unique and contain no spaces or commas.

Example

invoices = ["inv_a,5000,2026-03-10", "inv_b,2500,2026-02-01",
            "inv_c,2500,2026-01-15", "inv_d,9900,2026-04-01"]
r = Reconciler(invoices, tolerance=200)

r.match("p1,5000,Paying off: inv_a")
  -> "p1 pays inv_a (paid 5000, invoiced 5000, due 2026-03-10, by memo)"
r.match("p2,2500,thanks, see you")
  -> "p2 pays inv_c (paid 2500, invoiced 2500, due 2026-01-15, by amount)"
r.match("p3,9800,")
  -> "p3 pays inv_d (paid 9800, invoiced 9900, due 2026-04-01, by tolerance)"
r.match("p4,5000,paying off:inv_a")
  -> "p4 unmatched"      # inv_a is already paid

Later follow-ups can include partial payments, one payment covering several invoices, and matching only within the same customer.