A surveyor is dropped onto a foggy island laid out as an n × n grid of cells. The island is
covered with hills: each has a sharp summit and long, gentle slopes, and between the hills there
may be flat stretches at sea level. The surveyor wants the highest point. In the fog the only
instrument is an altimeter: altitude(r, c) returns the height of cell (r, c) (a whole number,
0 at sea level), and every reading costs one unit of a limited budget, even if you read the same
cell twice. One reading too many raises BudgetExceeded.
Write find_summit(altitude, n, budget) that returns the highest cell you found, as a tuple
(row, col) with 0 <= row, col < n.
The tests run explore(find_summit, n, budget, seed), which hides an island, lets your function
search it and reports the height of the cell you return. Try it with Run, for example
print(explore(find_summit, 40, 200, 3)).
How this problem is scored
A cell passes if it is at least as high as the summit you reach by starting in the centre cell
(n // 2, n // 2) and always stepping to the highest of the four neighbouring cells until none is
higher. Its quality (0 to 100) says how much of the gap between that summit and the highest
point of the island you close: 0 matches the climb from the centre, 100 finds the highest point.
Examples
Input: explore(find_summit, 40, 200, 3)
Output: {"cell": [...], "height": ..., "readings": ...}
the climb from the centre stops at height 147; the highest point is 420
Constraints
40 <= n <= 900,200 <= budget <= 4000- Neighbours are the four cells above, below, left and right (inside the grid).
- Use
randomfor any random choices and never the clock: the tests seed it, so your result is the same on every run.
Goals
- See why a single hill climb stops on the first summit it reaches
- Restart a local search from fresh random points
- Spend a fixed reading budget wisely