Recursion - Creating a matrix to paint a PPM file

Question

We have a .ppm file representing an image, that is converted into matrix form. Like so:

208 21  139 96  38  169 0   172 123 115 172 154 0   227 153 29  234 109 222 39
5   241 176 62  133 69  0   152 145 154 99  93  0   74  85  47  241 23  207 45
25  92  229 196 163 139 0   189 76  0   0   220 0   2   152 0   79  44  249 203
5   8   75  228 108 125 0   129 0   39  0   18  0   144 30  0   0   0   172 54
222 3   25  196 240 0   0   1   0   11  0   226 0   202 20  203 235 169 0   93
238 184 0   0   0   0   249 123 0   178 0   252 0   91  152 49  119 200 0   31
0   0   220 170 165 11  148 0   0   52  0   233 0   241 131 83  173 196 0   0
204 0   0   0   0   0   0   0   92  225 0   0   0   141 159 182 0   0   0   143
141 178 217 74  0   174 243 164 200 98  138 122 67  44  34  96  0   0   68  118
133 227 39  0   0   118 234 247 38  0   0   0   0   0   0   0   243 247 108 153
54  185 145 0   0   9   102 9   57  0   159 210 128 152 171 4   0   0   118 139
225 161 52  17  0   0   115 129 0   0   170 0   0   0   0   83  45  0   204 91
212 57  167 39  174 0   0   0   0   89  178 0   197 0   0   219 0   0   0   0
173 113 78  184 115 48  107 253 0   0   53  216 0   0   109 245 0   102 42  26
251 187 218 234 139 140 84  101 0   0   64  102 0   0   0   0   106 111 237 26
164 142 31  222 63  218 252 0   0   228 151 76  169 0   95  153 168 195 157 127
141 157 99  86  156 0   0   109 0   227 97  54  0   0   144 11  237 169 67  53
171 211 226 0   0   156 208 207 0   0   0   0   0   249 56  229 194 48  216 197
29  200 99  0   188 160 178 199 145 244 0   0   162 163 254 201 0   120 239 5
51  134 175 0   193 216 79  49  89  86  180 0   0   0   0   0   35  37  42  2

In this matrix zeroes (0) represent walls and positive numbers represent colors. As you can see the matrix is divided into areas&islands by walls (i.e. zeros)(diagonal zeros count as walls as well). I need a program that returns a list of islands including all numbers in that area. (So for example a list including all numbers in first island, then a list including all in the second etc.) I wrote a program below (it's incomplete) but it hits the recursion limit.

To give some perspective, what I am trying to build here is a program that averages the colors in every island. That is, I will need to convert every number within a certain island into an average number that is the average value of all numbers in that island, but I got stuck midway. I used a recursive algorithms as it made most sense to me.

def rec_appender(img,r,c,lst):
n_rows,n_cols=len(img),len(img[0])
if r<0 or c<0 or r>=n_rows or c>=n_cols: # check out actual borders
    return
if img[r][c] == 0:
    return
lst.append(img[r][c])
neigh_list=[[-1,0],[+1,0],[0,-1],[0,+1]]
for neigh in neigh_list:
    rec_appender(img,r+neigh[0],c+neigh[1],lst)


def averager(img):
lst = []
n_rows,n_cols=len(img),len(img[0])
for r in range(0,n_rows):
    for c in range(0,n_cols):
        if img[r][c] != 0: # is wall
            rec_appender(img,r,c,lst)

The second function checks for all points in matrix and if they are not walls refers to first function.

First function appends that point into a list then checks it neighbors whether they are part of the same island and adds them too recursively to the list if they are part of the island. (the code is incomplete as you can see islands won't be separated but my problem is the recursive limit)

Answer 1

Well this should work, in the method dfs() you iterate for every cell in the board, then when you find a cell not visited you tray to visit the entire island using the method _dfs(), every time you end the visit of an island you will have the sum of the colors then you divide by the total cells visited by _dfs(). I use a modified version of the algorithm DFS, you can find more info about it here .

def dfs(colors: list[list[int]]):

    mask=[ [False]*len(colors[0]) for _ in range(len(colors))]

    islands_average:list[float] = []

    for i in range(len(colors)):
        for j in range(len(colors[0])):
            if not mask[i][j] and colors[i][j]!=0 :
                total, sum_for_average=_dfs(i,j,colors, mask )
                average = sum_for_average/total 
                islands_average.append(average)
                
    return islands_average 


def verify_pos(colors,x,y):
    return  x>=0 and x < len(colors) and\
            y>=0 and y < len(colors[0]) 

def _dfs(x:int,y:int,colors, mask) -> tuple[int, int]:
    
    mask[x][y] = True
    sum_for_average = colors[x][y]
    total = 1

    for k in range(4):
        xx = x + helper_x[k]
        yy = y + helper_y[k]
        if verify_pos(colors,xx,yy) and colors[xx][yy]!=0 and not mask[xx][yy]:
            current=_dfs(xx,yy,colors,mask)
            total+=current[0]
            sum_for_average+=current[1]

    return total, sum_for_average 

EDIT: I assumed you had how to convert colors into matrix, you can do it as follow

def get_matrix(string:str):
    sol=[]
    for row in string.split("\n"):
        sol.append([ int(c) for c in row.split(' ') if c!=''])
    return sol

EDIT2: The start method of the algorithm is dfs(colors) and the argument colors is a list of lists of colors, you can use the method get_matrix(string) to get the colors from the input string format.