recursive finding longest path of same element in 2d list

Question

I need to find the longest path of 0's in a 2d matrix recursively and can't figure out how to do it.( from a given (i , j) it can only move up, down, right or left)

For example this matrix:

mat = [[1, 0, 0, 3, 0],
       [0, 0, 2, 3, 0],
       [2, 0, 0, 2, 0],
       [0, 1, 2, 3, 3]]
    print(question3_b(mat))

This should return 6 as there are communities of sizes 1,3,6. My attempt: I created a few wrapper functions to find the maximum in a list, and a function to find the route at a given (i,j) element and add it to a list, and doing this on every point(i,j) in the matrix.

def question3_b(mat) -> int:
    rows: int = len(mat)
    cols: int = len(mat[0])
    community_lengths = list()
    for i in range(rows):
        for j in range(cols):
            visited = zeros(rows, cols)  # create a 2d list of 0's with size rows,cols
            a = findcommunity(mat, (i, j), visited)
            print("a=", a)
            community_lengths.append(a)
    print(community_lengths)
    return findmax(community_lengths)


def findcommunity(mat: list, indices: tuple, visited: list):  # find length of community
    #global rec_counter
    #rec_counter += 1
    i, j = indices
    rows = len(mat)
    cols = len(mat[0])
    if mat[i][j] == 0:
        visited[i][j] = 1
        if i < rows - 1:
            if visited[i + 1][j] == 0:
                return 1 + findcommunity(mat, (i + 1, j), visited)
        if j < cols - 1:
            if visited[i][j + 1] == 0:
                return 1 + findcommunity(mat, (i, j + 1), visited)
        if i > 0:
            if visited[i - 1][j] == 0:
                return 1 + findcommunity(mat, (i - 1, j), visited)
        if j > 0:
            if visited[i][j - 1] == 0:
                return 1 + findcommunity(mat, (i, j - 1), visited)
    else:  # mat[i][j]!=0

        return 0

def zeros(rows:int,cols:int)->list: #create a 2d matrix of zeros with size (rows,cols)
    if rows==1 and cols==1:return [[0]]
    if rows==1 and cols>1:return [[0]*cols]
    if rows>1 and cols>1:return zeros(rows-1,cols)+zeros(1,cols)
def findmax(arr:list)->int: # find max in an array using recursion
    if len(arr)==2:
        if arr[0]>arr[1]:return arr[0]
        else:return arr[1]
    else:
        if arr[0]>arr[1]:
            arr[1]=arr[0]
            return findmax(arr[1:])
        else:
            return findmax(arr[1:])

Where did I go wrong? for a matrix of 4X4 zeros, I expect it to run 16*16 times[16 times for each i,j, and there are 16 elements in the matrix]. but it only runs once. zeros is a recursive function I made that functions like np.zeros, it creates a 2d matrix full of 0's with specified size.

Answer 1

Here a completely different approach, in case someone is interested.

import numpy as np

mat = [[1, 0, 0, 3, 0],
         [0, 0, 2, 3, 0],
         [2, 0, 0, 2, 0],
         [0, 1, 2, 3, 3]]
mat = np.array(mat)

# some padding of -1 to prevent index error
mask = np.full(np.array(mat.shape) + 2,  -1)
mask[1:-1, 1:-1 ] = mat

# visiteds are set to -2
def trace(f, pt):
    mask[tuple(pt)], pts = -2, [pt - 1]
    pts += [trace(f, pt + d) for d in 
([0, 1], [1, 0], [0, -1], [-1, 0]) if 
mask[tuple(pt + d)] == f]
    return pts

clusters = lambda f: {tuple(pt-1): trace(f, pt) for pt in np.argwhere(mask==f) if mask[tuple(pt)]==f}

# now call with value your looking for
print(clusters(0))

Answer 2

It got really messy but I tried to just change your code instead of writing a new solution. You should have a look at collections deque. Saw this several times where people keep track of visited a lot easier.

I changed visited to outside of the loop and defined it with np.zeros (didn't have your function ;) ). I'm not sure if your recursive function calls at return were wrong but your if-statements were, or at least the logic behind it (or I didn't understand, also possible :) ) I changed that block completly. The first time you come across a 0 in mat the recursive part will dig into the mat as long as it finds another 0 left,right,bottom or top of it (that's the functionality behind dc and dr). That's where the community_counter is increasing. If the function is returning the last time and you jump out to the outerloop in question_3b the counter gets resetted and searchs for the next 0 (next start of another community).

import numpy as np

def question3_b(mat) -> int:
    rows: int = len(mat)
    cols: int = len(mat[0])
    community_lengths = list()
    visited = np.zeros((rows, cols))  # create a 2d list of 0's with size rows,cols
    community_count = 0
    for row in range(rows):
        for col in range(cols):
            if visited[row][col]==0:
                community_count,visited = findcommunity(mat, (row, col), visited, community_count)
                if community_count!=0:
                    community_lengths.append(community_count)
                community_count=0
    return community_lengths


def findcommunity(mat: list, indices: tuple, visited: list,community_count: int):  # find length of community
    i, j = indices
    rows = len(mat)
    cols = len(mat[0])
    visited[i][j] = 1
    if mat[i][j] == 0:
        community_count += 1
        dr = [-1, 0, 1, 0]
        dc = [0,-1, 0, 1]
        for k in range(4):
            rr = i + dr[k]
            cc = j + dc[k]
            if 0<=rr<rows and 0<=cc<cols:
                if visited[rr][cc]==0 and mat[rr][cc]==0:
                    community_count, visited = findcommunity(mat, (rr,cc), visited, community_count)
        return community_count,visited
    else:
        return community_count,visited

mat = [[1, 0, 0, 3, 0],
       [0, 0, 2, 3, 0],
       [2, 0, 0, 2, 0],
       [0, 1, 2, 3, 3]]

all_communities = question3_b(mat)
print(all_communities)
# [6, 3, 1]
print(max(all_communities))
# 6

EDIT

Here is the findcommunity function in your way. Tested it and it works aswell.

def findcommunity(mat: list, indices: tuple, visited: list,community_count: int):  # find length of community
    i, j = indices
    rows = len(mat)
    cols = len(mat[0])
    visited[i][j] = 1
    if mat[i][j] == 0:
        community_count += 1
        if i < rows - 1:
            if visited[i + 1][j] == 0:
                community_count, visited = findcommunity(mat, (i + 1, j), visited, community_count)
        if j < cols - 1:
            if visited[i][j + 1] == 0:
                community_count, visited = findcommunity(mat, (i, j + 1), visited, community_count)
        if i > 0:
            if visited[i - 1][j] == 0:
                community_count, visited = findcommunity(mat, (i - 1, j), visited, community_count)
        if j > 0:
            if visited[i][j - 1] == 0:
                community_count, visited = findcommunity(mat, (i, j - 1), visited, community_count)
        return community_count,visited
    else:
        return community_count,visited