In MS Paint, if we choose paint bucket and fill click on a certain spot, it gets filled with a new chosen color along with its neighboring pixels that are the same color until it reaches certain limitations such as a different color. This program, using recursion, does the same thing except to a flat ASCII surface:
xxxx xxxx 0000 0000 0xx0 ---> 2, 2, p -> 0pp0 xxxx pppp
And here’s the code in question:
def findchar(pattern, posx, posy): pattern_list = pattern.splitlines() return pattern_list[posy][posx] def fill(pattern, posx, posy, char): oldchar = findchar(pattern, posx, posy) pattern_list = pattern.splitlines() line_split = list(pattern_list[posy]) line_split[posx] = char pattern_list[posy] = ''.join(line_split) new_pattern = 'n'.join(pattern_list) if posx >= 0 and posx+1 < len(pattern_list) and posy >= 0 and posy+1 < len(pattern_list): for i in [-1, 0, 1]: if pattern_list[posy+i][posx+1] == oldchar: new_pattern = fill(new_pattern, posx+1, posy+i, char) elif pattern_list[posy+i][posx-1] == oldchar: new_pattern = fill(new_pattern, posx-1, posy+i, char) elif pattern_list[posy+1][posx+i] == oldchar: new_pattern = fill(new_pattern, posx+i, posy+1, char) elif pattern_list[posy-1][posx+i] == oldchar: new_pattern = fill(new_pattern, posx+i, posy-1, char) return new_pattern print(fill("xxxxn0000n0xx0nxxxx", 2, 2, 'p'))
I would also suggest doing the conversion to a list once at the beginning and back to a string at the end.
In addition I would suggest to use a different algorithm. Your algorithm will fail if the image becomes too big (where too big is for a usual setup when the number of cells to fill > 1000, the default recursion limit of python).
You can easily write this as an iterative algorithm in this way:
def flood_fill(image, x, y, replace_value): image = [list(line) for line in image.split('n')] width, height = len(image), len(image) to_replace = image[y][x] to_fill = set() to_fill.add((x, y)) while to_fill: x, y = to_fill.pop() if not (0 <= x < width and 0 <= y < height): continue value = image[y][x] if value != to_replace: continue image[y][x] = replace_value to_fill.add((x-1, y)) to_fill.add((x+1, y)) to_fill.add((x, y-1)) to_fill.add((x, y+1)) return 'n'.join(''.join(line) for line in image)
This uses a set to hold all points which need to be replaced by the char, adding all adjacent points to the set if a point was replaced. It loops and processes each point in the set until it is empty.
You are doing too much work converting between string and list data-structures on each iteration, this is complicating the code.
I suggest converting to list of lists on input and back to string on output:
Input -> to list of lists -> logic -> to string -> output
Changing the character at the given coordinates in a list of lists should be much simpler.