Hacker Rank: Queens II

queensII.py

#!/bin/python3

#WARNING: Spoiler of https://www.hackerrank.com/challenges/queens-attack-2/problem

import math
import os
import random
import re
import sys

memo = None
def hit_obstacle(r,c,obstacles):
    global memo
    if (memo == None):
        memo = {}
        for obs in obstacles:
            memo[(obs[0]-1,obs[1]-1)] = True
    hit = memo.get((r,c), False)
    return hit

def mark_one(r,c,obstacles):
    if hit_obstacle(r,c,obstacles):
        return 0
    else:
        return 1

def mark_l(n,r_q,c_q,obstacles):
    x = 0
    for c in range(c_q-1,-1,-1):
        r = r_q
        if mark_one(r,c,obstacles):
            x += 1
        else:
            break
    return x

def mark_r(n,r_q,c_q,obstacles):
    x = 0
    for c in range(c_q+1,n):
        r = r_q
        if mark_one(r,c,obstacles):
            x+= 1
        else:
            break
    return x

def mark_u(n,r_q,c_q,obstacles):
    x = 0
    for r in range(r_q+1,n):
        c = c_q
        if mark_one(r,c,obstacles):
            x+= 1
        else: 
            break
    return x

def mark_d(board,r_q,c_q,obstacles):
    x = 0
    for r in range(r_q-1,-1,-1):
        c = c_q
        if mark_one(r,c,obstacles):
            x += 1
        else:
            break
    return x

def mark_ul(n,r_q,c_q,obstacles):
    x = 0
    for d in range(1,n - r_q):
        r = r_q + d
        c = c_q - d
        if c < 0:
            break
        elif mark_one(r,c,obstacles):
            x += 1
        else:
            break
    return x
    
def mark_ur(n,r_q,c_q,obstacles):
    x = 0
    for d in range(1,n - r_q):
        r = r_q + d
        c = c_q + d
        if c >= n:
            break
        elif mark_one(r,c,obstacles):
            x+=1
        else:
            break
    return x

def mark_dl(n,r_q,c_q,obstacles):
    x = 0
    for d in range(1,r_q+1):
        r = r_q - d
        c = c_q - d
        if c < 0:
            break
        elif mark_one(r,c,obstacles):
            x += 1
        else:
            break
    return x

def mark_dr(n,r_q,c_q,obstacles):
    x = 0
    for d in range(1, r_q+1):
        r = r_q - d
        c = c_q + d
        if c >= n:
            break
        elif mark_one(r,c,obstacles): 
            x += 1
        else:
            break
    return x

def mark_all(n,r_q,c_q,obstacles):
    x = 0
    x += mark_l(n,r_q,c_q,obstacles)
    x += mark_r(n,r_q,c_q,obstacles)
    x += mark_u(n,r_q,c_q,obstacles)
    x += mark_d(n,r_q,c_q,obstacles)
    x += mark_ul(n,r_q,c_q,obstacles)
    x += mark_ur(n,r_q,c_q,obstacles)
    x += mark_dl(n,r_q,c_q,obstacles)
    x += mark_dr(n,r_q,c_q,obstacles)
    return x

# Complete the queensAttack function below.
def queensAttack(n, k, r_q, c_q, obstacles):
    r_q = r_q-1
    c_q = c_q-1
    result = mark_all(n,r_q,c_q,obstacles)
    return result


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    r_qC_q = input().split()

    r_q = int(r_qC_q[0])

    c_q = int(r_qC_q[1])

    obstacles = []

    for _ in range(k):
        obstacles.append(list(map(int, input().rstrip().split())))

    result = queensAttack(n, k, r_q, c_q, obstacles)

    fptr.write(str(result) + '\n')

    fptr.close()

znaive.py

#!/bin/python3
# Spoiler of https://www.hackerrank.com/challenges/queens-attack-2/problem

import math
import os
import random
import re
import sys

EMPTY_W = chr(0x2591)
EMPTY_B = chr(0x2593)
QUEEN = chr(0x2655)
TARGT = chr(0x265F)
OBST = chr(0x265C)


def init_board(n,r_q,c_q,obstacles):
    board = []
    for r in range(n):
        row = []
        for c in range(n):
            if hit_obstacle(r,c,obstacles):
                square = OBST
            elif (c + r) % 2 == 0:
                square = EMPTY_B
            else:
                square = EMPTY_W
            row.append(square)
        board.append(row)
    board[r_q][c_q] = QUEEN
    return board

def print_board(board):
    n = len(board)
    print("")
    for r in range(n-1,-1,-1):
        for c in range(n):
            #print("[{},{}] = ".format(r,c), end =" " )
            square = board[r][c]
            print(square, end=" ")
        print("",end="\n\n")
    print("")

memo = {}
def hit_obstacle(r,c,obstacles):
    hit = memo.get((r,c))
    if hit == None:
        hit = False
        for obs in obstacles:
            if (obs[0]-1 == r) and (obs[1]-1 == c):
                hit = True
        memo[(r,c)] = hit    
    return hit

def mark_one(board,r,c,obstacles):
    if hit_obstacle(r,c,obstacles):
        return False    
    else:
        board[r][c] = TARGT
        return True

def mark_l(board,r_q,c_q,obstacles):
    for c in range(c_q-1,-1,-1):
        r = r_q
        if not mark_one(board,r,c,obstacles):
            break

def mark_r(board,r_q,c_q,obstacles):
    n = len(board)
    for c in range(c_q+1,n):
        r = r_q
        if not mark_one(board,r,c,obstacles):
            break

def mark_u(board,r_q,c_q,obstacles):
    n = len(board)
    for r in range(r_q+1,n):
        c = c_q
        if not mark_one(board,r,c,obstacles):
            break

def mark_d(board,r_q,c_q,obstacles):
    for r in range(r_q-1,-1,-1):
        c = c_q
        if not mark_one(board,r,c,obstacles):
            break

def mark_ul(board,r_q,c_q,obstacles):
    n = len(board)
    for d in range(1,n - r_q):
        r = r_q + d
        c = c_q - d
        if c < 0:
            break
        elif not mark_one(board,r,c,obstacles):
            break

def mark_ur(board,r_q,c_q,obstacles):
    n = len(board)
    for d in range(1,n - r_q):
        r = r_q + d
        c = c_q + d
        if c >= n:
            break
        elif not mark_one(board,r,c,obstacles):
            break

def mark_dl(board,r_q,c_q,obstacles):
    n = len(board)
    for d in range(1,r_q+1):
        r = r_q - d
        c = c_q - d
        if c < 0:
            break
        elif not mark_one(board,r,c,obstacles):
            break

def mark_dr(board,r_q,c_q,obstacles):
    n = len(board)
    for d in range(1, r_q+1):
        r = r_q - d
        c = c_q + d
        if c >= n:
            break
        elif not mark_one(board,r,c,obstacles):
            break

def mark_all(board,r_q,c_q,obstacles):
    mark_l(board,r_q,c_q,obstacles)
    mark_r(board,r_q,c_q,obstacles)
    mark_u(board,r_q,c_q,obstacles)
    mark_d(board,r_q,c_q,obstacles)
    mark_ul(board,r_q,c_q,obstacles)
    mark_ur(board,r_q,c_q,obstacles)
    mark_dl(board,r_q,c_q,obstacles)
    mark_dr(board,r_q,c_q,obstacles)

def sweep(board):
    n = len(board)
    x = 0
    print("")
    for r in range(n-1,-1,-1):
        for c in range(n):
            square = board[r][c]
            if (square == TARGT):
                x += 1
    return x



# Complete the queensAttack function below.
def queensAttack(n, k, r_q, c_q, obstacles):
    r_q = r_q-1
    c_q = c_q-1
    board = init_board(n,r_q,c_q,obstacles)
    mark_all(board,r_q,c_q,obstacles)
    result = sweep(board)
    print_board(board)
    return result


if __name__ == '__main__':

    # case 0
    ## n = 4
    ## k = 0
    ## r_q = 4
    ## c_q = 4
    ## obstacles = []

    # case 1
    n = 5
    k = 3
    r_q = 4
    c_q = 3
    obstacles = [[5,5], [4,2] , [2,3]]

    # case 2
    # n = 1
    # k = 0
    # r_q = 1
    # c_q = 1
    # obstacles = []

    # case 3
    # n = 100000
    # k = 0
    # r_q = 4187
    # c_q = 5068
    # obstacles = []

    result = queensAttack(n, k, r_q, c_q, obstacles)

    print(str(result) + '\n')