Queen's Attack II

I stumbled on a coding challenge in Hackerrank called Queen's Attack II.

There is a chessboard with a queen and a number of obstacles, we need to find how many squares the queen can attack taking into account the obstacles. I immediately thought: Alright seems pretty straight forward, you can recursively go in all the directions starting from the queen's position and once you reach an obstacle or the end of the chessboard you can stop.

The implementation would look like this:

queenAttack.js

// n - size of the chessboard
// k - size of the obstacles array
// r_q - queen's row position (y)
// c_q - queen's col position (x)
// obstacles - obstacles array
function queensAttack(n, k, r_q, c_q, obstacles) {
  // Write your code here
  let count = 0;
  let obs = {};

  // transform the obstacles array to an object for faster access
  for(let i = 0; i < obstacles.length; i++) {
    const [x,y] = obstacles[i];
    if(obs[x]) {
      obs[x][y] = true;
    } else 
      obs[x] = { [y]: true };
  }

  const walk = (startPos, direction) => {
    // if we go outside of bound
    if(startPos.y < 1 || startPos.x < 1 || startPos.x > n-1 || startPos.y > n-1) {
      return;
    }
  
    // if we hit an obstacle
    if(obs[startPos.y] && obs[startPos.y][startPos.x]) {
      return;
    }

    // increment counter and move to the next cell
    count++;
    walk({ y: startPos.y + direction.y, x: startPos.x + direction.x }, direction);
  }

  const startPos = { x: c_q , y: r_q };

  const directions = [
    { x: 0, y: -1 }, // top
    { x: -1, y: -1 }, // topLeft
    { x: -1, y: 0 }, // left
    { x: -1, y: +1 }, // bottomLeft
    { x: 0, y: +1 }, // bottom
    { x: +1, y: +1 }, // bottomRight
    { x: +1, y: 0 }, // right
    { x: +1, y: -1, } // topRight
  ];

  directions.forEach((dir) => {
    walk({ x: startPos.x + dir.x, y: startPos.y + dir.y }, dir);
  });

  return count;
}

I run the Code and see the results 😲:

Alt text

It seems that when the chessboard is very large my recursive function would just exceed the maximum call stack available for the process. In order to fix this we can convert our recursive function in a loop and things should be fine... BUT.. I think we can do better, Let's analyze the problem:

Alt text

Assuming we have no obstacles on our board we have to visit every cell in the queen's trajectory which would be a cost of O(n). We can leverage the fact that we can only go in a straight line, and if you know the magnitude and the direction of that line you have a vector. We can calculate the magnitude between the queen's position and the bounds of the chessboard and we can find the direction by calculating the angle, A big plus is that we already know that we can go in 45degrees increments:

Alt text

Assuming no obstacles we can immediately calculate the distance from the queen position to the four bounds:

queenAttack.js

  // n = size of the board
  // c_q = column position of the queen
  // r_q = row position of the queen

  let rightBound = n - c_q;
  let topBound = n - r_q;
  let bottomBound = r_q - 1;
  let leftBound = c_q - 1;

  const bounds = {
    0: rightBound,
    90: topBound,
    180: leftBound,
    270: bottomBound,
    45: Math.min(rightBound, topBound),
    135: Math.min(topBound, leftBound),
    225: Math.min(leftBound, bottomBound),
    315: Math.min(rightBound, bottomBound),
  }

If there are no obstacles all we need to do now is to sum up the values at each angle. Now let's handle the obstacles:

queenAttack.js

  // angle => [row, col]
  const angles = {
    0: [],
    45: [],
    90: [],
    135: [],
    180: [],
    225: [],
    270: [],
    315: [],
  };

  // we iterate through all obstacles
  for (let i = 0; i < obstacles.length; i++) {
    let [obsY, obsX] = obstacles[i];

    // calculate the distance from the queen position to the obstacle
    const yOffset = obsY - r_q;
    const xOffset = obsX - c_q;

    // calculate the angle
    let angle = Math.atan2(yOffset, xOffset) * 180 / Math.PI;
    // make the angle positive if it's negative
    if(angle < 0) {
      angle = 360 + angle;
    }

    /*
    * if the angle is not a multiple of 45 it means the obstacle is not in the
    *  queen's trajectory and we can discard it
    */
    if(angle in angles) {
      const currAngle = angles[angle];

      // there might be multiple obstacles on the same trajectory
      // we just pick the one that is closer to the queen
      const isClosest = currAngle.length && currAngle[0] < Math.abs(yOffset);

      if(!isClosest) {
        // once we calculate the angle we can use the absolute values
        angles[angle] = [Math.abs(yOffset), Math.abs(xOffset)];
      }
    }
  }

Now we're almost done, we have to go through all the angle values and if we find an obstacle in that direction we use the obstacle for the length, otherwise we use the bounds

queensAttack.js

  let count = 0;

  Object.keys(angles).map((key) => {
    const angle = angles[key];

    if(angle.length) {
      if(key == 0 || key == 90 || key == 180 || key == 270) {
        count += Math.max(angle[0], angle[1]) - 1;
      } else {
        count += Math.min(angle[0], angle[1]) - 1;
      }
    } else {
      count += bounds[key];
    }
  });
  
  return count;

And that's it, now we resubmit the code and Voila 🍾🎉

Alt text

Now no matter the size of the chessboard our solution is almost constant time, we only depend on the size of the obstacles array (which can also be empty) instead of the size of the chessboard and it means that our algorithm has constant time complexity which makes it... blazing fast!