How to delete a matrix cell's neighbors which are the same value with it

user_10738050 0
Viewed 59

I have a matrix as shown below (taken from a txt file with an argument), and every cell has neighbors. Once you pick a cell, that cell and all neighboring cells that containing the same number will disappear.

1 0 4 7 6 8
0 5 4 4 5 5
2 1 4 4 4 6
4 1 3 7 4 4

I've tried to do this with using recursion. I separated function four parts which are up(), down() , left() and right(). But I got an error message: RecursionError: maximum recursion depth exceeded in comparison 

cmd=input("Row,column:")
cmdlist=command.split(",")
row,column=int(cmdlist[0]),int(cmdlist[1])
num=lines[row-1][column-1]
def up(x,y):
    if lines[x-2][y-1]==num and x>1:
        left(x,y)
        right(x,y)
        lines[x-2][y-1]=None
def left(x,y):
    if lines[x-1][y-2]==num and y>1:     
        up(x,y)
        down(x,y)
        lines[x-1][y-2]=None      
def right(x,y):
    if lines[x-1][y]==num and y<len(lines[row-1]):      
        up(x,y)
        down(x,y)
        lines[x-1][y]=None    
def down(x,y):
    if lines[x][y-1]==num and x<len(lines):    
        left(x,y)
        right(x,y)
        lines[x][y-1]=None               
up(row,column)
down(row,column)
for i in lines:
    print(str(i).strip("[]").replace(",","").replace("None"," "))

When I give the input (3,3) which represents the number of "4", the output must be like this:

1 0   7 6 8
0 5     5 5
2 1       6
4 1 3 7

I don't need fixed code, just the main idea will be enough. Thanks a lot.

python-3.x matrix python
2 Answers

Maybe you should replace

def right(x,y):
    if lines[x-1][y]==num and y<len(lines[row-1]):      
        up(x,y)
        down(x,y)
        lines[x-1][y]=None

by

def right(x,y):
    if lines[x-1][y]==num and y<len(lines[row-1]):      
        lines[x-1][y]=None 
        up(x - 1,y)
        down(x - 1,y)
        right(x - 1, y)

and do the same for all the other functions. Putting lines[x-1][y]=None ensure that your algorithm stops and changing the indices ensure that the next step of your algorithm will start from the neighbouring cell.

user_21973720

Recursion error happens when your recursion does not terminate.

You can solve this without recursing using set's of indexes:

  1. search all indexes that contain the looked for number into all_num_idx
  2. add the index you are currently at (your input) to a set tbd (to be deleted)
  3. loop over the tbd and add all indexed from all_num_idx that differ only in -1/+1 in row or col to any index thats already in the set
  4. do until tbd does no longer grow

delete all indexes from tbd:

t = """4 0 4 7 6 8
0 5 4 4 5 5
2 1 4 4 4 6
4 1 3 7 4 4"""

data = [k.strip().split() for k in t.splitlines()]

row,column=map(int,input("Row,column:").strip().split(";"))
num = data[row][column]

len_r =len(data)
len_c = len(data[0])

all_num_idx = set((r,c) for r in range(len_r) for c in range(len_c) if data[r][c]==num)

tbd = set( [ (row,column)] ) # inital field
tbd_size = 0                 # different size to enter while
done = set()                 # we processed those already
while len(tbd) != tbd_size:  # loop while growing
    tbd_size=len(tbd)
    for t in tbd:
        if t in done:
            continue
        # only 4-piece neighbourhood +1 or -1 in one direction
        poss_neighbours = set( [(t[0]+1,t[1]), (t[0],t[1]+1),
                                (t[0]-1,t[1]), (t[0],t[1]-1)] )
        # 8-way neighbourhood with diagonals
        # poss_neighbours = set((t[0]+a,t[1]+b) for a in range(-1,2) for b in range(-1,2))
        tbd = tbd.union( poss_neighbours & all_num_idx) 
        # reduce all_num_idx by all those that we already addded 
        all_num_idx -= tbd
        done.add(t) 

# delete the indexes we collected
for r,c in tbd:
    data[r][c]=None

# output
for line in data:
    print(*(c or " " for c in line) , sep=" ")

Output:

Row,column: 3,4

4 0   7 6 8
0 5     5 5
2 1       6
4 1 3 7

This is a variant of a "flood-fill-algorythm" flooding only cells of a certain value. See https://en.wikipedia.org/wiki/Flood_fill

user_75053950
Related