A Straight Line Through the Cells · Python problem 568853

A warehouse robot would rather drive straight from cell a to cell b than follow a staircase of grid cells, but only if nothing is in the way. Its map is a list of strings grid, where grid[row][col] is '#' for a blocked cell and '.' for free floor; a cell is a pair (row, col).

The cells on the line from a = (r0, c0) to b = (r1, c1) are defined like this. Let dr = r1 - r0, dc = c1 - c0 and n = max(|dr|, |dc|). For k = 0, 1, ..., n the k-th cell is

\left(r_0 + \left\lfloor \frac{k \cdot dr}{n} + \frac12 \right\rfloor,\; c_0 + \left\lfloor \frac{k \cdot dc}{n} + \frac12 \right\rfloor\right)

so halves always round up (towards the larger index): \lfloor 0.5 + \frac12 \rfloor = 1 and \lfloor -0.5 + \frac12 \rfloor = 0. The line therefore has n + 1 cells, starting with a (k = 0) and ending with b (k = n). When a == b it is just that one cell.

Write first_blocked(grid, a, b) that walks the line from a towards b and returns the first cell on it that is blocked, as a tuple (row, col), or None if every cell on the line is free (so the robot can drive straight).

Examples

Input:  grid = ["....",
                ".#..",
                "...."], a = (0, 0), b = (2, 3)
Output: (1, 1)
Explanation: n = 3. For k = 1 the row is floor(2/3 + 1/2) = 1 and the column is 1.

Input:  grid = [".#.",
                "..."], a = (0, 0), b = (1, 2)
Output: None
Explanation: n = 2. For k = 1 the row is floor(0.5 + 0.5) = 1, so the line is
(0, 0), (1, 1), (1, 2) and misses the blocked cell (0, 1).

Input:  grid = ["....",
                ".#..",
                "...."], a = (2, 0), b = (2, 3)
Output: None

Constraints

all rows have the same length; a and b are inside the grid

Goals

List the cells a straight line passes through, by a precise rule
Round halves the stated way, not Python's way
Stop at the first blocked cell