Determine Reachability for a Chinese-Chess Horse with Blocked Legs
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Determine Reachability for a Chinese-Chess Horse with Blocked Legs
Implement a function that determines whether a Chinese-chess horse can reach a target square from a starting square on a standard 10-row by 9-column board. Some squares contain obstacles. An obstacle cannot be occupied, and it can also block the horse's “leg.” The horse may make any number of legal moves.
## Function Signature
```python
def can_reach(start: list[int], target: list[int], blocked: list[list[int]]) -> bool:
```
## Inputs
- `start` is `[row, column]` for the initial square.
- `target` is `[row, column]` for the destination square.
- `blocked` contains distinct obstacle coordinates.
- Rows are numbered `0` through `9`; columns are numbered `0` through `8`.
- `start` and `target` are valid board coordinates and are not blocked.
## Movement Rules
A horse move changes position by two squares along one axis and one square along the other axis. For a move with a two-row change, the orthogonally adjacent square one row toward the destination is the leg square. For a move with a two-column change, the orthogonally adjacent square one column toward the destination is the leg square. The move is legal only when the destination is on the board, the destination is not blocked, and the leg square is not blocked.
## Output
Return `True` if the target is reachable by zero or more legal moves; otherwise return `False`.
## Constraints
- `0 <= len(blocked) <= 88`
- All coordinates in `blocked` are unique and valid.
- The input collections must not be mutated.
## Examples
```text
start = [0, 0]
target = [2, 1]
blocked = []
output = True
```
```text
start = [0, 0]
target = [2, 1]
blocked = [[1, 0], [0, 1]]
output = False
```
In the second example, both possible first-move directions from the corner have blocked leg squares.
Quick Answer: Determine whether a Chinese-chess horse can reach a target on a 10-by-9 board when obstacles block both destinations and the horse's leg squares. The exercise tests finite-state graph traversal, precise move generation, board boundaries, visited-state handling, and zero-move reachability.
A Chinese-chess board has 10 rows and 9 columns. Rows are numbered `0` through `9` and columns are numbered `0` through `8`, so every square is a `[row, column]` pair.
A horse stands on `start` and wants to arrive at `target`. Some squares hold obstacles, listed in `blocked`. An obstacle cannot be occupied, and it can also block the horse's "leg". The horse may make any number of legal moves.
## Function
```
can_reach(start, target, blocked)
```
## Input
- `start` is `[row, column]` for the initial square.
- `target` is `[row, column]` for the destination square.
- `blocked` contains distinct obstacle coordinates, each written `[row, column]`.
- `start` and `target` are valid board coordinates and are not blocked.
## Movement Rules
A horse move changes position by two squares along one axis and one square along the other axis, so from `[r, c]` the eight candidate destinations are `[r-2, c-1]`, `[r-2, c+1]`, `[r+2, c-1]`, `[r+2, c+1]`, `[r-1, c-2]`, `[r-1, c+2]`, `[r+1, c-2]`, and `[r+1, c+2]`.
Every move has exactly one leg square, and which square it is depends on the axis carrying the two-square change:
- For a move with a two-row change, the leg is the orthogonally adjacent square one row toward the destination, in the same column: `[r+1, c]` when the row increases, `[r-1, c]` when it decreases.
- For a move with a two-column change, the leg is the orthogonally adjacent square one column toward the destination, in the same row: `[r, c+1]` when the column increases, `[r, c-1]` when it decreases.
The leg is therefore always orthogonally adjacent to the square the horse is standing on. It is never a diagonal neighbour, and it is never picked out by the one-square half of the move.
A move is legal only when all three of these hold:
1. the destination is on the board,
2. the destination is not blocked, and
3. the leg square is not blocked.
## Output
Return `True` if `target` can be reached from `start` by zero or more legal moves, and `False` otherwise.
The answer is a single boolean, so there is nothing to order or tie-break. Zero moves count: when `start` and `target` are the same square the answer is `True`, even if every move out of that square happens to be illegal.
Do not mutate `start`, `target`, or `blocked`.
## Constraints
- `0 <= len(blocked) <= 88`
- All coordinates in `blocked` are unique and valid.
- `0 <= row <= 9` and `0 <= column <= 8` for every coordinate in `start`, `target`, and `blocked`.
- `start` and `target` are valid board coordinates and are not blocked.
- The input collections must not be mutated.
- Every value in the input is a board index no larger than `9`, and the answer is a boolean, so no quantity anywhere in this problem approaches a 32-bit limit. `int` is the correct width in Java and C++.
## Examples
**Example 1**
```
start = [0, 0]
target = [2, 1]
blocked = []
output = True
```
The move from `[0, 0]` to `[2, 1]` changes the row by two, so its leg is `[1, 0]`. The destination is on the board, the destination is empty, and the leg is empty, so one legal move reaches the target.
**Example 2**
```
start = [0, 0]
target = [2, 1]
blocked = [[1, 0], [0, 1]]
output = False
```
The corner `[0, 0]` has only two on-board moves: `[2, 1]`, whose leg is `[1, 0]`, and `[1, 2]`, whose leg is `[0, 1]`. Both legs are blocked, so no move out of `[0, 0]` is legal. The square `[2, 1]` is empty and one jump away, but it can never be occupied.
Constraints
- 0 <= len(blocked) <= 88
- All coordinates in `blocked` are unique and valid.
- 0 <= row <= 9 and 0 <= column <= 8 for every coordinate in `start`, `target`, and `blocked`.
- `start` and `target` are valid board coordinates and are not blocked.
- The board is fixed at 10 rows by 9 columns, so it holds 90 squares in total.
- The input collections must not be mutated.
- Every input value is a board index of at most 9 and the return value is a boolean, so nothing in this problem approaches a 32-bit integer limit or a JavaScript precision limit; `int` is the correct width in Java and C++.
Examples
Input: ([0, 0], [2, 1], [])
Expected Output: True
Explanation: Source example 1. From `[0, 0]` the move to `[2, 1]` changes the row by two, so its leg is `[1, 0]`. Nothing is blocked, so the single move is legal and the target is reached.
Input: ([0, 0], [2, 1], [[1, 0], [0, 1]])
Expected Output: False
Explanation: Source example 2. The corner `[0, 0]` has only two on-board moves. `[2, 1]` has leg `[1, 0]` and `[1, 2]` has leg `[0, 1]`; both legs are blocked, so the horse can never leave `[0, 0]` and the target is unreachable even though `[2, 1]` itself is empty.
Hints
- "Zero or more moves" makes this a closure question rather than a shortest-path question. The board holds only 90 squares, so working out the full set of squares the horse can ever stand on -- and then asking whether the target is in it -- is enough; the number of moves never matters.
- The leg square is determined by the move, not by the destination. Read off which axis carries the two-square change, then step one square along that axis from where the horse is standing and leave the other coordinate alone. Storing the leg offset next to each of the eight move offsets keeps the two cases from being mixed up.
- Three separate conditions have to hold before a move counts, and it is easy to check only two of them: an obstacle on the destination and an obstacle on the leg block a move for different reasons. Also settle the degenerate case first -- what should the answer be when the horse does not have to move at all?