Bishop game - python

Question

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")

Answer 1

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))

Answer 2

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))