Split-Tender Payment Events with Gift Card Expiry, ZIP Surcharges and Refunds

A retail customer often pays for one purchase with several payment methods, for example covering a 100-dollar purchase with a 40-dollar gift card plus 60 dollars on a credit card. This is called a split-tender transaction, and point-of-sale payment systems for retail merchants must support it. Write the part of such a system that processes split-tender payments. For each purchase, the system first spends the customer's available gift card balance and charges whatever remains to the customer's credit card. Given a chronological stream of payment events, compute the result of every event. The rules come in four layers, and your function must apply all of them together: basic split tendering, gift card expiration and priority, regional credit card surcharges, and refunds. ### Function Signature ```python def process_events(events: list[str], surcharge_rates: list[str]) -> list[str]: ``` `events` holds one line per event, in chronological order. Each line uses one of three comma-separated formats: ```text timestamp,ADD_GIFTCARD,customer_id,card_id,amount,valid_before timestamp,CHARGE,charge_id,customer_id,amount,zip_code timestamp,REFUND,charge_id,refund_amount ``` Each entry of `surcharge_rates` has the format `start_zip-end_zip:rate`. For example, `90000-99999:0.05` means that a charge whose ZIP code is between `90000` and `99999` inclusive pays a 5% surcharge on its credit card portion. Return a list with exactly one string per event, in the same order as `events`. ### Rules All money amounts in the input and the output are non-negative integers counting cents: `4000` means 40.00 dollars. Output amounts are written as plain base-10 integers. #### Layer 1 — Gift cards and basic split tendering - Customers start with no gift cards. `ADD_GIFTCARD` gives customer `customer_id` a new gift card `card_id` whose balance is `amount`. Each card keeps its own balance, and a customer may hold any number of cards at once. A card belongs to one customer and is never used for another customer's charges. - The output for an `ADD_GIFTCARD` event is the empty string `""`. - A `CHARGE` of `amount` for `customer_id` is paid from that customer's usable gift cards first (layer 2 says which cards are usable and in which order). In priority order, take from each card the smaller of its balance and the amount still unpaid, and subtract it from that card's balance, so one card is fully drained before the next one is touched. Whatever is still unpaid after the usable cards run out is the credit card portion; if the cards cover everything, the credit card portion is 0. - The output for a `CHARGE` event is the final credit card charge, followed by one `,card_id:amount_used` item for every card that supplied a positive amount to this charge: ```text CC_CHARGE_AMOUNT,GIFT_CARD_ID_1:AMOUNT_USED,GIFT_CARD_ID_2:AMOUNT_USED ``` The card items are listed in ascending `card_id` order, not in the order the cards were drained. If no card was used, the output is only the credit card amount, for example `"1000"`. `CC_CHARGE_AMOUNT` (written `CC_CHARGE` below) includes the surcharge from layer 3. #### Layer 2 — Expiration and card priority - A card created by `ADD_GIFTCARD` is valid at time `T` only if `T < valid_before`. When `T >= valid_before`, the card is expired and its remaining balance is void for good. - Cards created by refunds (layer 4) have no expiration date and are always valid. Every `ADD_GIFTCARD` line carries an integer `valid_before`, so refund-created cards are the only cards without an expiration date. - For a charge at time `T`, the usable cards are the customer's cards that are valid at `T` and have a positive balance. They are used in this priority order: 1. cards with a finite `valid_before`, earliest `valid_before` first; 2. after all of those, cards with no expiration date; 3. cards that share the same expiration, including two cards that both have no expiration date, in ascending `card_id` order. #### Layer 3 — Regional surcharges - Find the range in `surcharge_rates` that contains the charge's `zip_code`, comparing ZIP codes as numbers. If no range contains it, the rate is 0. - The surcharge applies only to the credit card portion; amounts paid by gift cards are never surcharged. `CC_CHARGE = credit_card_portion + credit_card_portion × rate`. For example, a credit card portion of `10000` at rate `0.05` gives `CC_CHARGE = 10500`. - Every input guarantees that the exact value of `credit_card_portion × rate` is a whole number of cents. Output that exact value; no rounding is involved. #### Layer 4 — Refunds For a `REFUND` of `refund_amount` against an earlier `charge_id`: - Real money first: `CC_REFUND` is the smaller of `refund_amount` and the `CC_CHARGE` that the referenced charge actually put on the credit card, surcharge included. - Store credit second: `GC_REFUND = refund_amount - CC_REFUND`. If `GC_REFUND` is positive, create a new gift card for the customer of the original charge, with `card_id` equal to `REFUND_` followed by the charge id (for `chg_1` it is `REFUND_chg_1`), balance `GC_REFUND`, and no expiration date. It takes part in later charges like any other card. If `GC_REFUND` is 0, no card is created. - A refund never puts money back on the gift cards that the original charge drew from. - The output for a `REFUND` event is `CC_REFUND,GC_REFUND`, for example `"10500,1500"` or `"3000,0"`. #### Comparing card ids Wherever `card_id` values are ordered, compare them as strings by character code (ASCII order, which is Python's default string comparison). Uppercase letters sort before lowercase letters, so `REFUND_chg_1` comes before `gc_2`. ### Constraints - `1 <= len(events) <= 10^4` and `0 <= len(surcharge_rates) <= 1000`. - Every line is well formed. Timestamps are integers with `0 <= timestamp <= 10^9` and are non-decreasing along `events`; events with equal timestamps take effect in list order. - `1 <= valid_before <= 10^9`. A card may be added already expired; it is then never usable. - `1 <= amount <= 10^8` in `ADD_GIFTCARD` and `CHARGE` lines. - `customer_id`, `card_id` and `charge_id` are 1 to 20 characters drawn from ASCII letters, digits and underscores. `card_id` values in `ADD_GIFTCARD` lines are unique and never start with `REFUND_`. `charge_id` values are unique across `CHARGE` lines. - `zip_code` is exactly five digits and may start with 0. Each range has five-digit bounds with `start_zip <= end_zip`, and no two ranges overlap. - Each `rate` is a decimal number with at most 4 digits after the decimal point and `0 <= rate <= 1`. - Every `REFUND` references a `CHARGE` that appears earlier in `events`, and each `charge_id` is refunded at most once. `refund_amount` is at least 1 and at most the total originally paid for that charge: its `amount` plus its surcharge. - Every output amount is at most `2 * 10^8`, which fits in a signed 32-bit integer. The sum of one customer's balances across all cards can exceed `2^31 - 1` but stays below `2^53`. ### Examples **Example 1** ```text Input: events = [ "1,ADD_GIFTCARD,cust1,gc1,5000,10", "2,ADD_GIFTCARD,cust1,gc2,4000,5", "3,CHARGE,chg1,cust1,6000,10000", "11,CHARGE,chg2,cust1,1000,10000" ] surcharge_rates = [] Output: ["", "", "0,gc1:2000,gc2:4000", "1000"] ``` At time 3 both cards are valid. `gc2` expires earlier (5 versus 10), so it is drained for 4000 first, and `gc1` supplies the remaining 2000. The output lists `gc1` before `gc2` because the items are sorted by `card_id`. At time 11 both cards have expired (`11 >= 10` and `11 >= 5`), so the 3000 left on `gc1` is void and the whole 1000 goes to the credit card. There are no surcharge ranges, so the rate is 0. **Example 2** ```text Input: events = [ "1,ADD_GIFTCARD,cust1,gc1,5000,10", "2,CHARGE,chg1,cust1,15000,90210", "3,REFUND,chg1,12000" ] surcharge_rates = ["90000-99999:0.05"] Output: ["", "10500,gc1:5000", "10500,1500"] ``` `gc1` is valid at time 2 and covers 5000 of the 15000, leaving a credit card portion of 10000. ZIP `90210` falls in `90000-99999`, so the surcharge is `10000 × 0.05 = 500` and `CC_CHARGE` is 10500. The refund of 12000 returns 10500 to the credit card, which is everything charged there, and the remaining 1500 becomes a new non-expiring card `REFUND_chg1` for `cust1` with balance 1500. **Example 3** ```text Input: events = [ "1,ADD_GIFTCARD,cust_1,gc_1,10000,10", "2,CHARGE,chg_1,cust_1,20000,15000", "3,REFUND,chg_1,21000", "15,CHARGE,chg_2,cust_1,5000,15000", "16,ADD_GIFTCARD,cust_1,gc_2,3000,20", "17,CHARGE,chg_3,cust_1,9000,15000" ] surcharge_rates = ["10000-20000:0.10"] Output: [ "", "11000,gc_1:10000", "11000,10000", "0,REFUND_chg_1:5000", "", "1100,REFUND_chg_1:5000,gc_2:3000" ] ``` - Time 2: `gc_1` is drained for 10000. The credit card portion is 10000, and the 10% surcharge makes `CC_CHARGE` 11000. - Time 3: the refund of 21000 returns 11000 to the credit card and creates the non-expiring card `REFUND_chg_1` with balance 10000. - Time 15: `gc_1` is empty and also expired. `REFUND_chg_1` covers all 5000, keeping 5000 of its balance, and the surcharge on a credit card portion of 0 is 0. - Time 17: `gc_2` has a finite expiration, so it is used before the non-expiring `REFUND_chg_1`. `gc_2` gives 3000, `REFUND_chg_1` gives its remaining 5000, and the last 1000 goes to the credit card, which becomes 1100 with the surcharge. In the output, `REFUND_chg_1` is listed before `gc_2` because uppercase `R` sorts before lowercase `g`.