algoadvance

Problem Description

You are given an 8x8 chessboard board with the following pieces:

• ‘R’ (Rook)
• ‘p’ (Pawn)
• ‘B’ (Bishop)
• ’.’ (empty square)

You need to calculate the number of pawns the Rook can capture. The Rook moves horizontally or vertically until it hits another piece or the edge of the board. It can capture any pawn in these directions (not blocked by other pieces).

Clarifying Questions

1. Is there always exactly one Rook ‘R’ on the board?
   • Yes, you can assume there is exactly one Rook.
2. What should we return if the Rook cannot capture any pawns?
   • If the Rook cannot capture any pawns, return 0.

Strategy

1. Locate the Rook on the board.
2. Check all four possible directions (up, down, left, right) from the Rook’s position.
3. Count the number of pawns that the Rook can directly capture in these directions without being blocked by another piece.

Implementation

Let’s implement this step-by-step.

def numRookCaptures(board):
    # Helper function to find the position of the Rook 'R'
    def find_rook(board):
        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    return (i, j)
        return (-1, -1)  # Should not happen since we assume exactly one Rook is present.

    # Function to count captures in a specific direction
    def count_in_direction(board, start_i, start_j, delta_i, delta_j):
        i, j = start_i + delta_i, start_j + delta_j
        while 0 <= i < 8 and 0 <= j < 8:
            if board[i][j] == 'B':  # blocked by Bishop
                return 0
            if board[i][j] == 'p':  # found a Pawn
                return 1
            i += delta_i
            j += delta_j
        return 0

    rook_i, rook_j = find_rook(board)
    captures = 0

    # Check all four directions
    captures += count_in_direction(board, rook_i, rook_j, -1, 0)  # Up
    captures += count_in_direction(board, rook_i, rook_j, 1, 0)   # Down
    captures += count_in_direction(board, rook_i, rook_j, 0, -1)  # Left
    captures += count_in_direction(board, rook_i, rook_j, 0, 1)   # Right

    return captures

# Example usage:
board = [
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]

print(numRookCaptures(board))  # Output should be 3.

Time Complexity

The time complexity is O(1). This is because:

• Locating the Rook takes 8x8 = 64 operations.
• Checking each of the four directions involves at most 8 steps each. Hence, the overall complexity is constant and dominated by a few fixed-size steps: O(1).

This solution ensures we efficiently check each necessary direction and thus determine the number of pawns the Rook can capture within the constraints given.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?