-
Notifications
You must be signed in to change notification settings - Fork 3
/
68_Google_Find_Attacking_Bishops.py
executable file
·89 lines (66 loc) · 2.82 KB
/
68_Google_Find_Attacking_Bishops.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
"""
This problem was asked by Google.
On our special chessboard, two bishops attack each other if they share the same diagonal.
This includes bishops that have another bishop located between them, i.e. bishops can attack through pieces.
You are given N bishops, represented as (row, column) tuples on a M by M chessboard.
Write a function to count the number of pairs of bishops that attack each other.
The ordering of the pair doesn't matter: (1, 2) is considered the same as (2, 1).
For example, given M = 5 and the list of bishops:
(0, 0)
(1, 2)
(2, 2)
(4, 0)
The board would look like this:
[b 0 0 0 0]
[0 0 b 0 0]
[0 0 b 0 0]
[0 0 0 0 0]
[b 0 0 0 0]
You should return 2, since bishops 1 and 3 attack each other, as well as bishops 3 and 4.
"""
memo_attacking_pair = {}
#diag_moves->row_iter, col_iter
moves = [
(-1, -1),
(-1, +1),
(+1, -1),
(+1, +1)
]
def find_attacking_bishops(start_row, start_col, board):
global memo_attacking_pair, moves
size_of_board = len(board)
def helper(row, col, move, attackers=0):
# if out of bounds of the board return number of attackers found up till now
if row < 0 or col<0 or row == size_of_board or col == size_of_board:
return attackers
# if a bishop is found increment num of attackers by 1
if board[row][col] == 'b':
# check if we've seen this pair before
if (row, col) in memo_attacking_pair and memo_attacking_pair[(row, col)] == (start_row, start_col):
pass
else:
attackers = +1
# store attacking pairs so that next time we dont count it
memo_attacking_pair[(start_row, start_col)] = (row, col)
return helper(row+move[0], col+move[1], move, attackers)
num_attackers = 0
for row_iter, col_iter in moves:
# check if this diagonal has already been visited
num_attackers += helper(start_row+row_iter, start_col+col_iter, move=(row_iter, col_iter))
return num_attackers
def create_board(size_of_board, bishop_positions):
board = [[0 for _ in range(size_of_board)] for _ in range(size_of_board)]
for row,col in bishop_positions:
board[row][col] = 'b'
return board
def num_attacking_bishops(M, list_of_bishops):
# create board
board = create_board(M, list_of_bishops) # don't really need the board, added just for debugging
num_of_attacking_bishops = 0
# loop over all the positions in list
for row, col in list_of_bishops:
num_of_attacking_bishops += find_attacking_bishops(start_row=row, start_col=col, board=board)
return num_of_attacking_bishops
if __name__ == '__main__':
print(num_attacking_bishops(5, [(0, 0), (1, 2), (2, 2), (4, 0)])) # ans = 2
print(num_attacking_bishops(5,[(0, 0), (1, 2), (2, 2)])) # ans =1