HackerRank - Queens Attack II - Java

Question

The problem definition can already be found here. Given a chess board with dimensions n × n (where n is up to 100000) and the (r, c) positions of various obstacles, how many squares can a queen at a given position attack?

My solution is in Java. Any feedback is welcome.

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class QueensAttack {

    public static int queensAttack(int boardSize, int obstacleAmount, int queen_pos_y, int queen_pos_x, int[][] obstacles) {
        int queensAttack = 0;

        final Set<ObstacleLocation> obstacleLocations = new HashSet<ObstacleLocation>();
        for (int i = 0; i < obstacleAmount; i++) {
            final ObstacleLocation obstacleLocation = new ObstacleLocation(obstacles[i][0], obstacles[i][1]);
            obstacleLocations.add(obstacleLocation);
        }

        queensAttack += goNorth(boardSize, queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goSouth(queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goEast(boardSize, queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goWest(queen_pos_y, queen_pos_x, obstacleLocations);

        queensAttack += goNorthEast(boardSize, queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goSouthEast(boardSize, queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goNorthWest(boardSize, queen_pos_y, queen_pos_x, obstacleLocations);
        queensAttack += goSouthWest(queen_pos_y, queen_pos_x, obstacleLocations);

        return queensAttack;
    }

    private static int goNorth(int boardSize, int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int north = 0;

        while (true) {
            queen_pos_y = queen_pos_y + 1;
            if ((boardSize + 1) == queen_pos_y) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            north++;
        }

        return north;
    }

    private static int goSouth(int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int south = 0;

        while (true) {
            queen_pos_y = queen_pos_y - 1;
            if (0 == queen_pos_y) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            south++;
        }

        return south;
    }

    private static int goEast(int boardSize, int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int east = 0;

        while (true) {
            queen_pos_x = queen_pos_x + 1;
            if ((boardSize + 1) == queen_pos_x) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            east++;
        }

        return east;
    }

    private static int goWest(int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int west = 0;

        while (true) {
            queen_pos_x = queen_pos_x - 1;
            if (0 == queen_pos_x) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            west++;
        }

        return west;
    }

    private static int goNorthEast(int boardSize, int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int northEast = 0;

        while (true) {
            queen_pos_y = queen_pos_y + 1;
            queen_pos_x = queen_pos_x + 1;

            if ((boardSize + 1) == queen_pos_y) {
                break;
            }

            if ((boardSize + 1) == queen_pos_x) {
                break;
            }

            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }

            northEast++;
        }

        return northEast;
    }

    private static int goSouthEast(int boardSize, int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int southEast = 0;

        while (true) {
            queen_pos_y = queen_pos_y - 1;
            queen_pos_x = queen_pos_x + 1;
            if (0 == queen_pos_y) {
                break;
            }
            if ((boardSize + 1) == queen_pos_x) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            southEast++;
        }

        return southEast;
    }

    private static int goNorthWest(int boardSize, int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int northWest = 0;

        while (true) {
            queen_pos_y = queen_pos_y + 1;
            queen_pos_x = queen_pos_x - 1;
            if ((boardSize + 1) == queen_pos_y) {
                break;
            }
            if (0 == queen_pos_x) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            northWest++;
        }

        return northWest;
    }

    private static int goSouthWest(int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        int southWest = 0;
        while (true) {
            queen_pos_y = queen_pos_y - 1;
            queen_pos_x = queen_pos_x - 1;
            if (0 == queen_pos_y) {
                break;
            }
            if (0 == queen_pos_x) {
                break;
            }
            if (obstacleExists(queen_pos_y, queen_pos_x, obstacleLocations)) {
                break;
            }
            southWest++;
        }

        return southWest;
    }

    private static boolean obstacleExists(int queen_pos_y, int queen_pos_x, Set<ObstacleLocation> obstacleLocations) {
        final ObstacleLocation obstacleLocation = new ObstacleLocation(queen_pos_y, queen_pos_x);
        return obstacleLocations.contains(obstacleLocation);
    }
}

class ObstacleLocation {
    private final int pos_y;
    private final int pos_x;

    public ObstacleLocation(int pos_y, int pos_x) {
        this.pos_y = pos_y;
        this.pos_x = pos_x;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ObstacleLocation that = (ObstacleLocation) o;
        return pos_y == that.pos_y &&
                pos_x == that.pos_x;
    }

    @Override
    public int hashCode() {
        return Objects.hash(pos_y, pos_x);
    }
}

For me the most important part is readability. Does this code seem readable to you?

Answer 1

A few suggestions:

• Represent a point (x,y) with an object. It can be in fact exactly what you implemented for ObstacleLocation. There is nothing in this class particular to an obstacle, so it's not a good name anyway. If you rename and make it mutable, you can use it also for the queen's location (just remember to create a copy when passing it to goXXX functions). This could also be used directly instead of creating an object in obstracleExists.

• You can combine some of the ifs, IMO it would improve readability a lot. For example:

  if (0 == queen.y || 0 == queen.x || obstacleLocations.contains(queen)) {
    break;
  }
  

• Functional programming: instead of having all goXXX methods, you could have a single method and pass the a function to do the move, and another function to check if the position is valid. Example of moving S:

  queensAttack += countMoves(queen, q -> q.y--, q -> q.y != 0 && !obstacleLocations.contains(q));  
  

Note that you wouldn't need to pass obstacleLocations and boardSize.

Answer 2

here is my suggestion, regarding the if conditions:

if ((boardSize + 1) == queen_pos_y) should be replaced with if (queen_pos_y > boardSize) it looks technically the same. but there are two reasons to prefer the replacement:

1. it states the purpose of the condition more clearly "is the queen's position outside of the board"

2. what if, for some reason, queen position is advanced two places beyond the board's Size?