Do not recall if I received a message or decided to explore the Queen’s Attack II challenge from Hacker Rank. By the title there must have been a previous version. I decided not to look at it and just go for this one.
The challenge is well defined and there are no indications on which approach to use. I implemented it twice. On the first pass I went with what I considered a brute force approach with some refinements. Based on a sentence in the description of the challenge “A single cell may contain more than one obstacle; …” I figured that my first approach would fall short as far as timing out and it did. Something that I noted was that timeouts seem to be reported as errors when it should properly be labeled as a time out.
Following is a screen capture of the console in of the Eclipse IDE running the two sample inputs:
5 3 4 3 5 5 4 2 2 3 update <<< r,c: (5,5) update <<< r,c: (4,2) update <<< r,c: (2,3) 10
Please disregard all lines containing the name of a method followed by “<<<”. Such artifacts were added while the design, implementation and testing of the two approaches.
Following is the modified test code written in Java 8:
/**
* Test code.
*/
public static void main(String[] args) {
// **** ****
Approach approach = Approach.ClosestPoints;
// **** open scanner ****
Scanner in = new Scanner(System.in);
// **** ****
int n = in.nextInt();
int k = in.nextInt();
// **** we know the position for the queen before we get the obstacles ****
int rQueen = in.nextInt();
int cQueen = in.nextInt();
// **** ****
switch (approach) {
case ClosestPoints:
// **** ****
Obstacles obstacles = new Obstacles(n, rQueen, cQueen);
// **** read and place obstacles ****
for(int a0 = 0; a0 < k; a0++) {
int r = in.nextInt();
int c = in.nextInt();
// **** update distance based on obstacle ****
obstacles.update(c, r);
}
// **** compute and display position count ****
obstacles.compute();
break;
case WithBoard:
// **** allocate chessboard ****
boolean[][] chessboard = new boolean[n][n];
// **** read and place obstacles ****
for(int a0 = 0; a0 < k; a0++) {
int r = in.nextInt();
int c = in.nextInt();
// **** place obstacle on chessboard ****
placeObstacle(n, chessboard, r, c);
}
// **** display chessboard ****
display(chessboard, n);
// **** compute and display position count ****
posCount(n, k, rQueen, cQueen, chessboard);
break;
}
// **** close scanner ****
in.close();
}
The first two lines of data are read. At that point the test code implements one of two approaches. The WithBoard approach uses an n x n matrix of Boolean. The idea is to track the obstacles in the two dimensional array. If the same coordinates are used multiple times, so be it.
After reading and updating the matrix of obstacles we look for the closest obstacle in each of the eight directions (i.e., N, NE, E …). The main overhead is in updating the obstacles matrix. By the way, the sample input worked on this approach.
As I was developing the solution I generated the following test case:
5 5 3 3 5 5 5 1 1 3 1 5 1 1 update <<< r,c: (5,5) update <<< r,c: (5,1) update <<< r,c: (1,3) update <<< r,c: (1,5) update <<< r,c: (1,1) 11
I just moved one of the obstacles and inserted new ones at the corners. That provided enough information to develop and test the two approaches.
Following is the complete Java 8 code for both approaches:
import java.util.Scanner;
/**
*
*/
class Obstacles {
// **** members ****
int n;
int qR;
int qC;
// **** ****
int N;
int NE;
int E;
int SE;
int S;
int SW;
int W;
int NW;
/**
* Constructor.
*/
public Obstacles(int n, int qR, int qC) {
int d = 0;
this.n = n;
this.qR = qR;
this.qC = qC;
// **** ****
this.N = n - qR;
this.E = n - qC;
this.S = qR - 1;
this.W = qC - 1;
// **** ****
d = 0;
for (int r = qR, c = qC; (r < n) && (c < n); r++, c++) { d++; } this.NE = d; // **** **** d = 0; for (int r = qR, c = qC; (r > 1) && (c < n); r--, c++) { d++; } this.SE = d; // **** **** d = 0; for (int r = qR, c = qC; (r > 1) && (c > 1); r--, c--) {
d++;
}
this.SW = d;
// **** ****
d = 0;
for (int r = qR, c = qC; (r < n) && (c > 1); r++, c--) {
d++;
}
this.NW = d;
}
/**
* Print object.
*/
public void print() {
System.out.println("print <<< n: " + this.n);
System.out.println("print <<< (qR,qC): (" + this.qR + "," + qC + ")");
System.out.println("print <<< N: " + this.N);
System.out.println("print <<< NE: " + this.NE);
System.out.println("print <<< E: " + this.E);
System.out.println("print <<< SE: " + this.SE);
System.out.println("print <<< S: " + this.S);
System.out.println("print <<< SW: " + this.SW);
System.out.println("print <<< W: " + this.W);
System.out.println("print <<< NW: " + this.NW);
}
/**
* Update the number of positions open from the queen in the specified direction.
* TAKES into account the position of the queen.
*/
public void update(int c, int r) {
System.out.println("update <<< r,c: (" + r + "," + c + ")"); // **** obstacle N of queen **** if ((c == qC) && (r > qR) && (N > (r - qR - 1))) {
N = (r - qR - 1);
}
// **** obstacle E ****
if ((r == qR) && (c > qC) && (E > (c - qC - 1))) {
E = (c - qC - 1);
}
// **** obstacle S of queen ****
if ((c == qC) && (r < qR) && (S > (qR - r - 1))) {
S = (qR - r - 1);
}
// **** obstacle W ****
if ((r == qR) && (c < qC) && (W > (qC - c - 1))) {
W = (qC - c - 1);
}
// **** obstacle NE of queen ****
if ((r > qR) && (c > qC) && (r - qR == c - qC) && (NE > (r - qR - 1))) {
NE = (r - qR - 1);
}
// **** obstacle SE of queen ****
if ((r < qR) && (c > qC) && (qR - r == c - qC) && (SE > (c - qC - 1))) {
SE = (c - qC - 1);
}
// **** obstacle SW of queen ****
if ((r < qR) && (c < qC) && (qR - r == qC - c) && (SW > (qC - c - 1))) {
SW = (qC - c - 1);
}
// **** obstacle NW of queen ****
if ((r > qR) && (c < qC) && (r - qR == qC - c) && (NW > (r - qR - 1))) {
NW = (r - qR - 1);
}
}
/**
* Compute and display count of positions.
*/
public void compute() {
int distance = 0;
// **** ****
distance = this.N;
distance += this.E;
distance += this.S;
distance += this.W;
// **** ****
distance += this.NE;
distance += this.SE;
distance += this.SW;
distance += this.NW;
// **** ****
System.out.println(distance);
}
}
/**
*
*/
public class Solution {
// **** ****
static enum Approach {
WithBoard,
ClosestPoints
}
/**
* Print chessboard.
* Origin (0,0) @ top left.
*/
static void display(boolean[][] chessboard, int n) {
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) { System.out.print(((chessboard[row][col] == true) ? "X" : "O") + " "); } System.out.println(); } } /** * Place obstacle on chessboard. * Origin (0,0) @ top left. */ static void placeObstacle(int n, boolean[][] chessboard, int r, int c) { r = n - r; c = c - 1; chessboard[r] = true; } /** * Count and display the positions the queen can attack. * Origin (0,0) @ top left. */ static void posCount(int n, int k, int rQ, int cQ, boolean[][] chessboard) { // **** translate queen's position **** rQ = n - rQ; cQ = cQ - 1; // **** count positions per direction **** int count = 0; // **** up **** for (int r = rQ - 1; (r >= 0) && !chessboard[r][cQ]; r--){count++;}
// **** diagonal up right ****
for (int r = rQ - 1, c = cQ + 1; (r >= 0) && (c < n) && !chessboard[r]; r--, c++){count++;}
// **** right ****
for (int c = cQ + 1; (c < n) && !chessboard[rQ]; c++){count++;}
// **** diagonal down right ****
for (int r = rQ + 1, c = cQ + 1; (r < n) && (c < n) && !chessboard[r]; r++, c++){count++;}
// **** down ****
for (int r = rQ + 1; (r < n) && (!chessboard[r][cQ]); r++){count++;}
// **** diagonal down left ****
for (int r = rQ + 1, c = cQ - 1; (r < n) && (c >= 0) && !chessboard[r]; r++, c--){count++;}
// **** left ****
for (int c = cQ - 1; (c >= 0) && !chessboard[rQ]; c--){count++;}
// **** diagonal up left ****
for (int r = rQ - 1, c = cQ - 1; (r >= 0) && (c >= 0) && !chessboard[r]; r--, c--){count++;}
// **** display number of positions ****
System.out.println(count);
}
/**
* Test code.
*/
public static void main(String[] args) {
// **** ****
Approach approach = Approach.ClosestPoints;
// **** open scanner ****
Scanner in = new Scanner(System.in);
// **** ****
int n = in.nextInt();
int k = in.nextInt();
// **** we know the position for the queen before we get the obstacles ****
int rQueen = in.nextInt();
int cQueen = in.nextInt();
// **** ****
switch (approach) {
case ClosestPoints:
// **** ****
Obstacles obstacles = new Obstacles(n, rQueen, cQueen);
// **** read and place obstacles ****
for(int a0 = 0; a0 < k; a0++) {
int r = in.nextInt();
int c = in.nextInt();
// **** update distance based on obstacle ****
obstacles.update(c, r);
}
// **** compute and display position count ****
obstacles.compute();
break;
case WithBoard:
// **** allocate chessboard ****
boolean[][] chessboard = new boolean[n][n];
// **** read and place obstacles ****
for(int a0 = 0; a0 < k; a0++) {
int r = in.nextInt();
int c = in.nextInt();
// **** place obstacle on chessboard ****
placeObstacle(n, chessboard, r, c);
}
// **** display chessboard ****
display(chessboard, n);
// **** compute and display position count ****
posCount(n, k, rQueen, cQueen, chessboard);
break;
}
// **** close scanner ****
in.close();
}
}
The second approach makes use of the Obstacles class; the first one makes use of the Boolean matrix.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.
Regards;
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa