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\$
4
  • \$\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, 2018 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\$ Mar 19, 2018 at 8:41
  • \$\begingroup\$ Is an approach using numpy any good for you? \$\endgroup\$ Mar 19, 2018 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\$ Mar 19, 2018 at 9:09

1 Answer 1

9
\$\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\$
3
  • \$\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\$ Mar 19, 2018 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\$ Mar 19, 2018 at 9:45
  • \$\begingroup\$ Cool that works. This definitely gives me a lot to think about. Glad to accept! :-) \$\endgroup\$ Mar 19, 2018 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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