6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ (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? \$\endgroup\$ – greybeard Mar 19 '18 at 8:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Vivek Kalyanarangan Mar 19 '18 at 8:41
  • \$\begingroup\$ Is an approach using numpy any good for you? \$\endgroup\$ – Mathias Ettinger Mar 19 '18 at 9:06
  • \$\begingroup\$ @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 \$\endgroup\$ – Vivek Kalyanarangan Mar 19 '18 at 9:09
10
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Vivek Kalyanarangan Mar 19 '18 at 9:44
  • 1
    \$\begingroup\$ @VivekKalyanarangan If you time the whole script, that's possible. You can make a function out of the testing code and only time the function, to figure it out. \$\endgroup\$ – Mathias Ettinger Mar 19 '18 at 9:45
  • \$\begingroup\$ Cool that works. This definitely gives me a lot to think about. Glad to accept! :-) \$\endgroup\$ – Vivek Kalyanarangan Mar 19 '18 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.