Crossword orphan cells
EasyOnline Assessment
Find the white squares of a crossword grid that are too short to belong to any answer.
The grid is drawn with . for a white square (where a letter goes) and # for a black square. An across run is a maximal stretch of consecutive white squares in one row, bounded by a black square or the edge of the grid. A down run is the same thing in one column. Every answer in the puzzle fills a whole run, and a puzzle rule says an answer needs at least 3 letters, so runs of length 1 or 2 are not answers.
A white square is an orphan if it belongs to no run of length 3 or more, neither across nor down. A white square in a long across run is fine even when its down run is short, and the other way round.
Input: grid, a list of equal-length strings, one per row, top row first, using only . and #.
Output: the orphan squares as [row, column] pairs (zero-based), in row-major order (top row first, left to right). Return an empty list if there are none.
Example 1
- Input:
- [["...","...","..."]]
- Output:
- []
- Explanation
- Every row of this fully white 3 by 3 grid is an across run of length 3, and so is every column, so nothing is an orphan: the answer is
[].
Example 2
- Input:
- [["...#.","#.#..","..#.."]]
- Output:
- [[1,3],[2,0],[2,3]]
- Explanation
- Row 0 has an across run of 3 (squares
[0, 0]to[0, 2]). Columns 1 and 4 are white in all three rows, so their squares sit in down runs of 3. The squares[1, 3]and[2, 3]form a down run of 2 and each also lies in an across run of 2, so both are orphans. The square[2, 0]has an across run of 2 and a down run of 1 (black square above it), so it is an orphan too. A square short in one direction but long in the other, like[1, 4], is fine. The answer is[[1, 3], [2, 0], [2, 3]].
Example 3
- Input:
- [["###","#.#","###"]]
- Output:
- [[1,1]]
- Explanation
- Only one white square exists, and its across and down runs both have length 1, so it is an orphan:
[[1, 1]].
Constraints
1 <= len(grid) <= 151 <= len(grid[0]) <= 15- every row has the same length and contains only
.and#