Hackerrank Queen's Attack II

Problem statement

A queen is standing on an $n$x$n$ chessboard. The chessboard's rows are numbered from $1$ to $n$, going from bottom to top; its columns are numbered from $1$ to $n$, going from left to right. Each square on the board is denoted by a tuple, $(r,c)$, describing the row, $r$, and column, $c$, where the square is located.

The queen is standing at position $(r_q,c_q)$ and, in a single move, she can attack any square in any of the eight directions (left, right, up, down, or the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from $(4,4)$: There are $k$ obstacles on the chessboard preventing the queen from attacking any square that has an obstacle blocking the the queen's path to it. For example, an obstacle at location $(3,5)$ in the diagram above would prevent the queen from attacking cells $(3,5)$, $(2,6)$, and $(1,7)$: Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at $(r_q,c_q)$.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the side length of the board) and $k$ (the number of obstacles).

The next line contains two space-separated integers describing the respective values of $r_q$ and $c_q$, denoting the position of the queen.

Each line $i$ of the $k$ subsequent lines contains two space-separated integers describing the respective values $r_i$ of $c_i$ and , denoting the position of obstacle $i$.

Constraints

$0 \leq n \leq 100000$

$0 \leq k \leq 100000$

A single cell may contain more than one obstacle; however, it is guaranteed that there will never be an obstacle at position $(r_q,c_q)$ where the queen is located.

Output Format

Print the number of squares that the queen can attack from position .

Sample Input 0

$4$ $0$

$4$ $4$

Sample Output 0

$9$

Explanation 0

The queen is standing at position $(4,4)$ on a $4$x$4$ chessboard with no obstacles: We then print the number of squares she can attack from that position, which is $9$.

My introduction of algorithm:

This algorithm is a medium one in hackerrank world codesprint 9 contest, and I like to code review the solution I wrote after the contest, instead of the one in the contest. Because in the contest, I did not encapsulate the 8 directions very well, I spent time to write code for each direction. And I am studying the open/ close principle, the idea of implementation is the similar, do not write if/ else code to discuss each direction. Enumerate all directions by iterating the directions array once:

// start from left, clockwise, left up, up, right up, right, ...
public static int[] directions_row = new int[] {  0,  1, 1, 1, 0, -1, -1, -1 };
public static int[] directions_col = new int[] { -1, -1, 0, 1, 1,  1,  0, -1 };

For example, left direction $(0, -1)$, clockwise, next direction is left-up, $(1,-1)$. Enumerate all directions, for each direction, starting from the position of queen, just increment one by one using two direction arrays if staying in the boundary of matrix and it is not an obstacle cell.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QueenAttackII
{
/*
* January 30, 2017
* problem statement:
* https://www.hackerrank.com/contests/world-codesprint-9/challenges/queens-attack-2
*
*/
public class Directions
{
// start from left, clockwise, left and up, up, right and up, right,
//            right and down, down, left and down
public static int[] directions_row = new int[] {  0,  1, 1, 1, 0, -1, -1, -1 };
public static int[] directions_col = new int[] { -1, -1, 0, 1, 1,  1,  0, -1 };

public int rows { get; set; }

public Tuple<int, int> queen { set; get; }

public Directions(int row, int col, int size)
{
queen = new Tuple<int, int>(row, col);

rows = size;
}

public int CalculateTotal(Tuple<int, int>[] obstacles)
{
// put all obstacles in a hashset
var obstacleHashed = new HashSet<Tuple<int, int>>();
foreach (Tuple<int, int> obstacle in obstacles)
{
}

// go over each direction
int count = 0;

for (int i = 0; i < 8; i++)
{
int rowIncrement = directions_row[i];
int colIncrement = directions_col[i];

int runnerRow = queen.Item1 + rowIncrement;
int runnerCol = queen.Item2 + colIncrement;

while( runnerRow >= 0 && runnerRow < rows &&
runnerCol >= 0 && runnerCol < rows &&
!obstacleHashed.Contains(new Tuple<int,int>(runnerRow, runnerCol)))
{
runnerRow += rowIncrement;
runnerCol += colIncrement;

count++;
}
}

return count;
}
}

class Program
{
static void Main(string[] args)
{
ProcessInput();
}

public static void ProcessInput()
{
var data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

int rows = data;
int countObstacles = data;

var queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
var obstacles = new Tuple<int, int>[countObstacles];

for (int i = 0; i < countObstacles; i++)
{
var obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
obstacles[i] = new Tuple<int, int>(obstacle - 1, obstacle - 1);
}

var directions = new Directions(queen - 1, queen - 1, rows);
Console.WriteLine(directions.CalculateTotal(obstacles));
}
}
}

Hashing obstacles could be faster

Currently, you read all the obstacles into an array, and then you add all your obstacles from the array to a HashSet. You could just skip creating the array and just add the obstacles directly to your HashSet instead.

Another thing that would help would be to determine if the obstacles even need to be added. An obstacle only needs to be added if it lies in a direct path of the queen in one of the 8 directions. If the obstacle is not in the path of the queen, it doesn't need to be added to the HashSet.

Alternative algorithm

Just making the HashSet more efficient might make your program fast enough to pass the challenge. But your main loop still has to check each square in each of the 8 directions, and this takes quite a bit of time.

There is a simpler way to solve the problem without using a HashSet and without using a loop over the squares. Imagine we have an array which holds the distance from the queen to the nearest obstacle in each of the 8 directions. Initially, the array is initialized to the distance from the queen to the edges of the board. As we read in each obstacle's position, we can determine whether the obstacle is in the path of the queen in one of the 8 directions. If it is, and it is closer than the nearest obstacle in that direction, then we can update the array to make the new obstacle be the nearest obstacle.

After handling every obstacle, we can find the number of squares the queen can attack by summing the values of the array, which are the distances from the queen to the nearest obstacle in each direction. There is a slight adjustment of -1 to each direction because the queen can't actually attack the obstacle itself.

Sample implementation

Here is an implementation of the above idea:

using System;
using System.Text;

namespace QueenAttackII
{
/*
* January 30, 2017
* problem statement:
* https://www.hackerrank.com/contests/world-codesprint-9/challenges/queens-attack-2
*
*/
class Program
{
static void Main(string[] args)
{
ProcessInput();
}

public static void ProcessInput()
{
var data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

int rows = data;
int countObstacles = data;

var queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int qx    = queen;
int qy    = queen;

// Directions:
// 0 = left,  1 = left and up,    2 = up,   3 = right and up,
// 4 = right, 5 = right and down, 6 = down, 7 = left and down
int [] distances = new int;

// Initialize distance to edge of board in each direction.
distances = qx;
distances = qy;
distances = rows + 1 - qx;
distances = rows + 1 - qy;
distances = Math.Min(distances, distances);
distances = Math.Min(distances, distances);
distances = Math.Min(distances, distances);
distances = Math.Min(distances, distances);

for (int i = 0; i < countObstacles; i++)
{
var obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int dx        = obstacle - queen;
int dy        = obstacle - queen;
int direction = 0;
int distance  = 0;

if (dx == 0)
{
// Up or down.
direction = (dy < 0) ? 2 : 6;
distance  = Math.Abs(dy);
}
else if (dy == 0)
{
// Left or right.
direction = (dx < 0) ? 0 : 4;
distance  = Math.Abs(dx);
}
else if (Math.Abs(dx) == Math.Abs(dy))
{
// Diagonal.
if (dx < 0) {
// Left up or left down
direction = (dy < 0) ? 1 : 7;
} else {
// Right up or right down
direction = (dy < 0) ? 3 : 5;
}
distance = Math.Abs(dx);
}
else
{
// Not in any of the 8 directions, skip this obstacle.
continue;
}
// If this obstacle is closer than the previous obstacle in
// this direction, then update the distance to the nearest
// obstacle.
if (distance < distances[direction])
{
distances[direction] = distance;
}
}

// Compute the number of spaces the queen can move.  Note that
// we need to subtract 1 from each direction because the queen
// can't move on to the square of the obstacle.
int total = 0;
for (int i = 0; i < 8; i++)
{
total += distances[i] - 1;
}
Console.WriteLine(total);
}
}
}
• My algorithm is not efficient for special case, for example, when there is no obstacle but still start from queen position increment one by one in each direction, size of n, up to 100000; but your algorithm also is not efficient for special case, such as the minimum obstacle for each direction can be found just by walking one or two steps from queen position, first obstacle to meet is the minimum one, but instead go over all obstacles to compare with minimum value. And in fact all obstacles k can up to 100000. – Jianmin Chen Feb 4 '17 at 8:04
• @JianminChen I disagree. Your program does exactly k HashSet insertions followed by up to 4n HashSet finds. My program does exactly k distance comparisons which are less expensive than HashSet insertions. So my program is faster in all cases. – JS1 Feb 4 '17 at 8:30
• you are correct on time complexity analysis. It is less time to avoid using hashset, however, I did write the same idea in the contest, the code is gist.github.com/jianminchen/ea01caea42fafa41a5085b36e1b0059a. But I ended up using more than 2.5 hours to write and debug. The way you write as your comment says "Initialize distance to edge of board in each direction" is to find maximum value first, and then compare to find minimum one. The code is shorter than mine in the contest. Your comment is very clear, is very instructional, code is very lean. – Jianmin Chen Feb 4 '17 at 8:56
• @JianminChen I see, you had the same idea but your code was more complex. Hopefully, you can learn something from this shorter code and it will help you in your next challenge. – JS1 Feb 4 '17 at 9:05
• it is easy to write code using HashSet and encapsulate all directions in one or two arrays, avoid to get into the detail of each direction in the code. Even you add/ remove some directions, you do not need to refactor the code, only touch the two arrays for directions. That is something like 'Open for extension, close for change' code. But in theory, as you analyze, your approach is more time efficient, but it takes extra effort to take care each direction. For me, I created bugs and then I learned lessons, took me 3 submissions in the contest. – Jianmin Chen Feb 4 '17 at 9:33