The Sun-Wells of the Kessarine Waste
The Waterwardens of the Kessarine Waste are charting the great desert before the caravan season. Their survey splits the Waste into a rectangular grid of rows by cols squares. Rows are numbered 0 to rows - 1 and columns 0 to cols - 1. Some squares are sheer dune-cliffs that no traveller can enter. Some hold a sun-well. Every other square is open sand.
The Wardens will pay for one number: how far a stranded traveller could possibly be from water. A traveller moves one step at a time to a square that shares an edge with the current one (up, down, left or right, never diagonally). They may never step outside the grid or onto a cliff square. A well square is open and may be walked through.
Write farthestFromWater(rows, cols, walls, wells):
rowsandcolsare integers, each from1to100.wallsis a list of[row, col]pairs, the cliff squares. It may be empty.wellsis a list of[row, col]pairs, the well squares. It contains at least one entry.- Every pair lies inside the grid. No square appears twice, either within one list or across both, so a well is never a cliff.
An open square is any square that is not a cliff. Well squares count as open squares. For each open square, find the fewest steps needed to reach any well. A well square itself needs 0 steps.
Return an integer:
- If some open square cannot reach any well at all, return
-1. - Otherwise, return the largest of these step counts across all open squares.
Cliff squares are never counted.
examples
- case 1
rows 3, cols 3, walls at [1,0] and [1,1], one well at [0,0]6 — the square [2,0] must go around the cliffs: right along row 0, down column 2, then left along row 2 - case 2
rows 1, cols 7, no walls, wells at [0,0] and [0,6]3 — the middle square [0,3] is three steps from either well - case 3
rows 3, cols 3, walls at [1,2] and [2,1], one well at [0,0]-1 — the open square [2,2] is sealed off by cliffs and can never reach water - case 4
rows 1, cols 3, walls at [0,1] and [0,2], one well at [0,0]0 — the only open square is the well itself; cliff squares are not counted
- reward
- 320 XP
- signature
farthestFromWater
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- single well square
- open grid well in centre
- path forced around cliffs
- well sealed in its corner
- sealed pocket of sand
- two wells meet in the middle
- cliffs not counted
- two wells with a cliff ridge
- large open waste one corner well
- large open waste opposite corner wells