A grid planner gives a lawn robot a route as a list of cells, and on a grid that route is full of little zigzags. The robot would rather drive straight lines between a few waypoints. Thin the route out.
The map is a list of strings grid: grid[row][col] is '#' for a flower bed and '.' for lawn. A cell is a pair (row, col). The route path starts at path[0], ends at path[-1], uses only lawn cells, and each cell touches the next by a side or a corner.
Line of sight. The cells on the straight line from a = (r0, c0) to b = (r1, c1) are: with dr = r1 - r0, dc = c1 - c0 and n = max(|dr|, |dc|), for k = 0, 1, ..., n the cell
(halves round up, towards the larger index; for a == b the line is the single cell a). The line is clear when none of its cells is '#'.
The rule. Keep path[0]. Then, from the last kept cell path[i], keep path[j] for the largest index j > i such that the line from path[i] to path[j] is clear (j = i + 1 always qualifies, as neighbouring lawn cells see each other). Repeat until the last cell of the route has been kept.
Write shortcut(grid, path) that returns the list of kept cells, as (row, col) tuples in route order.
Examples
Input: grid = [".....",
".##..",
".##..",
"....."]
path = [(3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3), (1, 4)]
Output: [(3, 0), (0, 0), (0, 3), (1, 4)]
Explanation: from (3, 0) every later cell's line clips the bed, except (0, 0).
From (0, 0) the line to (1, 4) passes (1, 2); the line to (0, 3) is clear.
Input: grid = ["...",
".#.",
"..."]
path = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0)]
Output: [(0, 0), (2, 0)]
Explanation: the line to (1, 2) is blocked, but the end of the route is in plain
sight straight down the left edge, and it is the farthest.
The setup provides warehouse(rows, cols, seed, shelves=8), a random map of rectangular beds with the top-left and bottom-right cells free, and grid_route(grid, start, goal), a zigzag route between two cells; the larger tests use them. Try shortcut(warehouse(20, 30, 1, 40), grid_route(warehouse(20, 30, 1, 40), (0, 0), (19, 29))) with Run.
Constraints
- all rows have the same length;
1 <= len(path) <= 400
Goals
- Replace a cell-by-cell route with a few waypoints joined by straight, clear lines
- Search for the farthest visible waypoint, not the first blocked one
- Reuse a precise line-of-sight test inside a larger loop