If I have an array that is made up of arrays that contain integers
arr[0] = [0, 0, 1, 1, 1, 0, -1] 0
arr[1] = [1, 0, 0, 0, 1, -1, 0] 1
arr[2] = [0, 0, 0, 1, 1, -1, 0] 2
0 1 2 3 4 5 6
And I, for example, want to check how many of the same integers border each other, both horizontally and vertically. For example, if I choose the coordinate (1, 2), which is a 0. I want it to output the number 8. Since there are 8 zeros that are continuous, where all border one another. How would I be able to write a function that does exactly just that?
I have tried the following two functions in Python
print checkLoc(1, 2)
def checkLoc(x, y):
amt = 0
n = arr[y][x]
checkPos(x, y, n)
return amt
def checkPos(x, y, n):
amt += 1
if arr[y - 1][x] == n:
checkPos(x, y - 1, n)
if arr[y + 1][x] == n:
checkPos(x, y + 1, n)
if arr[y][x - 1] == n:
checkPos(x - 1, y, n)
if arr[y][x + 1] == n:
checkPos(x + 1, y, n)
I would expect this to work but it does not. I have experimented with this for a bit and since I simply cannot figure it out I would appreciate some help. Thanks.
In your recursive approach you lacked a basis cases and failed to guard against subscript out of range. You also did nothing to prevent visiting the same position multiple times. The following implements the logic that you seemed to be trying to use, with the aid of a helping data structure to keep track of which positions were visited. Note that I made arr a local variable since I don't like using global variables without a good reason:
def checkPos(arr,visited,i,j,v):
visited[i][j] = True
if arr[i][j] != v:
return 0
else:
count = 1 #current position
if i > 0 and not visited[i-1][j]:
count += checkPos(arr,visited,i-1,j,v)
if i < len(arr)-1 and not visited[i+1][j]:
count += checkPos(arr,visited,i+1,j,v)
if j > 0 and not visited[i][j-1]:
count += checkPos(arr,visited,i,j-1,v)
if j < len(arr[0])-1 and not visited[i][j+1]:
count += checkPos(arr,visited,i,j+1,v)
return count
def checkLoc(arr, x, y):
m = len(arr) # number of rows
n = len(arr[0]) #number of columns
visited = [[False]*n for _ in range(m)]
v = arr[y][x] #value at the position
return checkPos(arr, visited, y, x, v)
#test:
arr =[[0, 0, 1, 1, 1, 0, -1],
[1, 0, 0, 0, 1, -1, 0],
[0, 0, 0, 1, 1, -1, 0]]
counts = [[checkLoc(arr,j,i) for j in range(7)] for i in range(3)]
print('\n'.join(str(row) for row in counts))
The output is as expected:
[8, 8, 6, 6, 6, 1, 1]
[1, 8, 8, 8, 6, 2, 2]
[8, 8, 8, 6, 6, 2, 2]