Bishop game - python

A bishop can capture any other bishop if it lies along the same diagonal line, so long as no other bishop is in its path. Given a list of coordinates of the bishops locations, and a board size, determine how many bishops are unsafe.

This code has a time complexity of $$\O(N*K)\$$ where N is the number of bishops, K is (N- current index).

Is there a way to improve this?

bishops = [(0, 0),
(1, 1),
(0, 2),
(1, 3),
(2, 0),
(2, 2)]
size = 5

moves = [(1, 1), (1, -1), (-1, 1), (-1, -1)]

captured = []
for index, coordinates in enumerate(bishops):
remaining = bishops[index + 1:]
seen = bishops[:index + 1]
for dx, dy in moves:
x, y = coordinates
while 0 <= x + dx < size and 0 <= y + dy < size:
x += dx
y += dy
if (x, y) in seen:
break
if (x, y) in remaining:
remaining.remove((x, y))
capture = f"{coordinates} takes {x, y}"
captured.append(capture)
break

print(f"There are {len(captured)} moves")
print(*captured, sep = "\n")



If bishop X, Y & Z are all on a diagonal, X can capture Y, Y can capture both X & Z, and Z can capture Y. All 3 are unsafe. If the problem has no requirement to determine exactly which bishop captures which bishops -- just determine the number which could be captured -- then you don't need to move each bishop along the each of the four dx, dy in moves directions until it encounters another bishop. That is just mechanical busy work.

A bishop X is unsafe if any other bishop Y satisfies either (or both) of the following:

• bishop[X][0] + bishop[X][1] == bishop[Y][0] + bishop[Y][1], or
• bishop[X][0] - bishop[X][1] == bishop[Y][0] - bishop[Y][1].

You can partition the bishops according to diagonals. If two or more bishops are on the same diagonal, all of those bishops are unsafe.

Note that the size of the board is unnecessary.

The following is a review of and improvement upon @RootTwo's answer.

A vanilla dictionary is a poor choice for nwse and nesw. That requires you check if the diagonal index has already been created in the dictionary, to determine whether to store a new list in the dictionary, or to appended to the existing list. A better option is to use defaultdict, which automatically creates the entry using the provided default if that entry is not present:

from collections import defaultdict

nwse = defaultdict(list)
nesw = defaultdict(list)


The bishops is already a collection of tuple coordinates. Creating your own tuples in = [(row,col)] and .append((row,col)) is creating new objects identical to the existing ones in everything except identity. There is no need to pollute the memory with these new tuples; just reuse the existing ones:

for bishop in bishops:
row, col = bishop
nwse[row + col].append(bishop)
nesw[row - col].append(bishop)


The for k,v in nwse.items(): loop never uses the dictionary key value (k) in the body of the loop. It makes no sense to extract it from the dictionary. Just loop over the values() of the dictionaries:

in_danger = set()

for v in nwse.values():
if len(v) > 1:
in_danger.update(v)

for v in nesw.values():
if len(v) > 1:
in_danger.update(v)


The problem asks for "how many bishops are unsafe", not the number that are safe. So the output should be:

print(len(in_danger))


Finally, follow the PEP-8 standards. Specifically, you need a space after all of your commas.

from collections import defaultdict

bishops = [(0, 0),
(1, 1),
(0, 2),
(1, 3),
(2, 0),
(2, 2)]

nwse = defaultdict(list)
nesw = defaultdict(list)

for bishop in bishops:
row, col = bishop
nwse[row + col].append(bishop)
nesw[row - col].append(bishop)

in_danger = set()

for v in nwse.values():
if len(v) > 1:
in_danger.update(v)

for v in nesw.values():
if len(v) > 1:
in_danger.update(v)

print(len(in_danger))


O(n)

You can transform the (row,column) coordinate of a bishop to a (row+column, row-column) coordinate. The row+column coordinate tells you which upper-left to lower right diagonal the bishop is on. The row-column coordinate tells you which upper-right to lower-left diagonal the bishop is on.

      row + col                     row - col
7  8  9 10 11 12 13 14       7  6  5  4  3  2  1  0
6  7  8  9 10 11 12 13       6  5  4  3  2  1  0 -1
5  6  7  8  9 10 11 12       5  4  3  2  1  0 -1 -2
4  5  6  7  8  9 10 11       4  3  2  1  0 -1 -2 -3
3  4  5  6  7  8  9 10       3  2  1  0 -1 -2 -3 -4
2  3  4  5  6  7  8  9       2  1  0 -1 -2 -3 -4 -5
1  2  3  4  5  6  7  8       1  0 -1 -2 -3 -4 -5 -6
0  1  2  3  4  5  6  7       0 -1 -2 -3 -4 -5 -6 -7


Now create two dictionaries. One that maps each row+col value to a list of bishops on that diagonal. The other one similarly maps the row-col value. Any dict entry with more than one bishop, means all of those bishops are in danger.

bishops = [(0, 0),
(1, 1),
(0, 2),
(1, 3),
(2, 0),
(2, 2)]

nwse = {}
nesw = {}

for row,col in bishops:
nwse_index = row + col
if nwse_index not in nwse:
nwse[nwse_index] = [(row,col)]
else:
nwse[nwse_index].append((row,col))

nesw_index = row - col
if nesw_index not in nesw:
nesw[nesw_index] = [(row,col)]
else:
nesw[nesw_index].append((row,col))

in_danger = set()

for k,v in nwse.items():
if len(v) > 1:
in_danger.update(v)

for k,v in nesw.items():
if len(v) > 1:
in_danger.update(v)

safe_bishops = set(bishops) - in_danger

print(len(safe_bishops))


Improved code

based on AJNeuman's answer and my comment below.

The row - col index is offset by adding -8 so that all the values will be < 0. The row + col index are all > 0. So just one dict is needed.

from collections import defaultdict

bishops = [(0, 0),
(1, 1),
(0, 2),
(1, 3),
(2, 0),
(2, 2)]

occupied_diagonals = defaultdict(list)

for bishop in bishops:
row, col = bishop
occupied_diagonals[row + col].append(bishop)
occupied_diagonals[row - col - 8].append(bishop)

in_danger = set()

for bishop_list in occupied_diagonals.values():
if len(bishop_list) > 1:
in_danger.update(bishop_list)

print(len(in_danger))

• A nice answer (+1), but it could use improvement. – AJNeufeld Jul 12 '19 at 21:34
• @AJNeufeld, yes, lots of room for improvement. I don't know the skill level of OP and wanted to explain it simply without a lot of things that might be new. It could use a defaultdict. And if you offset one of the "diagonal" indexes (e.g add -8 to the row-column) so the numbers don't overlap, it would only need one dict. That would cut the code in half. – RootTwo Jul 12 '19 at 21:54
• While I like the reduction in code, I dislike the magic number -8. The code will no longer work for larger (or infinite) boards. You could fix this by subtracting max(row)+1. Alternately, you could turn the indices into strings f"/{row+col}" and fr"\{row-col}", adding a leading / for indices on one diagonal, and \ for the other. Or you could multiply the indices by 2, and then add 1 to partition by even/odd: (row+col)*2 & (row-col)*2+1. Or, you could partition by int/str with row+col and str(row-col) or by int/float by adding +0.5, depending on how hacky you want to be. – AJNeufeld Jul 14 '19 at 16:10