3
\$\begingroup\$

The challenge is this: You have a function that is passed a board length (8x8 chess board), with the coordinates of the queen's location, along with an array of obstructions (opponents). Given the location of the queen, how many moves spaces are available for her to move, total?

This is the solution I came up with, based on the matrix spiral one I did recently, and I absolutely cringe when I look at it because the code looks so reusable but every time I look at lines to reuse, there's always something preventing it.

I like this approach because it's straightforward, but it is super wet and I'm wondering if anyone has any tips for taking the same strategy and making it cleaner.

const queensMenace = (boardLength, queen, obstructions) => {
  let counter = 0;
  const x = queen[0];
  const y = queen[1];

  function isObstacle(row, col) {
    for (let o of obstructions) {
      if (o[0] === row && o[1] === col) {
        console.log(o[0] + ',' + o[1]);
        return true;
      }
    }
  }

  function checkUp(row, col) {
    if (row >= 0) {
      console.log(row);
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkUp(row-1,col);
      }
    }
  }

  function checkDown(row, col) {
    if (row < boardLength-1) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkDown(row+1,col);
      }
    }
  }

  function checkLeft(row, col) {
    if (col >= 0) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkLeft(row,col-1);
      }
    }
  }

  function checkRight(row, col) {
    if (col < boardLength-1) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkRight(row,col+1);
      }
    }
  }

  function checkUpLeft(row, col) {
    if (row >= 0 && col >= 0) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkUpLeft(row-1,col-1);
      }
    }
  }

  function checkUpRight(row, col) {
    if (row >= 0 && col < boardLength-1) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkUpRight(row-1,col+1);
      }
    }
  }

  function checkDownRight(row, col) {
    if (row < boardLength-1 && col < boardLength-1) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkDownRight(row+1,col+1);
      }
    }
  }

  function checkDownLeft(row, col) {
    if (row < boardLength-1 && col >= 0) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkDownRight(row+1,col-1);
      }
    }
  }

  checkUp(x-1,y);
  checkUp(x+1,y);
  checkLeft(x,y-1);
  checkRight(x,y+1);
  checkUpLeft(x-1,y-1);
  checkUpRight(x-1,y+1);
  checkDownRight(x+1,y+1);
  checkDownLeft(x+1,y-1);


  return counter;
};

queensMenace(8, [4,5], [[2,3], [7,4]]);
\$\endgroup\$
  • \$\begingroup\$ checkDownLeft recurses to checkDownRight, which is not consistent with your other functions. \$\endgroup\$ – AJD Jan 30 '18 at 5:24
1
\$\begingroup\$

What about defining checkDelta?

function checkDelta(dx, dy) {
    if (0 <= x + dx && x + dx < boardSize) {
        if (0 <= y + dy && y + dy < boardSize) {
            // And so on.

This function should make your code really simple.

\$\endgroup\$
  • \$\begingroup\$ in your example, x & y are constants, so deriving dx and dy would be problematic. However, I have used this concept in my answer below. \$\endgroup\$ – AJD Jan 30 '18 at 5:45
  • \$\begingroup\$ Oh, now I see. In the recursive calls, x and y need to be different. Luckily the main idea was to use the deltas of the coordinates, and that still works. \$\endgroup\$ – Roland Illig Jan 30 '18 at 7:38
0
\$\begingroup\$

The functions can be cleaned up slightly:

function checkDownRight(row, col) {
    if (row < boardLength-1 && col < boardLength-1) {
      if (isObstacle(row,col)) {
        return;
      } else {
        counter++;
        checkDownRight(row+1,col+1);
      }
    }
  }

Becomes

function checkDownRight(row, col) {
    if checkDelta(row-1, col-1) {
      if (not isObstacle(row,col)) {
        counter++;
        checkDownRight(row+1,col+1);
      }
    }
  }

I am not a javascript coder, so may have dropped some semantic in the above. A key point is that the functions do not return any particular value - I would use a Sub in VB. By not returning any value in the functions, you can skip the 'else' that does nothing but return.

Perhaps even (possible because of the removal of the else condition):

function checkDownRight(row, col) {
    if (checkDelta(row-1, col-1) and (not isObstacle(row,col)) {
        counter++;
        checkDownRight(row+1,col+1);
    }
  }

And finally, what about a generic function (noting that all checks travel in a straight line) - made possible through checkDelta and simplified if.

function checkLine(row, col, dx, dy) {
    if (checkDelta(row+dx,col+dy) and (not isObstacle(row,col)) {
        counter++;
        checkLine(row+dx,col+dy, dx, dy);
    }
  }

and your main body becomes:

  checkLine(x-1,y, -1, 0);
  checkLine(x+1,y, 1, 0);
  checkLine(x,y-1, 0, -1);
  checkLine(x,y+1, 0, 1);
  checkLine(x-1,y-1, -1, -1);
  checkLine(x-1,y+1, -1, +1);
  checkLine(x+1,y+1, 1, 1);
  checkLine(x+1,y-1, 1,-1);

But hold on, another thought for the main body.

Array = {(-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,1), (1,-1)}
For each element e(dx,dy)
    checkLine(x+dx,y+dy,dx,dy)

The use of arrays simplifies the re-use for other pieces (i.e. rooks and bishops).

(please excuse any error in adding or omitting dx, dy operations - you should get the gist).

\$\endgroup\$
0
\$\begingroup\$

An alternative solution.

Looking at the problem and seeing that the board can be any size. the search by iterating square will grow logarithmic with the size of the board and number of obstructions.

An alternative solution is tied to the number of obstructions by setting up a small grid of 8 directions ('dist' in example) containing the distance from the queen to the edge. The size of the board would not effect the complexity apart from being able to hold more pieces.

As you iterate the obstructions you check if they lay on one of the paths from the queen to the edge, if so you shorten the path, keeping track of the minimum path length.

Once all the obstructions have been tested just sum the values in dist array.

As the obstructions will always need to be iterated this method is near optimum for the type of input.

If the input was an array of squares containing obstruction then the original search would be the best on average as there would be no need to iterate all the other pieces.

// complexity governed by size of positions array, not size of board.
function checkMoves(size, queen, positions){
   const M = Math.min;   // For readability 
   const A = Math.abs;   // M for Math.min and A for Math.abs
   const qx = queen[0];  // get coord of queen
   const qy = queen[1];
   const n = size - 1;   // get number queen max steps

   // A grid of 9 for the possible moves from queen position to board edge
   const dist = [
        M(qx, qy),      qy,       M(n - qx, qy),
        qx,             0,        n - qx,
        M(qx, n - qy),  n - qy,   M(n - qx, n - qy)
   ];

   // For each obstructions position check if it gets in the way of the queen
   for(const pos of positions){
       const dx = pos[0] - qx;  // difference in coords
       const dy = pos[1] - qy;

       // use the dif to find the offset from center of dist array
       const off = Math.sign(dx) + Math.sign(dy) * 3;

       // if on queen's column row or diagonal store the min obstruction  distance
       if (dx === 0) { // is on queen column
           dist [4 + off] = M(dist [4 + off], A(dy) - 1);
       } else if (dy === 0 || A(dx) === A(dy)) { // is on queen row or on queen diagonal
           dist [4 + off] = M(dist [4 + off], A(dx) - 1);
       }
   }
   var i = 0;  // now just sum the distances
   return dist[i++] + dist[i++] + dist[i++] + 
          dist[i++] + dist[i++] + dist[i++] + 
          dist[i++] + dist[i++] + dist[i++];
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.