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.

Solution 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

Solution 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)

Solution 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
            ...

Solution 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

View more solutions