Skip to content

Instantly share code, notes, and snippets.

@faermanj
Last active December 8, 2020 15:09
Show Gist options
  • Save faermanj/87efa2246eb4a2c5a5fa145fb8b9aa3a to your computer and use it in GitHub Desktop.
Save faermanj/87efa2246eb4a2c5a5fa145fb8b9aa3a to your computer and use it in GitHub Desktop.
Hacker Rank: Queens II
#!/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()
#!/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')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment