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

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:

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:

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

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

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

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.