ASCII Paint Bucket

Question

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("xxxx\n0000\n0xx0\nxxxx", 2, 2, 'p'))

Thoughts?

Answer 1

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()
    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.

Answer 2

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.