A shop's accounting system has two tables that come from different systems: customers, a list of (ref, name, city), and orders, a list of (order_no, ref, amount) with the amount in cents. A ref identifies a customer. Two refs can be compared with == (the same customer or not), and each such comparison is a costly lookup in a remote directory. Refs can also be hashed, which is cheap: equal refs have equal hashes. The two tables use separate ref objects, so an order's ref is equal to, but not the same object as, its customer's.
Write revenue_by_city(customers, orders) that returns (totals, unknown): totals is a list of (city, total amount) pairs sorted by city, for every city with at least one matched order, and unknown is the list of order numbers whose ref matches no customer, in the order of orders. Each customer appears once in customers.
The tests call joined(revenue_by_city, customers, orders), which builds the refs and allows at most n + m comparisons of refs for n customers and m orders, raising TooManyComparisons beyond that. shop(n_customers, n_orders, seed) generates the plain tables that joined takes (codes instead of refs).
Examples
Input: joined(revenue_by_city, [("C1", "Ada", "Cork"), ("C2", "Bo", "Faro"), ("C3", "Cy", "Cork")], [(1, "C3", 500), (2, "C9", 70), (3, "C1", 250), (4, "C3", 1)])
Output: (([("Cork", 751)], [2]), True)
Input: joined(revenue_by_city, [], [(7, "C1", 10)])
Output: (([], [7]), True)
Constraints
- Up to 30,000 customers and 60,000 orders.
- The budget counts comparisons of refs; hashing is free.
Goals
- Replace a nested search with a dictionary built once, turning n * m work into n + m
- Understand that dictionaries and sets compare keys only when their hashes match
- Aggregate joined records with a dictionary of totals