The Tollgates of Tithe Moor
The carters of bitwick cross Tithe Moor, and the moor is nothing but gates. The gates stand in a rectangular grid, each one charging a toll in coins. A cart enters at the top-left gate, leaves at the bottom-right gate, and between gates may move only one step east (to the next column) or one step south (to the next row). The toll of every gate the cart stands on is paid, the first and the last included. The Warden of the Moor issues a number of wax seals; each seal cancels the toll of one gate on the cart's route, and seals may be left unused.
tollRoad(tolls, seals) takes:
tolls: the grid, given as a list of rows, each row a list of non-negative integers. Every row has the same length, and there is at least one row and one column. The toll of the gate in rowr, columncistolls[r][c].seals: a non-negative integer, the number of gates whose toll may be cancelled. It may exceed the number of gates on a route.
Return, as an integer, the smallest total toll payable on a route from the top-left gate to the bottom-right gate.
examples
- case 1
tolls of [[1,1,100],[1,100,1],[100,1,1]], seals of 0104 - every route passes through exactly one of the three 100-coin gates, plus four gates of 1 - case 2
tolls of [[1,1,100],[1,100,1],[100,1,1]], seals of 14 - spend the seal on the 100-coin gate, leaving four gates of 1 to pay - case 3
tolls of [[7]], seals of 10 - the single gate is both entrance and exit, and the seal cancels its toll
- reward
- 350 XP
- signature
tollRoad
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- one gate, no seal
- one gate, seals to spare
- cursed diagonal, no seals
- cursed diagonal, one seal
- staircase moor, two seals
- wide moor, no seals
- wide moor, one seal
- the long crossing of Tithe Moor