Match payments to invoices by memo or amount

Problem Statement

You are provided with two lists: a list of invoices and a list of payments. Each invoice has an id and an amount. Each payment has an amount, a memo string, and a date.

Your task is to reconcile these lists according to the following precedence rules:

1. ID Match: If an invoice id is found anywhere inside a payment's memo (as a substring), match them. If multiple invoices match a single payment memo, prioritize the one with the highest amount.
2. Amount Match: If no invoice ID is found in the memo, match the payment to an unpaid invoice with the exact same amount.
3. Tie-breaking: If multiple invoices have the same amount, match the payment to the invoice with the earliest date.

Function Signature

def reconcile_payments(invoices, payments):
    # invoices: List of dicts {'id': str, 'amount': float, 'date': str}
    # payments: List of dicts {'amount': float, 'memo': str, 'date': str}
    # Return a list of tuples: (payment_index, matched_invoice_id)
    pass

Example

Input: invoices = [{'id': 'INV-001', 'amount': 100.0, 'date': '2023-01-01'}, {'id': 'INV-002', 'amount': 200.0, 'date': '2023-01-02'}] payments = [{'amount': 100.0, 'memo': 'Paid INV-001'}, {'amount': 200.0, 'memo': 'Final balance'}]

Output: [(0, 'INV-001'), (1, 'INV-002')]

Constraints

• Number of invoices and payments: up to 10,000 each.
• Invoice IDs are unique.
• Each payment can be matched to at most one invoice.