Match payments to invoices with fallback rules

Problem Statement

You are building a reconciliation engine for a payment processor. Given a list of payments and a list of invoices, your goal is to match each payment to a corresponding invoice.

Each payment and invoice has an id and an amount. A payment can only be matched to one invoice, and an invoice can only be matched to one payment. Implement a function match_payments(payments, invoices) that follows these priority rules:

1. Exact Match: Match by id if IDs match exactly and amounts match exactly.
2. Amount-Only Match: If ID matching fails, match by amount if there is a unique invoice with that amount.
3. Fuzzy Amount Match: If multiple invoices have the same amount, or no invoice matches the amount, try to match by a 'tolerance' window (e.g., if the payment is within +/- 1% of the invoice amount). If multiple fit the tolerance, prioritize the closest amount.

Function Signature

def match_payments(payments, invoices):
    # payments: list of dicts {'id': str, 'amount': float}
    # invoices: list of dicts {'id': str, 'amount': float}
    # return: list of tuples (payment_id, invoice_id) for successful matches

Example

Input: payments = [{'id': 'p1', 'amount': 100.0}, {'id': 'p2', 'amount': 205.0}] invoices = [{'id': 'i1', 'amount': 100.0}, {'id': 'i2', 'amount': 200.0}]

Output: [('p1', 'i1'), ('p2', 'i2')] (p2 matches i2 because 205 is within a 3% tolerance window of 200)

Constraints

• Number of payments and invoices: up to 10,000 each.
• Amounts are non-negative floats.
• If a payment cannot be matched, exclude it from the final result.

Edge Cases

• Empty lists.
• Multiple invoices having the exact same amount.
• Floating point precision issues (use a small epsilon for comparisons).