How to get a value in a nested list that is smaller than the ones around it

Question

So basically I have to find the smallest number in a nested list as compared to the numbers around it. This would be called a 'sink' and the function returns True if it is a sink and False if it isn't. For example, if the nested list is

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

then the number at [0,2], (1), should be true as all the values adjacent to it are smaller than 1 but the number at [2, 0], (7), shouldn't be true as it is greater than some of the values around it.

I tried to use slicing to get the numbers beside it but I don't know how to slice it to get the number diagonal from the sink or above or below. This is some of the code that I tried to do:

for x in elevation_map:
    for xs in x:
        if elevation_map[cell[0]][cell[1]] < xs[cell[0]]:
            return True
return False

Welcome to Stack Overflow! Check out the [tour]. Please add the full expected output for that input. You can [edit] the question. I guess it would be `[[True, False, True], [False, False, False], [False, False, False]]`. See [ask] and [mre] if you want more advice. — wjandrea, Nov 11 '19 at 16:47
What are you counting as "adjacent" - the four orthogonal directions, or eight directions including diagonals? — kaya3, Nov 11 '19 at 16:51
This might be useful? [Calculate number of equal neighbouring cells within a numpy array](https://stackoverflow.com/q/36367531/4518341) — wjandrea, Nov 11 '19 at 16:54

score 1 · Answer 1 · answered Nov 11 '19 at 17:25

You could convert your list of lists to a numpy array, iterate the indices, and use two-dimensional slicing to get the sub-matrix and check whether the value at the current position is the minimal value.

>>> import numpy as np
>>> from itertools import product
>>> m = np.array([[1, 2, 1],
...               [4, 6, 5],
...               [7, 8, 9]])
...
>>> [(r, c, m[r,c]) for r,c in product(*map(range, m.shape))
...                 if m[r,c] == m[max(0,r-1):r+2,max(0,c-1):c+2].min()]
...       
[(0, 0, 1), (0, 2, 1)]

(The max(0, ...) is so that the lower bound 0-1 does not refer to the last element in the array; if the upper bound is higher then the size of the array, that's not a problem.)

Note: This will also identify a point as a "sink" if one of it's neighbors has the same value; not sure if this is a problem.

Thanks for the help, but we haven't learned that and therefore I can't use it but thanks anyway :) — lankup90, Nov 14 '19 at 17:21

wwii · Answer 2 · 2019-11-11T17:29:22.040

don't know how to slice it to get the number diagonal from the sink or above or below.

Your question shows an indexing scheme of [row,col].

Diagonals:

[row-1,col-1], [row-1,col+1], [row+1,col-1], [row+1,col+1]

left, right, up down:

[row,col-1],[row,col+1],[row-1,col],[row+1,col]

[row-1,col-1] [row-1, col ] [row-1,col+1]
[ row ,col-1] [ row , col ] [ row ,col+1]
[row+1,col-1] [row+1, col ] [row+1,col+1]

When calculating the indices you will need to include checks to see if you are at the edge of the 2-d structure. If you are at the left edge then col-1 will rap around to the last item in that row and if you are at the top edge then row-1 will rap around to the last item in that column. You also might want to check for the right and bottom edge - there won't be any cells at col+1 or row+1.

That `row-1` and `col-1` part could go wrong if `row` or `col` is `0`. — tobias_k, Nov 11 '19 at 17:15

score 0 · Answer 3 · answered Apr 03 '20 at 13:29

If you consider a value a sink if it is the minimum of the surrounding 3x3 grid, i.e. you don't require that it is strictly smaller than any other value around it, then you can use numpy.lib.stride_tricks.as_strided in order to create a window that checks the 3x3 neighbors. In order to work at the edges of the matrix, the original array can be padded with np.inf (since min is later used):

import numpy as np

matrix = np.array(
[[1, 2, 1],
 [4, 6, 5],
 [7, 8, 9]])

padded = np.pad(matrix.astype(float), 1, constant_values=np.inf)
window = np.lib.stride_tricks.as_strided(
    padded,
    padded.shape + (3, 3),
    padded.strides * 2)[:-2, :-2]

result = matrix == window.min(axis=(-2, -1))

Which gives the following result:

[[ True False  True]
 [False False False]
 [False False False]]

How to get a value in a nested list that is smaller than the ones around it

3 Answers3