Build a Flexible Expense Rules Engine

You are building a rules engine for a corporate credit card product. Employees use company cards for business expenses, and managers define policies that should flag invalid expenses. Each expense is provided as a dictionary with string keys and values, for example: `{"expense_id":"001","trip_id":"001","amount_usd":"49.99","expense_type":"client_hosting","vendor_type":"restaurant","vendor_name":"Outback Roadhouse"}` Implement: `evaluate_rules(rules, expenses) -> result` Requirements: - Evaluate both expense-level and trip-level policies. - Choose a return type that clearly reports which expenses or trips violated which rules. - Support multiple violations for the same expense or trip. - Design the rule representation so it can be extended later and created through an API. Initially support these rules: 1. No restaurant expense may exceed `$75` when `vendor_type == "restaurant"`. 2. No airfare expenses when `expense_type == "airfare"`. 3. No entertainment expenses when `expense_type == "entertainment"`. 4. No single expense may exceed `$250`. 5. The total amount for a trip may not exceed `$2000`. 6. Total meal expenses for a trip may not exceed `$200`. Then extend the design to support composite rules built from simpler predicates: - `(vendor_type == "restaurant") AND (expense_type == "meals") AND (amount_usd > 50)` - `((expense_type == "entertainment") AND (amount_usd > 100)) OR (expense_type == "client_hosting")` - `(amount_usd > 100) AND NOT (vendor_name == "Staples")` Assume some predicates may be expensive to evaluate, including ones that require database access. Explain and, if time permits, implement practical optimizations for rule evaluation, such as short-circuiting, predicate ordering, caching, or pre-aggregation.