Exact Change at the Mossback Bridge
The keeper of Mossback Bridge accepts no overpayment and gives no change.
A traveller arrives with a pouch of coins in a fixed order, and the crossing has a fixed price. The keeper inspects the coins one at a time, from the front of the pouch, and keeps a pile on the plank in front of him:
- If adding the inspected coin to the pile would keep the pile's total at or below the price, the coin is added to the pile.
- Otherwise the coin is handed back and the keeper moves on to the next coin.
- The moment the pile's total is exactly the price, the keeper stops inspecting; any coins still in the pouch are never looked at.
Write exactToll(coins, toll).
coinsis a list of positive integers, in the order they are inspected. It may be empty.tollis a non-negative integer.
Return the number of coins the keeper inspected before stopping — that is, the 1-based position of the coin whose addition brought the pile to exactly toll. If toll is 0, the pile already matches before any coin is inspected, so return 0. If the whole pouch is inspected and the pile never equals toll exactly, return -1.
examples
- case 1
coins of [3, 7, 4, 1, 5], toll of 84 — 3 is added (pile 3), 7 would overshoot and is handed back, 4 is added (pile 7), 1 is added (pile 8, exactly the toll). The final 5 is never inspected. - case 2
coins of [5, 5], toll of 3-1 — both coins would overshoot, the pile stays at 0, and the pouch runs out. - case 3
coins of [2], toll of 00 — the empty pile already matches the toll, so no coin is inspected.
- reward
- 210 XP
- signature
exactToll
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- skips an overshooting coin mid-pouch
- every coin is refused
- free crossing inspects nothing
- empty pouch cannot pay
- pays with the very last coin
- stops early and ignores the rest
- lands just short after refusals
- single coin matches exactly