trjhtr

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.

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.