How to find neighbors of a 2D list in python?

Question

I have a 2D list of only 1's and 0's:

Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

I need to test this list to check if there are any 1's surrounded by 8 other 1's (such as the middle 1 in this list). If there is a 1 surrounded by 1's as neighbours it should then be changed into a 0 such that after running the program the list above would return as something like this:

[
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,0,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

I'm trying to only use one parameter (the matrix of 1's and 0's). For some reason this is an incredibly difficult thing to wrap my head around. So far my code looks something like this:

def tempBoundaries(matrixC):
    for i in matrixC:
        for j in i:
            if j == 1:
                try:
                    if matrixC[i-1]==1 or matrixC[i+1]==1:
                     .......

This is a real struggle for whatever reason and I seem to be incapable of figuring out what to do, any tips or help would be greatly appreciated! Thanks.

Anserine

Nice. Are you open to using numpy? – Ilo

When you need to open that many blocks of code, it's a good indication that you need to create a method - otherwise the code becomes difficult to understand very quickly – Burro

you should use convolve2d – Micamicaela

You'll find something similar over here #12613163 – Ilo

What if you have a block of 4x4 1s? Should only one of the central 1s be changed to 0, or all four? – Unlawful

I'm trying to just use vanilla python, so numpy is a no no unfortunately :/ – Anserine

@Unlawful all 1's should be 0's, yes. – Anserine

Duplicate of #1621440 – Tolbooth

Answer 1

Using scipy you'd do something like the following

import numpy

boundaries = numpy.array([
                         [0,0,0,0,0],
                         [0,1,1,1,0],
                         [0,1,1,1,1],
                         [0,1,1,1,0],
                         [0,0,1,0,0]])

counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')

# which gives you a matrix with counts of the number of 1s around each point
array([[ 1.,  2.,  3.,  2.,  1.],
       [ 2.,  4.,  6.,  5.,  3.],
       [ 3.,  6.,  9.,  7.,  4.],
       [ 2.,  5.,  7.,  6.,  3.],
       [ 1.,  3.,  4.,  3.,  1.]])

 # so then you just find the points where it's == 9
 counts == 9
 array([[False, False, False, False, False],
        [False, False, False, False, False],
        [False, False,  True, False, False],
        [False, False, False, False, False],
        [False, False, False, False, False]], dtype=bool)

 # so you can update those positions
 boundaries[counts == 9] = 0

So the whole operation is simply:

boundaries = numpy.array(Boundaries)
counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')
boundaries[counts == 9] = 0

Ilo

Thanks! Accept that it turns out we're not allowed to use numpy! @LuisMasuelli, let's be honest, mine is only marginally better :) – Ilo

Answer 2

Since the no numpy requirement was added later I feel I should add a pure python answer.

You could flip the algorithm around. This answer is inspired by the Hough Transform that's used in computer vision feature extraction (http://en.wikipedia.org/wiki/Hough_transform). Instead of hunting around a position you let positions vote for the things they influence. In your case each position with a 1 in it votes for itself and all its neighbours.

It's a little bit of a different approach but it simplifies the logic around hitting the edges of the data. You can just ignore that aspect because even though, for example, (-1, 0) gets voted for, it won't get enough votes to be considered.

Updated

Changed so that a cell doesn't vote for itself. This allows us to use it in the other case too (by searching for cells that have 8 votes). I've split it in to a function that finds all the cells that are surrounded by 1s and an operation that does the flipping (depending on what you're searching for).

import collections
import itertools


def neighbours_of(i, j):
    """Positions of neighbours (includes out of bounds but excludes cell itself)."""
    neighbours = list(itertools.product(range(i-1, i+2), range(j-1, j+2)))
    neighbours.remove((i, j))
    return neighbours


def find_surrounded(grid):
    """List of x,y positions in grid where the cell is surrounded by 1s."""

    votes = collections.defaultdict(int)

    for i, x in enumerate(grid):
        for j, y in enumerate(x):
            # we don't get to vote if not ...
            if y == 0:
                continue

            # vote for everyone in the 3x3 square around us
            for a, b in neighbours_of(i, j):
                votes[(a, b)] += 1

    # now the things we want to change are those that got 8 votes
    surrounded_positions = [pos for pos, count in votes.items() if count == 8]

    return surrounded_positions

def change_when_cell_type_surrounded(grid, cell_type):
    """Update grid inline to flip bits of cells of cell_type that are surrounded."""

    # we'll flip to the opposite of what we're looking for
    change_to = 1 - cell_type

    surrounded = find_surrounded(grid)    

    for i, j in surrounded:
        if grid[i][j] == cell_type:
            grid[i][j] = change_to


grid = [[0,0,0,0,0],
        [0,1,1,1,0],
        [0,1,1,1,1],
        [0,1,1,1,0],
        [0,0,1,0,0]]

change_when_cell_type_surrounded(grid, 1)
change_when_cell_type_surrounded(grid, 0)

Ilo

So using this how would I create another 2D list with the surrounded 0's changed into 1's? I really like how this is structured btw. Thanks for the input :) – Anserine

With the dictionary that is created how would i extract that info and use it properly? I'm not entirely sure what to do with it. – Anserine

No problem. You do like moving the goalposts! :) you mean after we've done this step, do a subsequent operation on the transformed data to then turn any 0s totally surrounded by 1s into a 1? – Ilo

You'll see I convert the votes dict into a list, to_change, that contains the indexes that you're interested in. In the final step I use those indexes to change the values in Boundaries. – Ilo

Yea exactly that. I'm trying to recreate the boundaries list with any 0's surrounded by 1's into a 1. – Anserine

I've updated with the new requirement. Something inside me is telling me that you won't always get back to the same result by reversing the operation. Flipping from 1s to 0s will create holes so there will be less flipping from 0s to 1s. You may already know this. – Ilo

Your neighbours_of method is very elegant. – Germanism

Answer 3

To simplify your code, you should move the code to check the neighbors inside a function. You can also use a list of directions, then iterate through the directions, like this:

directions = [(-1, -1), (0, -1), ...]
def check_neighbors(m, x, y):
    for direction in directions:
        dx, dy = direction
        # You should check here that (x+dx, y+dx) 
        # is still inside the matrix
        if ...:
            continue
        if matrix[x+dx][y+dy] == 0:
            return False
    return True

In your main function, your matrix is basically a list of lists. Since you're going to manipulate the indexes, you should use a range of the possible indexes.

# Big assumption: all sublists have the same length
for x in range(len(matrixC)):
    for y in range(len(matrixC[0])):
        if check_neighbors(matrixC, x, y):
            # Do what you want here
            ...

Shaeffer

I am assuming that the 2D list is infact rectangular so you're right on the money there. – Anserine

This is great actually, really putting me on the right track. I'm gonna try to get this working and I'll follow up later! Thanks! :) – Anserine

Answer 4

what about this:

Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

tochange = []
for i in xrange(len(Boundaries)-3):
    for j in xrange(len(Boundaries)-3):
        for k in xrange(3):
            for l in xrange(3):
                if not Boundaries[i+k][j+k]:
                    break
            else:
                continue
            break
        else:
            tochange.append((i+1, j+1))

for i, j in tochange:
    Boundaries[i][j] = 0

Egg

Answer 5

You can use numpy

from numpy import ones
from scipy.signal import convolve2d

kernel = ones((3, 3))
#you create a matrix like this
#1 1 1
#1 1 1
#1 1 1

image = array(Boundaries)
#your boundaries were converted to a bidimensional numpy array

convolved = convolve2d(image, kernel, mode="same")
#you will have an image like this:
#[
#    [1,2,3,2,1],
#    [2,4,6,4,3],
#    [3,6,9,7,4],
#    [2,4,6,4,3],
#    [1,2,3,2,1]
#]

then you should change the images accordingly:

for (x,y), value in numpy.ndenumerate(a):
    image[x, y] = image[x, y] if convolved[x, y] < 9 else 0

disclaimer : this code does not kill 1s in the borders. you must change it accordingly

Micamicaela

Answer 6

No numpy

Edit

I think this is a better solution, as it breaks the inner loop as soon as a neighbor is equal to zero

def zero_one(input2d, r, c):
    for rr in (r-1, r, r+1):
        for cc in (c-1, c, c+1):
            if input2d[rr][cc] == 0 : return 1
    return 0

Boundaries = [[0,0,0,0,0],
              [0,1,1,1,0],
              [0,1,1,1,1],
              [0,1,1,1,0],
              [0,0,1,0,0]]

rows = 5
cols = 5
Output = []

for r in range(rows):
    Output.append([])
    for c in range(cols):
        if (r==0 or r==rows-1) or (c==0 or c==cols-1):
            Output[r].append(Boundaries[r][c])
        elif Boundaries[r][c] == 0:
            Output[r].append(0)
        else:
            Output[r].append(zero_one(Boundaries, r, c))

for line in Output:
    print line

executing the above code gives

[0, 0, 0, 0, 0]
[0, 1, 1, 1, 0]
[0, 1, 0, 1, 1]
[0, 1, 1, 1, 0]
[0, 0, 1, 0, 0]

My previous code is after the

End of Edit

In [15]: Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

In [16]: Output = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

In [17]: for i in (1, 2, 3):
    for j in (1,2,3):
        s = 0
        for m in (i-1, i, i+1):
            for n in (j-1, j, j+1):
                s = s+Boundaries[n][m]
        if s == 9 : Output[j][i] = 0
   ....:         

In [18]: Output
Out[18]: 
[[0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0],
 [0, 1, 0, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 0, 1, 0, 0]]

In [19]: 

Stores

Answer 7

I created a simple one like this, you can make custom

from itertools import product, starmap, islice
def findNeighbors(grid, x, y):
    xi = (0, -1, 1) if 0 < x < len(grid) - 1 else ((0, -1) if x > 0 else (0, 1))
    yi = (0, -1, 1) if 0 < y < len(grid[0]) - 1 else ((0, -1) if y > 0 else (0, 1))
    return islice(starmap((lambda a, b: grid[x + a][y + b]), product(xi, yi)), 1, None)

1st example:

grid = [[ 0,  1,  2,  3],
...     [ 4,  5,  6,  7],
...     [ 8,  9, 10, 11],
...     [12, 13, 14, 15]]
n = list(findNeighbors(grid, 2, 1))   # find neighbors of 9
print(n)

Output: [8, 10, 5, 4, 6, 13, 12, 14]

2nd Example:

grid = [[ 0,  1,  2,  3],
...     [ 4,  5,  6,  7],
...     [ 8,  9, 10, 11],
...     [12, 13, 14, 15]]
n1 = list(findNeighbors(grid, 3, 3))   # find neighbors of 15
print(n1)

Output: [14, 11, 10]

Let me know if you have any question

Tombouctou