‹ back to the board

Monday, September 14

Apprenticelogic & control flow

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).

  • coins is a list of positive integers, in the order they are inspected. It may be empty.
  • toll is 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.

  • loops with early exit
  • Apprentice

examples

  1. case 1coins 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.
  2. case 2coins of [5, 5], toll of 3-1 — both coins would overshoot, the pile stays at 0, and the pouch runs out.
  3. case 3coins of [2], toll of 00 — the empty pile already matches the toll, so no coin is inspected.
reward
210 XP
signature
exactToll
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • 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
Exact Change at the Mossback Bridge · bitwick