The Bramble-Maze of Ostley Barrow
The Wardens of Ostley Barrow offer a bounty to whoever can carry a relic from the barrow's mouth to its inner chamber. A maze of bramble has grown over the barrow. The bounty-taker carries a pouch of flame-seals, and each seal burns away one square of bramble as they step into it.
Write bramblePath(grid, k).
gridis a non-empty list of strings, all of the same length, mapping the maze row by row. Every character is one of:.an open square#a bramble squareSthe barrow's mouth, where you start. There is exactly one, and it is open.Ethe inner chamber, where you must arrive. There is exactly one, and it is open. It is never the same square asS.kis a non-negative integer: the number of flame-seals in the pouch.
A move steps one square up, down, left or right, and must stay inside the grid. Stepping onto a # square spends one seal. This applies every time you step onto it, even if you have stood there before. Stepping onto ., S or E costs nothing. You may never spend more than k seals in total.
Return the fewest moves needed to get from S to E while spending at most k seals. If that cannot be done, return -1.
examples
- case 1
grid of ["S#.#E", ".#.#.", "....."], k of 24 - burn straight along the top row - case 2
the same grid, k of 18 - a single seal saves nothing here, so you take the long way round the bottom - case 3
grid of ["S#.#E", "...##"], k of 16 - go round through the lower row to keep your seal, then burn the last bramble before the chamber - case 4
grid of ["S.#.E"], k of 0-1
- reward
- 320 XP
- signature
bramblePath
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- adjacent chamber
- single row blocked without seals
- single row one seal
- columns maze no seals
- columns maze one seal
- one seal saves nothing
- two seals straight through
- must save seal for later
- enclosed chamber no seals
- snake corridor no seals
- all bramble exactly enough
- all bramble one short