Queen's Attack II Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Queen's Attack II
  5. Discussions

Queen's Attack II

Sort by

recency

|

937 Discussions

|

  • oborrallo
     + 0 comments

    My solution in Java.

    The idea is count distances from queen on every cardinal point until:

    a. An obstacle is found. b. Chessboard edge is found.

    So response will be movesToNorth + movesToSouth + movesToEast+...

    public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {
    // Write your code here
    // By default, distance to row beyond upper chessboard bound
    int distanceToNearestNorthObstacle = n - r_q + 1;
    // By default, distance to row beyond lower chessboard bound
    int distanceToNearestSouthObstacle = r_q;
    // By default, distance to column beyond right chessboard bound
    int distanceToNearestEastObstacle = n - c_q + 1;
    // By default, distance to column beyond left chessboard bound
    int distanceToNearestWestObstacle = c_q;
    int distanceToNearestNorthEastObstacle = Math.min(distanceToNearestNorthObstacle, distanceToNearestEastObstacle);
    int distanceToNearestNorthWestObstacle = Math.min(distanceToNearestNorthObstacle, distanceToNearestWestObstacle);
    int distanceToNearestSouthEastObstacle = Math.min(distanceToNearestSouthObstacle, distanceToNearestEastObstacle);
    int distanceToNearestSouthWestObstacle = Math.min(distanceToNearestSouthObstacle, distanceToNearestWestObstacle);
    for(List<Integer> obstacle : obstacles) {
        int obstacleRow = obstacle.get(0);
        int obstacleColumn = obstacle.get(1);
        // Is obstacle in vertical ?
        if(r_q == obstacleRow) {
            if(c_q < obstacleColumn) {
                distanceToNearestEastObstacle = Math.min(distanceToNearestEastObstacle, obstacleColumn - c_q);
            } else {
                distanceToNearestWestObstacle = Math.min(distanceToNearestEastObstacle, c_q - obstacleColumn);
            }
            continue;
        }
        // Is obstacle in horizontal ? 
        if(c_q == obstacleColumn) {
            if(r_q < obstacleRow) {
                distanceToNearestNorthObstacle = Math.min(distanceToNearestNorthObstacle, obstacleRow - r_q);
            } else {
                distanceToNearestSouthObstacle = Math.min(distanceToNearestSouthObstacle, r_q - obstacleRow);
            }
            continue;
        }
        // Is obstacle in any diagonal ? 
        if(Math.abs(c_q - obstacleColumn) == Math.abs(r_q - obstacleRow)) {
            if(r_q < obstacleRow && c_q < obstacleColumn) {
                distanceToNearestNorthEastObstacle = Math.min(distanceToNearestNorthEastObstacle, obstacleColumn - c_q);
            } else if(r_q < obstacleRow && c_q > obstacleColumn) {
                distanceToNearestNorthWestObstacle = Math.min(distanceToNearestNorthWestObstacle, obstacleRow - r_q);
            } else if(r_q > obstacleRow && c_q < obstacleColumn) {
                distanceToNearestSouthEastObstacle = Math.min(distanceToNearestSouthEastObstacle, r_q - obstacleRow);
            } else {
                distanceToNearestSouthWestObstacle = Math.min(distanceToNearestSouthWestObstacle, r_q - obstacleRow);
            }
            continue;
        }
    }
    return (distanceToNearestNorthObstacle - 1) + (distanceToNearestSouthObstacle - 1) + (distanceToNearestEastObstacle - 1) + (distanceToNearestWestObstacle - 1) + (distanceToNearestNorthEastObstacle - 1) + (distanceToNearestNorthWestObstacle - 1) + (distanceToNearestSouthEastObstacle - 1) + (distanceToNearestSouthWestObstacle - 1);

    }

  • ihorfinance
     + 0 comments

    C++ O(n) time and space complexity (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star :) )

    int queensAttack(
    int const & _n, 
    int const & _k,
    int const & _rQ,
    int const & _cQ,
    std::vector<std::vector<int>> & _obstacles
){
    using namespace std;
    auto leftMoves = _cQ - 1;
    auto rightMoves = _n - _cQ;
    auto upMoves = _rQ - 1;
    auto downMoves = _n - _rQ;
    auto toUpperLeftMoves = min(_rQ - 1, _cQ - 1);
    auto toLowerRightMoves = min(_n - _rQ, _n - _cQ);
    auto toUpperRightMoves = min(_rQ - 1, _n - _cQ);
    auto toLowerLeftMoves = min(_n - _rQ, _cQ - 1);
    auto diff = _rQ - _cQ;
    auto sum = _rQ + _cQ;
    for(auto const & rc : _obstacles){
        if(rc.at(0) == _rQ){
            if(rc.at(1) < _cQ){
                leftMoves = min(leftMoves, _cQ - rc.at(1) - 1);
            }else{
                 rightMoves = min(rightMoves, rc.at(1) - _cQ - 1);
            }
        }else if(rc.at(1) == _cQ){
            if(rc.at(0) < _rQ){
                upMoves = min(upMoves, _rQ - rc.at(0) - 1);
            }else{
                downMoves = min(downMoves, rc.at(0) - _rQ - 1);
            }
        }else if(rc.at(0) - rc.at(1) == diff){
            if(rc.at(0) < _rQ){
                toUpperLeftMoves = min(toUpperLeftMoves, _rQ - rc.at(0)
                    - 1);
            }else{
                toLowerRightMoves = min(toLowerRightMoves, rc.at(0) - _rQ
                    - 1);
            }
        }else if(rc.at(0) + rc.at(1) == sum){
            if(rc.at(0) < _rQ){
                toUpperRightMoves = min(toUpperRightMoves, _rQ - rc.at(0)
                    - 1);
            }else{
                toLowerLeftMoves = min(toLowerLeftMoves, rc.at(0) - _rQ - 1);
            }
        }
    }
    return leftMoves + rightMoves + upMoves + downMoves + toUpperLeftMoves
        + toLowerRightMoves + toUpperRightMoves + toLowerLeftMoves;
}

  • ztekinerten
     + 0 comments

    python

    def queensAttack(n, k, r_q, c_q, obstacles):
    # count of attacks without any obstacles
    attacks = (n-1)*2 + min(r_q-1, n-c_q) + min(n-r_q, n-c_q) + min(r_q-1, c_q-1) + min(n-r_q, c_q-1)
    # values to delete for each direction
    right, left, up, down, right_up, left_up, right_down, left_down = ([0] for i in range(8))
    
    for ob in obstacles:
        r_ob = ob[0]
        c_ob = ob[1]
             
        # right-left  
        if r_ob == r_q:
            if c_ob > c_q:
                right.append((n-c_q) - (abs(c_ob - c_q) - 1))
            else:
                left.append((c_q-1) - (abs(c_ob - c_q) - 1))
         
        # down-up
        elif c_ob == c_q:
            if r_ob > r_q:
                down.append((n-r_q) - (abs(r_ob - r_q) - 1))
            else:
                up.append((r_q-1) - (abs(r_ob - r_q) - 1))
                
        # right up- left down
        elif r_ob - c_ob == r_q -c_q:
            if r_ob > r_q:
                right_up.append(min(n-r_q, n-c_q) - (abs(r_ob - r_q) - 1))
            else:
                left_down.append(min(r_q-1, c_q-1) - (abs(r_ob - r_q) - 1))
                
        # left up - right down
        elif abs(r_ob-r_q) == abs(c_ob - c_q):
            if r_ob >r_q:
                right_down.append(min(n-r_q, c_q -1)- (abs(r_ob - r_q) - 1))
            else:
                left_up.append(min(r_q -1, n-c_q)- (abs(r_ob - r_q) - 1))
    
    # for each direction get the maximum number to delete
    attacks_to_delete = list(map(max, [up, down, right, left, right_up, right_down, left_up, left_down]))
    
    return attacks-sum(attacks_to_delete)

  • gurfire1
     + 0 comments

    def queensAttack(n, k, r_q, c_q, obstacles): final=0

    def all_move(n, r_q, c_q):
    h_v=2*(n-1)
    s=min(r_q-1,c_q-1)+min(n-r_q,c_q-1)+min(n-r_q,n-c_q)+min(r_q-1,n-c_q)
    return (h_v + s) if (h_v + s) else 0


def blok(n, k, r_q, c_q, obstacles):
    blocker={
        "h":{"near":[],"far":[]}, "v":{"near":[],"far":[]}, "s":{"snn":[],"sfn":[],"sff":[],"snf":[]}
    }
    for r in obstacles:
        if not(r[0]==r_q and r[1]==c_q): #not same position as queen
            if((r[0]==r_q) or (r[1])== c_q):  # checking vertical & horizonatal blockers

                if((r[1]==c_q)): # checking vertical blockers
                    if (r_q - r[0])>0:
                        if not(len(blocker["v"]["near"])):
                            blocker["v"]["near"]=r
                            blocker["v"]["near"].append(r[0])
                        elif((r[0] - blocker["v"]["near"][1])>0):
                                blocker["v"]["near"]=r  
                                blocker["v"]["near"].append(r[0])

                    elif (r_q - r[0])<0:
                        if not(len(blocker["v"]["far"])):
                            blocker["v"]["far"]=r
                            blocker["v"]["far"].append(n- r[0] + 1)
                        elif((r[0] - blocker["v"]["far"][1])<0):
                                blocker["v"]["far"]=r
                                blocker["v"]["far"].append(n- r[0] + 1)


                elif((r[0]==r_q)): # checking horizontal blockers
                    if (c_q - r[1])>0:
                        if not(len(blocker["h"]["near"])):
                            blocker["h"]["near"]=r
                            blocker["h"]["near"].append(r[1])
                        elif((r[1] - blocker["h"]["near"][1])>0):
                                blocker["h"]["near"]=r
                                blocker["h"]["near"].append(r[1]) 

                    elif (c_q - r[1])<0:
                        if (not(len(blocker["h"]["far"]))):
                            blocker["h"]["far"]=r
                            blocker["h"]["far"].append(n-r[1]+1)
                        elif((r[1] - blocker["h"]["far"][1])<0):
                                blocker["h"]["far"]=r
                                blocker["h"]["far"].append(n-r[1]+1)

            else:# side blockers
                blkr=[r[1],r[0]]
                row=c_q
                col=r_q
                cases={
                    "snn": {
                        "case": ((blkr[0]< row) and (blkr[1] < col)),
                        "moves_blocked":  min(blkr[0]-1, blkr[1]-1)+1,
                        "queen_moves": min(row-1,col-1)
                    },
                    "sfn": {
                        "case": ((blkr[0]< row) and (blkr[1] > col)),
                        "moves_blocked": min(blkr[0]-1, n-blkr[1])+1,
                        "queen_moves": min(row-1,n-col)
                    },
                    "sff": {
                        "case": ((blkr[0]> row) and (blkr[1] > col)),
                        "moves_blocked": min(n-blkr[0], n-blkr[1])+1,
                        "queen_moves": min(n-row,n-col)
                    },
                    "snf": {
                        "case": ((blkr[0]> row) and (blkr[1] < col)),
                        "moves_blocked": min(n-blkr[0], blkr[1]-1)+1,
                        "queen_moves": min(n-row,col-1)
                    }
                }

                if((abs(row-blkr[0]) == abs(col- blkr[1]))):
                    for c in cases:
                        if(cases[c]["case"]):
                            def manage():
                                blocker["s"][c]=blkr
                                blocker["s"][c].append(cases[c]["moves_blocked"])

                            if(not(len(blocker["s"][c]))):
                                manage()
                            elif(abs(row-blkr[0]) <  abs(row-(blocker["s"][c][0]))):
                                manage()                        

    #all blockeed moves
    blocked_move_count= ((blocker["h"]["near"][-1])if len(blocker["h"]["near"]) else 0) + ((blocker["h"]["far"][-1])if len(blocker["h"]["far"]) else 0) + ((blocker["v"]["near"][-1])if len(blocker["v"]["near"]) else 0) + ((blocker["v"]["far"][-1])if len(blocker["v"]["far"]) else 0) + ((blocker["s"]["snn"][-1])if len(blocker["s"]["snn"]) else 0) + ((blocker["s"]["sfn"][-1])if len(blocker["s"]["sfn"]) else 0)+ ((blocker["s"]["sff"][-1])if len(blocker["s"]["sff"]) else 0) + ((blocker["s"]["snf"][-1])if len(blocker["s"]["snf"]) else 0)

    return blocked_move_count if blocked_move_count else 0

final= all_move(n, r_q, c_q) - blok(n, k, r_q, c_q, obstacles)                           
return final

  • jvk2117
     + 0 comments

    I wrote a c# struct that saves the board state, and allows you to add an obstacle and modify the movable spaces based on the current state.

        {
        BoardConfig boardConfig = new BoardConfig(r_q, c_q, n);
        
        for(int i = 0; i < k; ++i)
        {
            boardConfig.AddObsticle(obstacles[i]);
        }
        
        return boardConfig.GetMaxMoves();
    }
    
    private struct BoardConfig
    {
        public int RowIndex { get; private set; }
        public int ColumnIndex { get; private set; }
        public int BorderMax { get; private set; }
        public int BorderMin { get; private set; }
        
        public int LeftMax { get; private set; }
        public int RightMax { get; private set; }
        public int UpMax { get; private set; }
        public int DownMax { get; private set; }
        public int UpRightMax { get; private set; }
        public int UpLeftMax { get; private set; }
        public int DownLeftMax { get; private set; }
        public int DownRightMax { get; private set; }
        
        public BoardConfig(int queenRow, int queenColumn, int boardSize)
        {
            RowIndex = queenRow - 1;
            ColumnIndex = queenColumn - 1;
            BorderMax = boardSize - 1;
            BorderMin = 0;
            
            LeftMax = Math.Max(ColumnIndex, BorderMin);
            RightMax = BorderMax - Math.Min(ColumnIndex, BorderMax);
            UpMax = BorderMax - Math.Min(RowIndex, BorderMax);
            DownMax = Math.Max(RowIndex, BorderMin);
            UpRightMax = Math.Min(UpMax, RightMax);
            UpLeftMax = Math.Min(UpMax, LeftMax);
            DownLeftMax = Math.Min(DownMax, LeftMax);
            DownRightMax = Math.Min(DownMax, RightMax);
        }
        
        public void Print()
        {
            Console.WriteLine("RowIndex: " + RowIndex);
            Console.WriteLine("ColumnIndex: " + ColumnIndex);
            Console.WriteLine("BorderMax: " + BorderMax);
            Console.WriteLine("BorderMin: " + BorderMin);
            Console.WriteLine("LeftMax: " + LeftMax);
            Console.WriteLine("RightMax: " + RightMax);
            Console.WriteLine("UpMax: " + UpMax);
            Console.WriteLine("DownMax: " + DownMax);
            Console.WriteLine("UpRightMax: " + UpRightMax);
            Console.WriteLine("UpLeftMax: " + UpLeftMax);
            Console.WriteLine("DownLeftMax: " + DownLeftMax);
            Console.WriteLine("DownRightMax: " + DownRightMax);
        }
        
        public void AddObsticle(List<int> obstacle)
        {
            int x, y;
            y = obstacle[0] - 1;
            x = obstacle[1] - 1;
            if(RowIndex == y)
            {
               CheckLeftRightMax(x);
            }
            else if(ColumnIndex == x)
            {
                CheckUpDownMax(y);
            }
            else
            {
                CheckDiagonals(x, y);
            }
        }
        
        private void CheckLeftRightMax(int obstacleX)
        {
            if(obstacleX > ColumnIndex)
            {
                RightMax = Math.Min(RightMax, obstacleX - 1 - ColumnIndex);
            }
            else
            {
                LeftMax = Math.Min(LeftMax, ColumnIndex - 1 - obstacleX);
            }
        }
        
        private void CheckUpDownMax(int obstacleY)
        {
            if(obstacleY > RowIndex)
            {
                UpMax = Math.Min(UpMax, obstacleY - 1 - RowIndex);
            }
            else
            {
                DownMax = Math.Min(DownMax, RowIndex - 1 - obstacleY);
            }
        }
        
        private void CheckDiagonals(int obstacleX, int obstacleY)
        {
            int difX = obstacleX - ColumnIndex;
            int difY = obstacleY - RowIndex;
            if(Math.Abs(difX) == Math.Abs(difY))
            {
                int dist = Math.Abs(difX) - 1;
                if(difX > 0)
                {
                    if(difY > 0) // Up Right
                    {
                        UpRightMax = Math.Min(UpRightMax, dist);
                    }
                    else // Down Right
                    {
                        DownRightMax = Math.Min(DownRightMax, dist);
                    }
                }
                else
                {
                    if(difY > 0) // Up Left
                    {
                        UpLeftMax = Math.Min(UpLeftMax, dist);
                    }
                    else // Down Left
                    {
                        DownLeftMax = Math.Min(DownLeftMax, dist);
                    }
                }
            }   
        }
        
        public int GetMaxMoves()
        {
            return LeftMax + RightMax + UpMax + DownMax + UpRightMax + UpLeftMax + DownLeftMax + DownRightMax;
        }
    }