Python exercise: reconcile duplicate receipt counts without losing multiplicity

Operation contract

Two bounded batches represent expected and scanned receipt IDs. Counter subtraction reports missing and unexpected occurrences separately. The expected batch contains R41 twice; a set comparison would erase that discrepancy. The function returns sorted count pairs so output order is independent of input arrival. It validates every identifier before counting and does not change either caller list.

Failure and ownership boundary

Counter subtraction discards nonpositive results, which is correct for each directional gap but wrong for a signed ledger balance. An identifier appearing in both batches can still have a positive gap in one direction. For very large streams, batch materialization and sorted output need size limits or a persisted counting strategy. Python Counter and deque: counts, queues and bounded history, Python reconciliation exercise: reject duplicate IDs before comparing ledgers and Python collections reference: selection costs and retained ownership give nearby contracts.

Working program

from collections import Counter

def receipt_gaps(expected, scanned):
    for batch in (expected, scanned):
        if type(batch) is not list or len(batch) > 100:
            raise ValueError("batch cap")
        if any(type(identifier) is not str or len(identifier) != 3 or identifier[0] != "R" or not identifier[1:].isascii() or not identifier[1:].isdigit() for identifier in batch):
            raise ValueError("receipt identifier")
    due, seen = Counter(expected), Counter(scanned)
    return sorted((due - seen).items()), sorted((seen - due).items())

print(receipt_gaps(["R41", "R41", "R42"], ["R41", "R43"]))
try:
    receipt_gaps(["R41"], ["R４１"])
except ValueError:
    print("non-ASCII identifier rejected")

Output

([('R41', 1), ('R42', 1)], [('R43', 1)])
non-ASCII identifier rejected

Costs and limits

Counting n+m values takes expected O(n+m) dictionary work and O(u) key storage, where u is the number of distinct IDs. Sorting u results costs O(u log u). The 100-entry cap bounds this teaching exercise.

Common Mistakes

• A set comparison loses duplicate counts.
• Directional Counter subtraction is not a signed net balance.

Connected lessons

Python Counter and deque: counts, queues and bounded history, Python reconciliation exercise: reject duplicate IDs before comparing ledgers, Python collections reference: selection costs and retained ownership.