Find all integral coordinates given top left corner and bottom right corner of a rectangle

Question

Here is the problem I am working on -

There is an \$N \times N\$ field on which missiles are being bombarded. Initially, all the cells in this field have the value \$0\$. There will be \$M\$ missiles bombarded on this field. The \$i\$th missile will have power \$P_i\$ and it will affect all the cells in region with \$(A_i,B_i)\$ as top-left corner and \$(C_i,D_i)\$ as bottom-right corner. Because of missile, value of all the cells in this rectangle will get XORed with \$P_i\$.

After all the missiles have been bombarded, you have to find out values in each cell of this field.

Here is what I have tried -

N = 3
M = 3
missiles = [[3,3,1,3,2],
[2,2,1,2,2],
[3,1,1,2,3]]

from itertools import product
# Logic
coords = {}
for i in missiles:
    Pi, Ai, Bi, Ci, Di = i
    for j in product(*[range(Ai-1, Ci), range(Bi-1, Di)]):
        if coords.get(j):
            coords[j] ^= Pi
            #[NxN[i[0]][i[1]] ^= Pi
        else:
            coords[j] = 0 ^ Pi

def print_grid(coords, N):
    count = 0
    for i in product(*[range(N), range(N)]):
        if i in coords:
            print(coords[i], "",end="")
        else:
            print(0, "",end="")
        count+=1
        if count%N==0:
            print()

print_grid(coords, N)

Output -

3 3 3 
1 1 3 
3 3 0 

Exactly does what I want, but I was wondering is there a way to optimize it for large inputs. Any help appreciated.

Answer 1

Since you commented that using numpy is OK for you, you can simplify the whole rectangle computation using its advanced slicing capabilities:

>>> # Let's define a square array
... 
>>> a = np.array(range(25)).reshape((5, 5))
>>> a
array([[ 0,  1,  2,  3,  4],
       [ 5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14],
       [15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24]])
>>> # Advanced slicing allow us to extract blocks at once
... 
>>> a[2:5, 1:3]
array([[11, 12],
       [16, 17],
       [21, 22]])

You just need to encapsulate this behaviour in a class for ease of use:

import numpy as np


class BattleField:
    def __init__(self, size):
        self.field = np.zeros((size, size), dtype=int)

    def receive_missile(self, power, top, left, bottom, right):
        self.field[top-1:bottom, left-1:right] ^= power

    def __str__(self):
        return str(self.field)


if __name__ == '__main__':
    missiles = [
        [3,3,1,3,2],
        [2,2,1,2,2],
        [3,1,1,2,3],
    ]
    field = BattleField(3)
    for missile in missiles:
        field.receive_missile(*missile)
    print(field)

---

Other points to improve from your code includes:

• using more descriptive names than A, B, or C;
• using functions instead of code at top-level for ease of testing/reuse;
• using the if __name__ == '__main__' guard to avoid running some code when importing the file;
• using direct parameters values instead of packing them in a list and unpacking them in the function call (product(*[range(N), range(N)]) => product(range(N), range(N)));
• using dict.get with its default value (coords[j] = coords.get(j, 0) ^ Pi) to simplify the code.