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

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][i] ^= 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.

• (Welcome to CR!) (I don't post without the help of a spelling checker.) How would you design based on symbolic execution of effects? Can the solution be produced by a systolic array or more than one thread? Can a symbolic representation of N x N be found and presented strictly faster than in N x N steps? – greybeard Mar 19 '18 at 8:32
• @greybeard multithreading might be a good option. I, however want to question my logic, whether it is the most optimized logic, not concerned about the implementation right now. – Vivek Kalyanarangan Mar 19 '18 at 8:41
• Is an approach using numpy any good for you? – Mathias Ettinger Mar 19 '18 at 9:06
• @MathiasEttinger yes very much. So lets say I make an np.array() out of the coordinate indices and find a way to multiply Pi directly with the original np.zeros((N,N)) that would help. The bottleneck for me seems to be the way I am generating all the points in the rectangle given Ai, Bi, Ci, Di – Vivek Kalyanarangan Mar 19 '18 at 9:09

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:

• using more descriptive names than A, B, or C;
• 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.
• Thanks @MathiasEttinger this is elegant. I timed it against mine - 10.6 µs ± 3.01 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each) # for mine and 31.3 µs ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) on yours. You think this is because of the overhead of loading numpy in such a small example? – Vivek Kalyanarangan Mar 19 '18 at 9:44