Queen’s Attack II Simple Solution – HackerRank

This is a simple and clear solution to the Queen’s  Attack 2 problem in HackerRank. It take just three steps as given below:

  1. determine all the cells the queen can attack without obstacles – queenCells
  2. determine all the cells blocked by the obstacles – pawnCells
  3. return queenCells – pawnCells

That’s it! But seriously, what make this challenge a bit tasking is not only that there are obstacles, but we don’t know how many of them.

For simplicity, I have decided to use the name ‘pawns’ for ‘obstacles’.

To solve this problem, we would need three helper functions:

  1. getCellsQueenCanAttack() – The queen can attack diagonal and orthogonal. For orthogonal, the number of cells is 2n -2 for diagonals the number of cells is given by 2n – 2 – |x – y| – |x + y – n – 1|. Just add the two and you’ll already pass tests for cases with no obstacles.
  2. getRelativeLocation(queenX, queenY, pawnX, pawnY): this function returns one of the position of the pawn relative to the queen. U for up, D for down, L for left, R for right, UL for upper left, DL for down left etc
  3. getCellsBlockedByPawns() – this function will use the relative position of the pawn to determine how many cells lies between the pawn and the edge of the board.

The original chess board setup is shown below:

Original Board Setup
Original Chess Board Setup

 

The board showing the CellsQueenCanAttack (cells the queen can attack). Note that the queen cannot attack herself.

Board showing the QueenAttackCells
Board showing the CellsQueenCanAttack – A total of 14 cells

 

The board showing only the pawns(obstacles) and the cells blocked by them is shown below:

Pawn Blocked Cells
Pawn Blocked Cells –  a total of 4

 

You can see from the figures above that the result in this case is 14 – 4 = 10

 

Helper Function Descriptions

So let’s just look at the three helper functions:

getCellsQueenCanAttack(queenX, queenY, boardSize)

This function is given below. I already explained formula to you earlier. Here, n is the board size and the queen is at position (queenX, queenY).

def getCellsQueenCanAttack(queenX, queenY, boardSize):
    orthognals =  2 * boardSize - 2
    diagonals = 2 * boardSize - 2 - abs(queenX - queenY) - abs(queenX + queenY - boardSize - 1)
    return orthognals + diagonals

 

getRelativeLocation(queenX, queenY, pawnX, pawnY):

This function for a single pawn, returns a value indicating the relative position of the pawn to the queen.

if both are in the same column (ie pawnY = queenY), then it could be ‘U’ or ‘D’ depending on the which is greater between queenX and pawnX. The same logic applies for all other positions. Watch the video for a detailed explanation:

def getRelativeLocation(queenX, queenY, pawnX, pawnY):
    if pawnY == queenY and pawnX < queenX:
        return 'L'
    if pawnY == queenY and pawnX > queenX:
        return 'R'
    if queenX == pawnX and pawnY > queenY:
        return 'U'
    if queenX == pawnX and pawnY < queenY:
        return 'D'
    if abs(queenX - pawnX) == abs(queenY - pawnY): #filter out irrelevant pawns
        if pawnY > queenY and pawnX < queenX:
            return 'UL'
        if pawnY > queenY and pawnX > queenX:
            return 'UR'
        if pawnY < queenY and pawnX > queenX:
            return 'DR'
        if pawnY < queenY and pawnX < queenX:
            return 'DL'

Note that some pawns are irrelevant. These are pawns that fall outside the diagonals and orthogonals of the queen.

 

getCellsBlockedByPawns(queenX, queenY, pawns)

This is the function that does more logic that previous two. So basically what it does is this: for each pawn, get its relative location, then determine how many cells lie between this pawn and the edge of the board. For each cell, add the cell position (x, y) to a set or tuples. This means there will be no repeated counts of the same cell.

At the end just return the count of  the set. This function is given below

def getCellsBlockedByPawns(queenX, queenY, pawns):
    blockedCells = set()   
    for pawn in pawns:
        x = pawn[1]
        y = pawn[0]
        position = getRelativeLocation(queenX, queenY, x, y)
        if position == 'U':
            for i in range(y, n+1):
                blockedCells.add((i, x))
        if position == 'D':
            for i in range(y, 0, -1):
                blockedCells.add((i, x))
        if position == 'L':
            for i in range(x, 0, -1):
                blockedCells.add((y, i))
        if position == 'R':
            for i in range(x, n+1):
                blockedCells.add((y, i))   
        if position == 'UL':
            while y <= n and x > 0:
                blockedCells.add((y, x))
                x -= 1
                y += 1   
        if position == 'UR':
            while y <= n and x <= n:
                blockedCells.add((y, x))
                x += 1
                y += 1 
        if position == 'DR':
            while y > 0 and x <= n:
                blockedCells.add((y, x))
                x += 1
                y -= 1   
        if position == 'DL':
            while y > 0 and x > 0:
                blockedCells.add((y, x))
                x -= 1
                y -= 1 
    return len(blockedCells)

 

QueenAttack() Function

Finally we need to complete the QueenAttack  as shown below.

def queensAttack(boardSize, k, queenY, queenX, pawns):
    # Write your code here
    if len(pawns) == 0:
        return getCellsQueenCanAttack(queenX, queenY, boardSize)
    else:
        queenCells = getCellsQueenCanAttack(queenX, queenY, boardSize)
        pawnCells = getCellsBlockedByPawns(queenX, queenY, pawns)
        return queenCells - pawnCells

From the code, we first check if there are pawns(obstacles), if not, we simply return the number of cells queen can attack without obstacles. If however, there are obstacles, we calculated cell blocked by the obstacles. The we subtract.

Hope this has helped you. I also recommend watching the video and feel free to reach me if you need more clarification.

Queen’s Attack II complete code in Github – https://github.com/KindsonTheGenius/QueenAttack2

Admin bar avatar

kindsonthegenius

Kindson Munonye is currently completing his doctoral program in Software Engineering in Budapest University of Technology and Economics

View all posts by kindsonthegenius →

Leave a Reply

Your email address will not be published. Required fields are marked *