# ASCII Paint Bucket

Posted on

Problem

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[0]) 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'))
``````

Thoughts?

Solution

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[0]), len(image)
to_replace = image[y][x]
to_fill = set()
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
``````Input -> to list of lists -> logic -> to string -> output