Question 266332 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Matrix based chess/rook question on square to be maximum count

You are given a matrix A representing a chessboard with N rows and M columns. Each square of the chessboard contains an integer representing a
points-based score. You have to place two rooks on the chessboard in such a way that they cannot attack each other and the sum of points on
their squares is maximal. Rooks in chess can attack each other only if they are in the same row or column.

For example, given a matrix as in the following picture:

enter image description here

we can place rooks in two different ways:

  • One rook on A[00][00] = 1 and another rook on A[01][02] = 3. The sum of points on these squares is 4.
  • One rook on A[00][02] = 4 and another rook on A[01][00] = 2. The sum of points on these squares is 6.
    Your task is to find the maximum sum of two squares of the chessboards on which the rooks can be placed. In the example above, the answer is 6.
    We cannot, for example, place the rooks at A[00][02] and A[01][02] (whose sum is 7), as they would attack each other.

Write a function:
function solution(A);
which, given a matrix A, returns the maximum sum that can be achieved by placing two non-attacking rooks

Examples:

  1. Given matrix A with two rows and two columns:

enter image description here

the function should return 6. We can achieve the maximum sum by selecting A[00][02] + A[01][00] = 4 + 2. The selected squares are marked in green

  1. Given matrix A with three rows and three columns:

enter image description here

the function should return 23. We can achieve the maximum sum by selecting A[00][00] + A[01][02] = 15 + 8. The selected squares are marked in green.

  1. Given matrix A with three rows and two columns:

enter image description here

the function should return 24. We can achieve the maximum sum by selecting A[00][00] + A[01][02] = 12 + 12 or A[00][02] + A[01][00] = 12 + 12. The latter
the solution is marked in green.

  1. Given matrix A with two rows and three columns:

enter image description here

the function should return 22. We can achieve the maximum sum by selecting A[00][02] + A[01][00] = 14 + 8. The selected squares are marked in green.
Write an efficient algorithm for the following assumptions

N and M are integers within the range [2..600];
each element of matrix A is an integer within the range [0..1,000,000,000].

I tried but don’t think it’s valid.

function solution(A) {
    const N = A.length;
    const M = A[0].length;
    let maxSum = 0;

    if(N > M){
        for (let i = 0; i < N; i++) {
            for (let j = i + 1; j < N; j++) {
                for (let col1 = 0; col1 < M; col1++) {
                    for (let col2 = col1 + 1; col2 < M; col2++) {
                        if (col1 !== col2) {
                            const sum = A[i][col1] + A[j][col2];
                            maxSum = Math.max(maxSum, sum);
                        }
                    }
                }
            }
        }
        return maxSum;
    }

    for (let i = 0; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
            for (let col1 = 0; col1 < M; col1++) {
                for (let col2 = 0; col2 < M; col2++) {
                    if (col1 !== col2 && A[i][col1] !== A[j][col2]) {
                        maxSum = Math.max(maxSum, A[i][col1] + A[j][col2]);
                    }
                }
            }
        }
    }
    return maxSum;
}
Tags:

2

Answers


  1. 0

    You can solve this problem in linear time.

    Just iterate through the matrix row-by-row, and:

    • As you finish each row, keep track of the maximum value seen so far in each column in higher rows.
    • Traverse each row from left to right, using those column values to track the maximum value above and to the left, and add it to the current value. This will find the sums of all rook arrangements oriented like this .
    • Traverse each row from right to left to find the rook arrangements oriented like /.
    function solution(A) {
    // TODO make sure dimensions are >= 2x2
    let maxSum = A[0][0] + A[1][1];

    // track the maximum in each column
    const colMax = [...(A[0])];

    for (let r = 1;r < A.length; r++) {
        const row = A[r];
        // find  orientations
        let rectMax = colMax[0];
        for (let c = 1; c<row.length; ++c) {
            maxSum = Math.max(maxSum, row[c]+rectMax);
            rectMax = Math.max(rectMax, colMax[c]);
        }
        // find / orientations
        rectMax = colMax[row.length-1];
        for (let c=row.length-2; c>=0; --c) {
            maxSum = Math.max(maxSum, row[c]+rectMax);
            rectMax = Math.max(rectMax, colMax[c]);
        }
        // update colmax
        for (let c=0; c<row.length; ++c) {
            colMax[c] = Math.max(colMax[c], row[c]);
        }
    }
    return maxSum;
}
    Login or Signup to reply.
  2. 0

    We can build this fairly easily atop a function that creates a grid removing all the cells sharing a row or column with a given square. That function in turn can be written atop one that removes a given index from an array. It might looks like this:

    // Removes an index from an array; returns a copy, not mutating
const without = (i) => (xs) => [...xs.slice(0, i), ...xs.slice(i + 1)]

// Removes a row and column from a rectangular grid; returns a copy, not mutating
const removeSquare = (r, c) => (ss) => without(r)(ss).map(without(c))

// Finds the maximum sum of square values for two non-attacking rooks
const maxRookSum = (board) =>
  board.length <= 1 || board[0].length <= 1
    ? -Infinity
    : Math.max(
        maxRookSum(board.slice(1)),
        Math.max(...board[0].map((v, i) => v + Math.max(...removeSquare(0, i)(board).flat()))),
      )

console.log(maxRookSum([
  [1, 4,],
  [2, 3,],
])) //=> 2 + 4 => 6

console.log(maxRookSum([
  [15, 1, 5,],
  [16, 3, 8,],
  [2,  6, 4,],
])) //=> 15 + 8 => 23

console.log(maxRookSum([
  [12, 12,],
  [12, 12,],
  [ 0,  7,],
])) //=> 12 + 12 => 24

console.log(maxRookSum([
  [1, 2, 14,],
  [3, 8, 15,]
])) //=> 14 + 8 => 22
    .as-console-wrapper {max-height: 100% !important; top: 0}

    Our main function first ensures that we can even get two non-attacking rooks, meaning that we have at least two rows of at least two columns. If not, we return -Infinity as a signal. Otherwise we find the maximum of two values: First, we skip the initial row, and recur on the remaining rows. Second, we take the maximum of testing each value in the first row, removing the associated row and column, and finding the largest remaining square and adding it to our cell value. The maximum of these two values is the best we can do.

    Note that this technique could easily be extended to find the maximum sum of all non-attacking rooks in the grid, simply be recurring rather than flattening and taking the maximum in the that second main branch. (I know that, as that’s what I wrote first on misreading the problem; the version presented here is only slightly simpler.)

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search