Counting Attacking Bishop Pairs on a Chessboard with TypeScript

Efficiently Determine Attacking Bishop Pairs Using Diagonal Properties

In this article, we will solve a classic chess problem involving bishops and their attacking patterns on a special M by M chessboard. We’ll write an efficient TypeScript function to count the number of pairs of bishops that can attack each other.

Problem

On our special chessboard, two bishops attack each other if they share the same diagonal. This includes bishops that have another bishop located between them, i.e. bishops can attack through pieces.

You are given N bishops, represented as (row, column) tuples on a M by M chessboard. Write a function to count the number of pairs of bishops that attack each other. The ordering of the pair doesn’t matter: (1, 2) is considered the same as (2, 1).

For example, given M = 5 and the list of bishops:

• (0, 0)
• (1, 2)
• (2, 2)
• (4, 0)

The board would look like this:

[b 0 0 0 0]
[0 0 b 0 0]
[0 0 b 0 0]
[0 0 0 0 0]
[b 0 0 0 0]

You should return 2, since bishops 1 and 3 attack each other, as well as bishops 3 and 4.

Problem Description

Given N bishops represented as (row, column) tuples on an M by M chessboard, two bishops attack each other if they share the same diagonal. This includes bishops that have another bishop located between them. We need to count the number of pairs of bishops that attack each other.

Understanding Bishop Movement

Bishops move diagonally, and there are two types of diagonals:

• Primary Diagonal: From top-left to bottom-right, represented by cells where the difference between the row and column indices is constant (i - j).
• Secondary Diagonal: From top-right to bottom-left, represented by cells where the sum of the row and column indices is constant (i + j).

Approach

To efficiently count the attacking pairs:

1. Use dictionaries to keep track of the number of bishops on each diagonal.
2. For each diagonal, if there are n bishops, the number of attacking pairs is given by the combination formula n * (n - 1) / 2.

TypeScript Implementation

Here’s the implementation:

type Position = [number, number];

function countAttackingPairs(M: number, bishops: Position[]): number {
    const primaryDiagonals: Map<number, number> = new Map();
    const secondaryDiagonals: Map<number, number> = new Map();

    // Populate the maps with counts of bishops on each diagonal
    for (const [row, col] of bishops) {
        const primaryDiag = row - col;
        const secondaryDiag = row + col;

        primaryDiagonals.set(primaryDiag, (primaryDiagonals.get(primaryDiag) || 0) + 1);
        secondaryDiagonals.set(secondaryDiag, (secondaryDiagonals.get(secondaryDiag) || 0) + 1);
    }

    let attackingPairs = 0;

    // Calculate pairs for primary diagonals
    for (const count of primaryDiagonals.values()) {
        if (count > 1) {
            attackingPairs += (count * (count - 1)) / 2;
        }
    }

    // Calculate pairs for secondary diagonals
    for (const count of secondaryDiagonals.values()) {
        if (count > 1) {
            attackingPairs += (count * (count - 1)) / 2;
        }
    }

    return attackingPairs;
}

// Example usage:
const M = 5;
const bishops: Position[] = [
    [0, 0],
    [1, 2],
    [2, 2],
    [4, 0]
];

console.log(countAttackingPairs(M, bishops)); // Output: 2

Explanation

Data Collection:

• We iterate over each bishop and update two maps: primaryDiagonals and secondaryDiagonals. The keys are the diagonal identifiers, and the values are the counts of bishops on those diagonals.

Counting Attack Pairs:

• For each entry in both maps, if the count of bishops on a diagonal is greater than 1, we calculate the number of attacking pairs using the combination formula n * (n - 1) / 2 and sum these values.

Alternative Solutions

Brute Force:

• Iterate through all pairs of bishops and check if they share the same diagonal. This approach has a time complexity of O(N²), where N is the number of bishops, and is less efficient for larger inputs.

Optimized Approach:

• The provided diagonal counting method has a time complexity of O(N), making it suitable for larger inputs.

Conclusion

The solution provided is efficient and leverages the properties of diagonals to count the attacking pairs of bishops effectively. This approach ensures we handle larger inputs gracefully and with optimal performance.

---

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go:

• Follow us: LinkedIn | YouTube| Newsletter
• Listen to our podcast on: Spotify| Amazon Music | Apple Podcasts
• More content at Burhanuddin’s Code Compendium

---