Transit Wallet Ledger: Expiring Vouchers, Zone Fees and Refunds

A city transit app lets riders pay for passes with travel vouchers (prepaid credit, often promotional, that expires) and covers any shortfall with the rider's linked bank card. Build the ledger engine that processes a chronological stream of wallet events and reports the outcome of each one.

def process_ledger(events: list[str], fee_bands: list[str]) -> list[str]:

Each event is a |-separated line, and timestamps are non-decreasing integers:

t|CREDIT|rider|voucher_id|amount|expires_at
t|PURCHASE|order_id|rider|amount|zone
t|REFUND|order_id|amount

Each fee_bands entry looks like lo-hi:bps. A purchase whose integer zone lies in [lo, hi] pays a fee of bps basis points (1 bps = 0.01%) on its card portion. All money values are integer cents. Return exactly one output line per event.

Part 1: Vouchers, then card

CREDIT stores a voucher for the rider and outputs t CREDIT <voucher_id> <amount>. A PURCHASE draws from the rider's vouchers until the amount is covered or the vouchers run out, and the rest goes on the card. Output:

t PURCHASE <order_id> vouchers=<V> card=<C> fee=<F> charged=<C+F>

Part 2: Expiry and priority

A voucher is usable only while t < expires_at. Spend usable vouchers in order of earliest expires_at first. If two vouchers have the same expires_at, spend the one with the lexicographically smaller voucher_id first. A voucher can be partly spent and keeps its remaining balance.

Part 3: Zone fees

F = round_half_up(C * bps / 10000), computed with integers only. If several bands contain the zone, the first one listed wins. If no band contains the zone, F = 0.

Part 4: Refunds

REFUND returns money for an earlier order:

• The money goes back to the card first, up to the card portion not yet refunded. Fees are never refunded.
• Anything left over is returned as a new voucher for the same rider, up to the voucher-paid portion not yet refunded. The new voucher's id is RF-<order_id>-<k>, where k is that order's refund count, including this refund. It expires at t + 90.
• Output t REFUND <order_id> card=<X> credit=<Y>, and append voucher=<id> if Y > 0.
• If the order is unknown, or the amount exceeds what is still refundable, output t REFUND <order_id> REJECTED and change nothing.

Example

fee_bands = ["4000-4999:250", "9000-9499:175", "9100-9199:999"]
events =
10|CREDIT|ana|v-b|1500|200
12|CREDIT|ana|v-a|800|200
15|CREDIT|ana|v-c|1000|50
20|PURCHASE|o1|ana|2000|4410
60|PURCHASE|o2|ana|3000|9120
70|REFUND|o2|1500
75|PURCHASE|o3|ana|900|1000
80|REFUND|o2|800
81|REFUND|o9|100
100|PURCHASE|o4|ana|700|4000
110|REFUND|o1|2500

Output:

10 CREDIT v-b 1500
12 CREDIT v-a 800
15 CREDIT v-c 1000
20 PURCHASE o1 vouchers=2000 card=0 fee=0 charged=0
60 PURCHASE o2 vouchers=1300 card=1700 fee=30 charged=1730
70 REFUND o2 card=1500 credit=0
75 PURCHASE o3 vouchers=0 card=900 fee=0 charged=900
80 REFUND o2 card=200 credit=600 voucher=RF-o2-2
81 REFUND o9 REJECTED
100 PURCHASE o4 vouchers=600 card=100 fee=3 charged=103
110 REFUND o1 REJECTED

At t=20, v-c expires first, so it is spent first. Then v-a beats v-b on the id tie-break. At t=60, zone 9120 matches two bands, and the first one (175 bps) wins: 1700 × 0.0175 = 29.75, which rounds to 30. At t=100, the refund voucher from t=80 pays 600, and the 2.5-cent fee rounds up to 3.

Constraints

• Up to 10^5 events. Amounts are positive and at most 10^9.
• Voucher ids are unique. Order ids are unique across purchases.