# [SOLVED] Finding the optimal location in 2D array

## Issue

I’m working with 2D numpy arrays of equal size in terms of the number of rows and columns. I would like to find the optimal location where 2n + 1 on each side would result in highest possible sum. 2(n) + 1 here means the the neghbouring elements.

So the 2D array:

``````[[0 0 0 0 0]
[0 1 1 1 0]
[0 1 1 1 0]
[0 1 1 1 0]
[0 0 0 0 0]]
``````

In this array, the element at (2, 2) appears to be the optimal location at 2(1) + 1.
So, at, `n = 2` the ideal location would be same. However, at `n = 3`, it would be `none`, because that would exceed the 2D array matices.

This is my approach to the problem, which is not giving the desired output.

``````def find_target_location(arr, area):
sum_1 = 0
sum_2 = sum_1
square_area = (2 * area) + 1

if square_area > len(arr):
return None

for row in range(len(arr)):
for index in range(len(arr[row])):
area_forward = arr[row: square_area + row, index: square_area + index]
# This is where I am doing wrong but cannot figure out.
area_previous = arr[row - len(arr): -row -1, row - len(arr), -index -1]

sum_area_forward = sum(sum(area_forward))
sum_area_backward = sum(sum(area_backward))
sum_2 = sum_area_forward + sum_area_backward
if sum_2 > sum_1:
sum_1 = sum_2
optimal_location = (row, index)
return optimal_location
``````

## Sum of immediate neighbors

If you’re looking for the index of the element with the largest sum of immediately adjacent neighbor values:

``````from numpy.lib.stride_tricks import sliding_window_view as windows

np.unravel_index(np.pad(windows(x, (3, 3)).sum(axis=(2, 3)), 1).argmax(), x.shape)
``````

Note however that this solution counts the value of an element itself when calculating the sum of its neighboring values.

## Sum of neighbors in `2n+1` square neighborhood

So you want to sum all neighbors in a `2n+1` "radius" neighborhood:

``````n = 1

# x = np.array(...)

``````

I’ve only sort of tested this, but I think it should work. Note here that the first index of the max value will be chosen, so if you have more than one "optimal" location, you’ll always end up with the "first" one that occurs (when searching from top-left to bottom-right).

I don’t think padding is strictly necessary but it does let you avoid having to do some tedious arithmetic, and also helps if you want to not count the value of each cell when summing the neighboring values, like so:

``````padded -= x

optimal_location # = same as above
``````

## How to do it without `stride_tricks`

At the end of the day, `np.lib.stride_tricks.sliding_window_view` is just clever indexing.

Let `x` be this `(5, 5)` array:

``````array([[0, 0, 0, 0, 0],
[0, 1, 2, 3, 0],
[0, 4, 5, 6, 0],
[0, 7, 8, 9, 0],
[0, 0, 0, 0, 0]])
``````

And suppose `n = 1`, so the area of your neighborhood is `2n+1 = 3`. Now imagine placing a `(3, 3)` "window" over `x`, matching the top-left corner of the window with the top-left corner of `x`. That "window" is surrounding the values

``````0 0 0
0 1 2
0 4 5
``````

What are the column indices of those values? They are `(0, 1, 2)`.

Now, if we’re sliding a `(3, 3)` window across `x`, we can’t move the window such that it hangs over any side of `x`. So the furthest right we could move this window across the top of `x` would be such that the top-left corner of the window is at index 2. That way, the top-right corner of the window lines up with the top-right corner of `x`. That window is now surrounding the values

``````0 0 0
2 3 0
5 6 0
``````

What are the column indices of those values? They are `(2, 3, 4)`.

Let’s create a list of tuples which can represent the columns selected as we slide across the top of `x`:

``````n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))
``````

Output:

``````>>> idxs
[(0, 1, 2), (1, 2, 3), (2, 3, 4)]
``````

Since `x` is square, these column indexes will also work for the rows for when we want to slide the window down one row (imagine sliding the window across `x` the same way you read a page of a book written in English — left to right, top to bottom).

If you take the Cartesian product of `idxs`, this will give you the row and column indices of all 9 windows:

``````>>> [(rows, cols) for rows in idxs for cols in idxs]
[((0, 1, 2), (0, 1, 2)),
((0, 1, 2), (1, 2, 3)),
((0, 1, 2), (2, 3, 4)),
((1, 2, 3), (0, 1, 2)),
((1, 2, 3), (1, 2, 3)),
((1, 2, 3), (2, 3, 4)),
((2, 3, 4), (0, 1, 2)),
((2, 3, 4), (1, 2, 3)),
((2, 3, 4), (2, 3, 4))]
``````

Now, one last thing: for each tuple of `(rows, cols)`, we need to take the Cartesian product again to get all 9 index pairs for each `(3, 3)` window. For instance, the 9 indices of the `(3, 3)` window anchored at the top left of `x` where we start are

``````[[(0, 0), (0, 1), (0, 2)],
[(1, 0), (1, 1), (1, 2)],
[(2, 0), (2, 1), (2, 2)]]
``````

Using those tuples to index into `x`:

``````>>> [[x[i, j] for i in (0, 1, 2)] for j in (0, 1, 2)]
[[0, 0, 0],
[0, 1, 4],
[0, 2, 5]]
``````

Now we could wrap the above in another two nested list comprehensions to iterate over the `(rows, cols)` tuples:

``````>>> np.array([[[[x[i, j] for j in cols] for i in rows] for cols in idxs] for rows in idxs])
array([[[[0, 0, 0],
[0, 1, 2],
[0, 4, 5]],

[[0, 0, 0],
[1, 2, 3],
[4, 5, 6]],

[[0, 0, 0],
[2, 3, 0],
[5, 6, 0]]],

[[[0, 1, 2],
[0, 4, 5],
[0, 7, 8]],

[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]],

[[2, 3, 0],
[5, 6, 0],
[8, 9, 0]]],

[[[0, 4, 5],
[0, 7, 8],
[0, 0, 0]],

[[4, 5, 6],
[7, 8, 9],
[0, 0, 0]],

[[5, 6, 0],
[8, 9, 0],
[0, 0, 0]]]])
``````

This produces the `(3, 3, 3, 3)` array over which you can then sum the last two axes.

But that comprehension is awful. Fortunately, the `np.ix_()` function makes it incredibly easy to get these Cartesian products in a form suitable for advanced indexing:

``````>>> np.ix_((0, 1, 2), (0, 1, 2))
(array([,
,
]),
array([[0, 1, 2]]))
``````

Now getting our windows is much easier (together with the setup data):

``````n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))

# all (3, 3) windows of x
np.array([[x[np.ix_(rows, cols)] for cols in idxs] for rows in idxs])
``````

Which produces the same result as above. From there, you can apply the sum over the last two axes (the rows and columns of each individual 2D array).

Of course, that’s still an awful looking comprehension… and `np.lib.stride_tricks.sliding_window_view` abstracts away all that indexing nonsense.