const { runTests } = require("./tests.js");
function validChessMoves(board, piece, r, c) {
function isMoveValid(board, r, c) {
const rows = board.length;
const cols = board[0].length;
return (
(r >= 0 && r < rows) &&
(c >= 0 && c < cols) &&
board[r][c] != 1
);
}
const knightDirections = [[-2,1],[-2,-1],[2,1],[2,-1],[-1,2],[1,2],[-1,-2],[1,-2]];
const kingDirections = [[0, 1], [0,-1],[-1,0],[1,0],[-1,1], [-1,-1],[1,1], [1,-1]];
const queenDirections = kingDirections;
const moves = [];
if (piece === "knight") {
for (const [rDir, cDir] of knightDirections) {
const [newR, newC] = [r + rDir, c + cDir];
if (isMoveValid(board, newR, newC)) {
moves.push([newR, newC]);
}
}
}
else if (piece === "king") {
for (const [rDir, cDir] of kingDirections) {
const newR = r + rDir;
const newC = c + cDir;
if (isMoveValid(board, newR, newC)) {
moves.push([newR, newC]);
}
}
}
else {
for (const [rDir, cDir] of queenDirections) {
let newR = r + rDir;
let newC = c + cDir;
while (isMoveValid(board, newR, newC)) {
moves.push([newR, newC]);
newR += rDir;
newC += cDir;
}
}
}
return moves;
}
runTests(validChessMoves);
Link: https://start.interviewing.io/beyond-ctci/part-vii-catalog/grids-and-matrices#chess-moves
# Chess Moves
For context, this is how the King, Knight, and Queen move on a chessboard:
https://iio-beyond-ctci-images.s3.us-east-1.amazonaws.com/chess-moves-1.png
The king can go to any adjacent cell, including diagonals. The knight 'jumps' one cell in one dimension and two in the other, even if there are pieces in between. The queen can move *any number of cells* in any direction, including diagonals, but cannot go through occupied cells.
We are given three inputs:
- `board`, an `nxn` binary grid, where a `0` denotes an empty cell, `1` denotes an occupied cell (for this problem, it doesn't matter what piece is in it)
- `piece`, which is one of `"king"`, `"knight"`, or `"queen"`
- `r` and `c`, with `0 ≤ r < n` and `0 ≤ c < n`, which denote an unoccupied position in the board
Return a list of all the **unoccupied** cells in `board` that can be reached by the given `piece` in one move starting from `[r, c]`. The order of the output cells does not matter.
```
Example 1:
board = [[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]]
piece = "king"
r = 3
c = 5
Output: [[2, 5], [3, 4], [4, 4], [4, 5]]
Example 2:
board = [[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]]
piece = "knight"
r = 4
c = 3
Output: [[2, 2], [3, 5], [5, 5]]
Example 3:
board = [[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]]
piece = "queen"
r = 4
c = 4
Output: [[3, 4], [3, 5], [4, 0], [4, 1], [4, 2], [4, 3], [4, 5], [5, 3], [5, 4], [5, 5]]
```
https://iio-beyond-ctci-images.s3.us-east-1.amazonaws.com/chess-moves-2.png
Constraints:
- `1 ≤ n ≤ 100`
- `board[i][j]` is either `0` or `1`
- `0 ≤ r, c < n`
- `piece` is one of `"king"`, `"knight"`, or `"queen"`
function runTests(func) {
const tests = [
// Example 1 from the book - king moves
[[[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]], "king", 3, 5,
[[2, 5], [3, 4], [4, 4], [4, 5]]],
// Example 2 from the book - knight moves
[[[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]], "knight", 4, 3,
[[2, 2], [3, 5], [5, 5]]],
// Example 3 from the book - queen moves
[[[0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0]], "queen", 4, 4,
[[3, 4], [3, 5], [4, 0], [4, 1], [4, 2], [4, 3], [4, 5],
[5, 3], [5, 4], [5, 5]]],
// Edge case - 1x1 board
[[[0]], "queen", 0, 0, []],
// Edge case - all occupied except current position
[[[1, 1], [1, 0]], "knight", 1, 1, []],
];
console.log("Testing...");
for (const [board, piece, r, c, want] of tests) {
const got = func(board, piece, r, c);
// Sort both lists for consistent comparison
got.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
want.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
console.assert(JSON.stringify(got) === JSON.stringify(want),
`\nchessMoves(${JSON.stringify(board)}, ${piece}, ${r}, ${c}): ` +
`got: ${JSON.stringify(got)}, want: ${JSON.stringify(want)}\n`);
}
console.log("Testing done!");
}
module.exports = {
runTests,
};
