Determining neighbours of cell two dimensional list

Question

I have a list of lists, something like

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

Represented graphically as:

1 2 3
4 5 6
7 8 9

I'm looking for an elegant approach to check the value of neighbours of a cell, horizontally, vertically and diagonally. For instance, the neighbours of [0][2] are [0][1], [1][1] and [1][2] or the numbers 2, 5, 6.

Now I realise, I could just do a bruteforce attack checking every value a la:

[i-1][j]
[i][j-1]
[i-1][j-1]
[i+1][j]
[i][j+1]
[i+1][j+1]
[i+1][j-1]
[i-1][j+1]

But thats easy, and I figured I can learn more by seeing some more elegant approaches.

Drucilla

Do you want to get the indices or the values? And do you want a function that can do random access on every index or a function that returns a list of (val, neighbors_of_val) pairs? -- Just getting the indices is too simple for a elegant solution, but what you really want to do might be more interesting – Invercargill

Either or - I deliberately left this question fairly general so people wouldn't feel constrained. – Drucilla

Answer 1

# Size of "board"
X = 10
Y = 10

neighbors = lambda x, y : [(x2, y2) for x2 in range(x-1, x+2)
                               for y2 in range(y-1, y+2)
                               if (-1 < x <= X and
                                   -1 < y <= Y and
                                   (x != x2 or y != y2) and
                                   (0 <= x2 <= X) and
                                   (0 <= y2 <= Y))]

>>> print(neighbors(5, 5))
[(4, 4), (4, 5), (4, 6), (5, 4), (5, 6), (6, 4), (6, 5), (6, 6)]

I don't know if this is considered clean, but this one-liner gives you all neighbors by iterating over them and discarding any edge cases.

Lynnette

What if the "board" is 10201x10201? – Firstling

@CF84: Then the constants X and Y would need to have different values assigned to them. Do you have an issue regarding this—what's your point? – Marshall

@CDspace how does the edit deviate from the original intent of the post? If you mean the one-liner, it can still be written on one line with a normal function. Also, it hasn't been a one-liner anyway since the previous edit. At least the uppercase X and Y variables should be changed, since they are hard to spot. – Zambia

Why doesn't print(neighbors(10, 9)) return empty set, when I am giving a value out of range? – Burkey

I think the conditions are wrong. they should be (-1 < x <X) and (-1 < y < Y) and 0 <= x2 <X) and (0 <= y2 < Y). Note omitting = in front of array size X and Y. – Seabee

Answer 2

Assuming you have a square matrix:

from itertools import product

size = 3

def neighbours(cell):
    for c in product(*(range(n-1, n+2) for n in cell)):
        if c != cell and all(0 <= n < size for n in c):
            yield c

Using itertools.product and thanks to Python's yield expression and star operator, the function is pretty dry but still readable enough.

Given a matrix size of 3, you can then (if needed) collect the neighbours in a list:

>>> list(neighbours((2,2)))
[(1, 1), (1, 2), (2, 1)]

What the function does can be visualized as follows:

Contrecoup

hi, this looks great. But what about an matrix with unequal row and col numbers, like 2*4 array? – Corse

@Corse having the matrix width and height as a tuple, e.g. size = [3, 4] you can check whether c[0] and c[1] are larger than (or equal to) zero and smaller than size[0] and size[1] respectively. E.g. 0 <= i < bound for i, bound in zip(c, size). – Contrecoup

Answer 3

mb...

from itertools import product, starmap

x, y = (8, 13)
cells = starmap(lambda a,b: (x+a, y+b), product((0,-1,+1), (0,-1,+1)))

// [(8, 12), (8, 14), (7, 13), (7, 12), (7, 14), (9, 13), (9, 12), (9, 14)]
print(list(cells)[1:])

Ayakoayala

I don't understand this answer, and I ran it along with the question's example in Python 2.7. – Putative

How would you add a check to make sure the coordinates don't exceed the bounds of the matrix? – Fez

Answer 4

for x_ in range(max(0,x-1),min(height,x+2)):
  for y_ in range(max(0,y-1),min(width,y+2)):
    if (x,y)==(x_,y_): continue
    # do stuff with the neighbours

>>> a=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> width=height=3
>>> x,y=0,2
>>> for x_ in range(max(0,x-1),min(height,x+2)):
...   for y_ in range(max(0,y-1),min(width,y+2)):
...     if (x,y)==(x_,y_): continue
...     print a[x_][y_]
... 
2
5
6

Procedure

Answer 5

If someone is curious about alternative way to pick direct (non-diagonal) neighbors, here you go:

neighbors = [(x+a[0], y+a[1]) for a in 
                    [(-1,0), (1,0), (0,-1), (0,1)] 
                    if ( (0 <= x+a[0] < w) and (0 <= y+a[1] < h))]

Respiration

Answer 6

There's no cleaner way to do this. If you really want you could create a function:

def top(matrix, x, y):
     try:
         return matrix[x][y - 1];
     except IndexError:
         return None

Darell

@ Kaizer.se: Thanks, wasn't sure which one it was and too lazy to look it up or try it. – Katekatee

+1 this is not a complete solution, but interesting since that could be quite a Pythonic way to search for neighbors -- it's EAFP – Koine

This actually won't work. I was doing a similar solution and realized this. Negative indexes actually used for looking up the index in reverse order. For example -1 means the last element. – Heterophony

Answer 7

Here is your list:

(x - 1, y - 1) (x, y - 1) (x + 1, y - 1)
(x - 1, y)     (x, y)     (x + 1, y)
(x - 1, y + 1) (x, y + 1) (x + 1, y + 1)

So the horizontal neighbors of (x, y) are (x +/- 1, y).

The vertical neighbors are (x, y +/- 1).

Diagonal neighbors are (x +/- 1, y +/- 1).

These rules apply for an infinite matrix. To make sure the neighbors fit into a finite matrix, if the initial (x, y) is at the edge, just apply one more restriction to the coordinates of neighbors - the matrix size.

Ehr

Answer 8

>>> import itertools
>>> def sl(lst, i, j):
    il, iu = max(0, i-1), min(len(lst)-1, i+1)
    jl, ju = max(0, j-1), min(len(lst[0])-1, j+1)
    return (il, iu), (jl, ju)

>>> lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> tup = 0, 2
>>> [lst[i][j] for i, j in itertools.product(*sl(lst, *tup)) if (i, j) != tup]
[2, 5, 6]

I don't know how elegant it seems to you, but it seems to work w/o any hard-coding.

Dinkins

Answer 9

This generates all indices:

def neighboring( array ):
    nn,mm = len(array), len(array[0])
    offset = (0,-1,1) # 0 first so the current cell is the first in the gen
    indices = ( (i,j) for i in range(nn) for j in range(mm) )
    for i,j in indices:
        all_neigh =  ( (i+x,j+y) for x in offset for y in offset )
        valid = ( (i,j) for i,j in all_neigh if (0<=i<nn) and (0<=j<mm) ) # -1 is a valid index in normal lists, but not here so throw it out
        yield valid.next(), valid ## first is the current cell, next are the neightbors

for (x,y), neigh in neighboring( l ):
    print l[x][y], [l[x][y] for x,y in neigh]

Invercargill

Answer 10

Thank you to @JS_is_bad for a great hint about the neighbors. Here is the running code for this problem:

    def findNeighbours(l,elem):
    #This try is for escaping from unbound error that happens 
    #when we try to iterate through indices that are not in array
    try:
        #Iterate through each item of multidimensional array using enumerate
        for row,i in enumerate(l):
            try:
                #Identifying the column index of the givem element
                column=i.index(elem)
            except ValueError:
                continue
            x,y=row,column
    
    #    hn=list(((x,y+1),(x,y-1))) #horizontal neighbours=(x,y+/-1)
    #    vn=list(((x+1,y),(x-1,y))) #vertical neighbours=(x+/-1,y)
    #    dn=list(((x+1,y+1),(x-1,y-1),(x+1,y-1),(x-1,y+1))) #diagonal neighbours=(x+/-1,y+/-1)
        #Creating a list with values that are actual neighbors for the extracted index of array
        neighbours=[(x,y+1),(x,y-1),(x+1,y),(x-1,y),(x+1,y+1),(x-1,y-1),(x+1,y-1),(x-1,y+1)]
        #Creating a universe of indices from given array
        index_list=[(i,j) for i in range(len(l)) for j in range(len(l[i]))]
        #Looping through index_list and nested loop for neighbours but filter for matched ones
        # and extract the value of respective index
        return_values=[l[index[0]][index[1]] for index in index_list for neighbour in neighbours if index==neighbour]
        return return_values,neighbours
    except UnboundLocalError:
        return []

Halakah

Answer 11

If lambdas daunt you here you are .But lambdas make your code look clean.@johniek_comp has a very clean solution TBH

k,l=(2,3)
x = (0,-1,+1)
y = (0,-1,+1)
cell_u = ((k+a,l+b) for a in x for b in y)
print(list(cell_u))

Bona

Answer 12

Inspired by one of the previous answers.

You can use min() and max() functions to shorten the calculations:

width = 3
height = 3

[(x2, y2) for x2 in range(max(0, x-1), min(width, x+2)) 
                    for y2 in range(max(0, y-1), min(height, y+2))
                    if (x2, y2) != (x, y)]

Kp

Answer 13

Inspired by johniek's answer here is my solution which also checks for boundaries.

def get_neighbours(node, grid_map):
   row_index, col_index = node
   height, width = len(grid_map), len(grid_map[0])
   cells = list(starmap(lambda a, b: (row_index + a, col_index + b), product((0, -1, +1), (0, -1, +1))))
   cells.pop(0) #  do not include original node
   cells = list(filter(lambda cell: cell[0] in range(height) and cell[1] in range(width), cells))
   return cells

Load

Answer 14

def numCells(grid):
    x=len(grid)
    y=len(grid[0])
    c=0
    for i in range(x):
        for j in range(y):
            value_=grid[i][j]
            f=1
            for i2 in range(max(0,i-1),min(x,i+2)):
                for j2 in range(max(0,j-1),min(y,j+2)):
                    if (i2,j2) != (i,j) and value_<=grid[i2][j2]:
                        flag=0
                        break
                if flag ==0:
                    break
                else:
                    c+=1
    return c

Hearty

This determines the number of neighbours, if I understand it correctly, which isn't what the question is asking. – Fanfaronade

Answer 15

def getNeighbors(matrix: list, point: tuple):
    neighbors = [] 
    m = len(matrix)
    n = len(matrix[0])
    x, y = point 
    for i in range (x -1, x +2): #prev row to next row
        for j in range(y - 1, y +2): #prev column to next col 
            if (0 <= i < m) and (0 <= j < n): 
                neighbors.append((i,j))
    return neighbors

Candra

Answer 16

# Get the neighbour elements

from itertools import product
def neighbours(arr, *coordinate):
    x, y=coordinate[0], coordinate[1]
    row=[i for i in range(x-1,x+2) if 0<=i<len(arr)]
    col=[i for i in range(y-1,y+2) if 0<=i<len(arr[0])]
    neighbours= set(product(row,col))-{(x,y)}
    return [arr[val[0]][val[1]] for val in neighbours]


# Example:

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

# 1 2 3
# 4 5 6
# 7 8 9

print(neighbours(arr,0,0))
print(neighbours(arr,0,1))
print(neighbours(arr,1,1))

# Output

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

arr2=[[12,34,12,54],[23,23,11,44],[76,67,87,22],[13,78,45,22],[55,77,33,87]]

# 12 34 12 54
# 23 23 11 44
# 76 67 87 22
# 13 78 45 22
# 55 77 33 87

print(neighbours(arr2,0,0))
print(neighbours(arr2,2,2))
print(neighbours(arr2,4,3))

# Output

[34, 23, 23]
[11, 67, 78, 23, 22, 22, 45, 44]
[45, 22, 33]

Keri

Thank you for your interest in contributing to the Stack Overflow community. This question already has quite a few answers—including one that has been extensively validated by the community. Are you certain your approach hasn’t been given previously? If so, it would be useful to explain how your approach is different, under what circumstances your approach might be preferred, and/or why you think the previous answers aren’t sufficient. Can you kindly edit your answer to offer an explanation? – Officiate

Answer 17

maybe you are checking a sudoku box. If the box is n x n and current cell is (x,y) start checking:

startingRow = x / n * n;
startingCol = y/ n * n

Motorize