Hackerrank Queen's Attack II

Question

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;
using System.Threading.Tasks;

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)
        {
            obstacleHashed.Add(obstacle);
        }

        // 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[0];
        int countObstacles = data[1];

        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[0] - 1, obstacle[1] - 1);
        }

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

Answer 1

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[0];
            int countObstacles = data[1];

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

            // 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[8];

            // Initialize distance to edge of board in each direction.
            distances[0] = qx;
            distances[2] = qy;
            distances[4] = rows + 1 - qx;
            distances[6] = rows + 1 - qy;
            distances[1] = Math.Min(distances[0], distances[2]);
            distances[3] = Math.Min(distances[4], distances[2]);
            distances[5] = Math.Min(distances[4], distances[6]);
            distances[7] = Math.Min(distances[0], distances[6]);

            for (int i = 0; i < countObstacles; i++)
            {
                var obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                int dx        = obstacle[0] - queen[0];
                int dy        = obstacle[1] - queen[1];
                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);
        }
    }
}