Python – Sums elements in a multidimensional array within a range

I’m creating a game where the robot traverses a map of a two-dimensional array. Each point in the two-dimensional array has a “treasure”, i.e. some coins. I want to be able to add all elements in up to 4 positions up, down, right, and left from the robot’s current position (making a “plus”). So, if we have an array:

a = [[1, 2, 3, 4]
      [5, 6, 7 ,8]
      [9, 10, 11, 12]
      [13, 14, 15, 16]

If the robot stands on a[0][0] (at position 1), the sum will return 1+2+3+4+5+9+13. If he stands on a[1][2] (7th place), it will return (7+3)+(8)+(5+6)+(11+ 15). But I want it to only return a maximum of 4 positions. Finally, I want to find the best position for the robot.

Here is my code :

def the_place_to_be(a):
    maximum = 0
    for i in range(len(a)):
        # Looping through columns
        for j in range(len(a[i])):
            # Looping through rows
            sum_at_ij = a[i][j]
            for x in range(i - max_steps_in_direction(a, i, "up"), i):
                sum_at_ij += a[x][j]

for x in range(j - max_steps_in_direction(a[i], j, "left"), j):
                sum_at_ij += a[i][x]

for x in range(i, i + max_steps_in_direction(a, i, "down")):
                sum_at_ij += a[x+1][j]

for x in range(j, j + max_steps_in_direction(a[i], j, "right")):
                sum_at_ij += a[i][x+1]

if sum_at_ij >= maximum:
                maximum = sum_at_ij
                coordinates = "(" + str(i) + ", " + str(j) + ")"
    return maximum, coordinates

def max_steps_in_direction(a, idx, direction):
    if direction == "up" or direction == "left":
        return min(idx, 4)
    elif direction == "down" or direction == "right":
        return min(len(a) - idx - 1, 4)

This can have the worst time complexity. I’m looking at the entire array and then looping through all the elements, up to four positions away from the coordinates where the robot is located, in the top, bottom, right and left directions.

At each step, I was calculating more than I had to calculate. Is there a way to mitigate this? I was thinking maybe my variable sum_at_ij could be saved. I’m basically going through each list in multiple lists. At each point in the list, I’m really just calculating some values that differ from the previous one. So, again suppose I’m at coordinates a[2][2] or coordinate 11, and when I move to a[2][3] or coordinates 12, the difference is:

sum_at_22: 11 + 7 + 3 + 15 + 12 + 10 + 9

sum_at_23: 12 + 8 + 4 + 16 + 11 + 10 + 9

I’m calculating a total of 3 new values (different top and bottom). If this is an 8×8 matrix, the new values will be the highest, lowest, and one new value on the right and one less value on the left. If I saved each value (probably in some hashmap), then maybe I can find some formula. Honestly, I don’t know. Maybe it’s a math.stackexchange problem.

Any ideas to save (yes, it doesn’t matter) compute time for memory overhead?

What you do during the summation process is actually convolution with the +shaped filter. If you replace the explicit loop with a >convolve2d With a single call, you can get faster scipy functions, which will do all the necessary loops for you, but not in python, but in C:

import numpy as np
from scipy.signal import convolve2d

# Your original array:
a = np.asarray([[1, 2, 3, 4],
                [5, 6, 7 ,8],
                [9, 10, 11, 12],
                [13, 14, 15, 16]])

# Building a filter that is essentially a + with arms of length 4
mask = np.zeros((2*4+1, 2*4+1))
mask[4, :] = 1
mask[:, 4] = 1

# Apply that filter to your array
sums = convolve2d(a, mask, mode="same")

# Find the maximum and its position in the sums array:
np.max(sums), np.unravel_index(np.argmax(sums), sums.shape)

Finally, sums is an array that gives the value of the summation procedure for each position in the original array. You just need to find the maximum value and its location.

While the complexity may not be better than your solution, it will still be much faster because the python loop is very slow, and many of the mechanisms in numpy and scipy are written in C/Fortran, which speeds up calculations

Comparing your solution to this solution on a 100×100 array provides an approximately 100x speedup factor. 40 on my machine (78.7ms vs. 2.06ms).