Judge a route by its worst moment
Find the route whose hardest single step is as easy as possible, using the cheapest-first search with max instead of plus. About 15 minutes.
Plus becomes max
A hiker crosses a hilly map made of squares with heights. Walking from one square to the next, the effort for that step is the difference in height. The hiker's tiredness depends on the steepest step of the whole walk, not the total. You want the walk where the steepest step is as gentle as possible.
The cheapest-first search handles this with one tiny change. Instead of adding the step's effort to the cost so far, take the larger of the cost so far and the step's effort.
effort = max(d, abs(h2 - h1)) # the worst step so far
- effort
- 0
Start at the top-left. The effort so far is 0.
Why it is still correct
Dijkstra works as long as extending a route never makes it cheaper. Adding steps never reduces a sum, and taking a maximum never goes down either, so once a square is the cheapest open one, no other way into it can beat it.
Everything else is the same: a heap of open squares keyed by cost, skip stale entries, and stop when you pop the final square. This pattern, minimising the worst step, is called a minimax or bottleneck path.
if (r, c) == goal:
return dA walk so far has an effort of 4. The next step has a height difference of 2. What is the effort now?
- A4, because the steepest step is still 4
- B6, adding the step
- C2, the latest step
Show the answer
4, because the steepest step is still 4. The route cost is the maximum, and 2 doesn't beat 4.
Gentlest steepest step
heights is a grid of whole numbers giving the height of each square. You start at the top-left square and walk to the bottom-right square, moving up, down, left or right. The effort of a walk is the largest height difference between two squares that are next to each other on the walk. Return the smallest effort over all walks.
heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]] → 2
1 ≤ rows, columns ≤ 20 · 1 ≤ height ≤ 1,000,000