‹ back to the board

Sunday, October 18

Adeptalgorithms & data structures

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

  • rows and cols are integers, each from 1 to 100.
  • walls is a list of [row, col] pairs, the cliff squares. It may be empty.
  • wells is 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.

  • graph traversal
  • Adept

examples

  1. case 1rows 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
  2. case 2rows 1, cols 7, no walls, wells at [0,0] and [0,6]3 — the middle square [0,3] is three steps from either well
  3. case 3rows 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
  4. case 4rows 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
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…
  • 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
The Sun-Wells of the Kessarine Waste · bitwick