6
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What does while to_fill() entail? What does it mean? I'm not familiar with sets. \$\endgroup\$ – CodesInTheValley Aug 21 '16 at 16:04
  • \$\begingroup\$ @CodesInTheValley Like most objects in python, a set will evaluate to Truthy if it is not empty and to Falsy if it is empty. Therefore, this loop will run until there are no more points to process. \$\endgroup\$ – Graipher Aug 21 '16 at 18:10
  • \$\begingroup\$ In my opinion recursion is simpler and the limit of 1000 can easily be increased (sys.setrecursionlimit). \$\endgroup\$ – Caridorc Aug 21 '16 at 19:39
  • \$\begingroup\$ @Caridorc YMMV. I personally like to have an algorithm where I don't have to think about having to increase that limit. Just one less point of failure. Regarding simpler, it may be a bit shorter (if all the unnecessary list conversions are taken out of OP's code and that if structure simplified), agreed, but I don't think it is conceptually any easier (or harder) than the iterative approach. \$\endgroup\$ – Graipher Aug 21 '16 at 19:56
  • \$\begingroup\$ @Graipher Yes, something analogous to to_fill is kept implicitly by recursion (stack) so there is not much difference in the end. \$\endgroup\$ – Caridorc Aug 21 '16 at 20:20
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.