6
\$\begingroup\$

https://www.hackerrank.com/challenges/queens-attack-2/problem

A queen is standing on an nxn 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 (rq,cq) 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):

enter image description here

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)\$:

enter image description here

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:

enter image description here

We then print the number of squares she can attack from that position, which is \$9\$.

My approach:

Instead of iterating through every single point in the queens path as that will be resource intensive when n is very high, I went with separating the paths into 8 different directions (up left, up, up right, right, etc).

int u, d, l, r, ul, ur, dl, dr;
u = d = l = r = ul = ur = dl = dr = 0;
bool modified[8] = { false };

Than I checked if there is an obstacle in the path by checking if the queens x = obstacles x or queens y = obstacles y and if its on the vertical/horizontal path of the queens I would find the distance by calculating the delta - 1 and to find the diagonal points I know since the points either have to have a 1 or -1 slope to be in the queens path so I checked if |queen's y - obstacle's y| = |queen's x - obstacle's x| and if it is true than I find the delta between either the x or y as either work and if there is no obstacles I would just use the edge to find the distance. I only checks to see if obstacle was in path then calculate the possible points than mark the direction as solved so if it is unmarked than it means there is no obstacles in the path so I find the distance from edge using:

if (!modified[0]) u = n - qy;
if (!modified[1]) d = qy - 1;
if (!modified[2]) l = qx - 1;
if (!modified[3]) r = n - qx;
if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

Sorry for messy style, this is my first time on stackoverflow/stackexchange.

Full code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int queensAttack(const int &n, const int &k, const int & qy, const int & qx, const vector<vector<int>> &obstacles) {
    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;          
    bool modified[8] = { false };                   //if modified is still false after looping through obstacles check that means no obstacle at path

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen
        int temp{};
        if (obstacles[i][1] == qx) {                //if obstacle x = queen x than they are on same column
            if (obstacles[i][0] > qy) {             //check if its above or below queen
                temp = obstacles[i][0] - qy - 1;    
                if (modified[0] && u > temp || !modified[0]) {    //only assign distance if it was never assigned before or less than it  
                    u = temp;
                }
                modified[0] = true;
            }
            else {
                temp = qy - obstacles[i][0] - 1;
                if (modified[1] && d > temp || !modified[1]) {
                    d = temp;
                }
                modified[1] = true;
            }
        }
        if (obstacles[i][0] == qy) {
            if (obstacles[i][1] < qx) {
                temp = qx - obstacles[i][1] - 1;
                if (modified[2] && l > temp || !modified[2]) {
                    l = temp;
                }
                modified[2] = true;
            }
            else {
                temp = obstacles[i][1] - qx - 1;
                if (modified[3] && r > temp || !modified[3]) {
                    r = temp;
                }
                modified[3] = true;
            }
        }
        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }
        }
    }
    if (!modified[0]) u = n - qy;                               //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

    return u + d + l + r + ul + ur + dl + dr;
}

int main() {

    int n, k, qx, qy;
    cin >> n >> k >> qy >> qx;
    const int c = k;
    vector<vector<int>> ob(k);
    for (int i = 0; i < k; i++) {
        ob[i].resize(2);
        cin >> ob[i][0] >> ob[i][1];
    }

    cout << queensAttack(n,k,qy,qx,ob);

    return 0;
}

Forgot to mention I loop through the obstacles and only replaces the current distance if the new one is smaller as the obstacles in the array aren't in order from closest to farthest.

Can I get some feedback or suggestions for improvement? Thanks!

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ Also, do you want a review of your answer strictly or do you want to see alternate approaches too? \$\endgroup\$
    – user228914
    Oct 27, 2020 at 3:36
  • 1
    \$\begingroup\$ Please post a program which is also able to be executed. Please create an int main() and call your function with some example-values. Please use meaningful variable names. Please don't do things like this -> u = d = l = r = ul = ur = dl = dr = 0; PS some /* comments */ would help for better understanding your program \$\endgroup\$
    – paladin
    Oct 27, 2020 at 5:30
  • \$\begingroup\$ It is absolutely pointless to have constant reference to primitive types. The whole idea of reference is to not pass whole object, but only a much smaller pointer. In the case of primitive types, they are already small, and you wouldn't gain anything by passing const int's as const int refs. \$\endgroup\$
    – Ilkhd
    Oct 27, 2020 at 11:07
  • \$\begingroup\$ @paladin This is the part of the code that the program challenge left to be programmed, the rest of the program is provided by Hacker Rank. This is very common with questions from code challenge sites. In other words the Original Poster posted all the code they wrote. \$\endgroup\$
    – pacmaninbw
    Oct 27, 2020 at 11:37
  • 1
    \$\begingroup\$ @pacmaninbw I know about this, but OP should anyway implement his own testing environment. \$\endgroup\$
    – paladin
    Oct 27, 2020 at 12:02

2 Answers 2

Reset to default
4
\$\begingroup\$

General Observations

It was good that you included the necessary headers rather than using the catchall header provided by Hacker Rank. You did include headers that were unnecessary, the code compiles without cmath or algorithm. Only include what is necessary to make the code compile. Using unnecessary headers can increase build times because C++ actually creates a temporary file and copies the headers into that temporary file.

As a professional software developer one needs to be concerned with maintenance of the code (adding features, fixing bugs). You may write code but not be the person that maintains it because you could be on vacation, you may have gotten a better job at another company, you may have suddenly become rich.

This code will be very difficult to maintain. Some of it is very easy to read and some of it is almost unreadable. Some examples of almost unreadable code are:

    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;

and

    if (!modified[0]) u = n - qy;        //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

The function queensAttack() is 88 lines and a single function that size is very difficult to write, read, debug or maintain.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Complexity

The function queensAttack() is too complex (does too much). It should be broken up into functions, I see at least 3 possible functions and probably more. A good design technique is to keep breaking a problem into separate smaller problems until each problem is very easy to solve. This also make the code more maintainable.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Magic Numbers

There are Magic Numbers in the queensAttack() function (0 through 7), it might be better to create symbolic constants for them to make the code more readable and easier to maintain, in this case an enum could also be used. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Prefer unsigned Types to Integer for Index Variables

When indexing into arrays or other container types it is better to use unsigned types such as size_t rather than integers. Unsigned types cannot become negative and using a negative index can lead to undefined behavior. The size() function of all container types returns size_t and the code is generating a type mismatch warning in the for loop:

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen

Variable Declarations

Declare and initialize variables one per line. While the following results in a lot of added vertical space it is easier to read and maintain:

    int u = 0;
    int d = 0;
    int l = 0;
    int r = 0;
    int ul = 0;
    int ur = 0;
    int dl = 0;
    int dr = 0;
    bool modified[8] = { false };

If some needs to add or delete a variable it is much easier to add a line or delete a line than to modify the current code. In this case it might also be possible to have an array of directions that matches the array of modifications that already exists, especially if the enum mentioned above is used to index both arrays.

Variable Names

It is generally better to use descriptive variable names to make the code more readable. Comments are okay, but they need to be maintained as well, self documenting code is better than using comments when that can be done.

DRY Code

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

This is very repetitious code:

        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Thank you so much! 😊 \$\endgroup\$
    – Bork
    Oct 28, 2020 at 2:34
  • \$\begingroup\$ The function queensAttack() should not be broken up. Instead, the algorithm should be reworked. \$\endgroup\$
    – Deduplicator
    Oct 28, 2020 at 17:40
  • \$\begingroup\$ Amazing answer. I tried to edit and correct the formatting by changing "##Complexity" to "## Complexity", but Stack doesn't allow such a tiny change. \$\endgroup\$
    – JSmart523
    Oct 28, 2020 at 17:53
  • \$\begingroup\$ @JSmart523 thank you for the heads up, I fixed the formatting. \$\endgroup\$
    – pacmaninbw
    Oct 28, 2020 at 18:02
  • \$\begingroup\$ @Deduplicator I agree the algorithm should be reworked, the goal of my review was to improve some programming habits, and it may provide the OP with an understanding of why another algorithm would be better. \$\endgroup\$
    – pacmaninbw
    Oct 28, 2020 at 18:26
2
\$\begingroup\$

Your Code:

  1. Good on you to only include the headers you think you need. You don't use anything from <cmath> or <algorithm> though.

  2. using namespace std; is plain evil. That namespace is not designed for inclusion, thus there is no comprehensive, fixed and reliable list of its contents.
    See "Why is “using namespace std;” considered bad practice?" for details.

  3. Small trivial types are better passed by copy than by value. Less indirection means more efficient access, and no need to beware of anyone else mucking about with the value, which improves reasoning about the code and generally enables better optimisation.
    See "In C++, why shouldn't all function parameters be references?".

  4. Take a look at std::span for passing a view of contiguous objects.
    See also "What is a “span” and when should I use one?".

  5. C++ has for-range loops since C++11. Much less error-prone than manually fiddling with indices or iterators.

  6. Using flags to check whether a ray encountered an obstacle and otherwise returning the maximum is distinctly sub-optimal. Just initialize with the maximum and update that as needed.

  7. A std::vector of length two is a very poor data-structure to store a point's coordinates. It is very inefficient, inconvenient and error-prone. At least use a std::pair, std::array, or std::tuple, if you decline to invest a single line for a trivial custom type.

  8. Your code never tests the user-input is well-formed. Actually, that can be justified for a challenge like this, so let's keep it.

  9. return 0; is implicit for main() in C++ and C99+.

Your approach can be optimized and simplified further:

  1. Use a queen-centric coordinate-system. All the checks are about the queen, and now much simpler.

  2. If you store the reach of each arm of the queen's attack considering the obstacles you know (initialise with the border), you can immediately drop each obstacle after processing.

#include <algorithm>
#include <iostream>

int main() {
    int x, y, k, qx, qy;
    std::cin >> x >> k >> qx >> qy;

    int d = qy,
        l = qx,
        u = x + 1 - qy,
        r = x + 1 - qx;
    int dl = std::min(d, l),
        dr = std::min(d, r),
        ul = std::min(u, l),
        ur = std::min(u, r);
    auto update = [](int a, int& b, int& c){
        if (a < 0)
            b = std::min(b, -a);
        else
            c = std::min(c, a);
    };

    while (k--) {
        std::cin >> x >> y;
        x -= qx;
        y -= qy;
        if (!x)
            update(y, d, u);
        else if (!y)
            update(x, l, r);
        else if (x == y)
            update(x, dl, ur);
        else if (x == -y)
            update(x, ul, dr);
    }

    std::cout << (d + u + l + r + dl + dr + ul + ur - 8);
}

Beware: The above code was only proven right, never run.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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