Bucket Fill Exercise

bucket_fill.py

"""
Bucket Fill Exercise

Imagine you are working on an image editing application. You need to implement a bucket fill tool similar to the one
in paint. The user will use the tool by selecting a color and clicking on the canvas. The tool fills the selected
region of color with the new color.

When a pixel is filled, all of its neighbors (above, below, left, or right) of the same color must also be filled,
as well as their neighbors, and so on, until the entire region has been filled with the new color.

In this exercise, you must write *TWO* implementations of the tool. Each implementation must be different. It is not
required that you invent the solutions yourself. You are encouraged to research the problem. Please write documentation
explaining the difference of each implementation, such as when one solution might be more appropriate than the other.
Don't forget to validate input. There is one existing test, however, you might consider adding some more. Keep in mind
that although the given canvas is small, the solution should be applicable for a real canvas that could have huge
resolutions.

Please use python3 to complete this assignment.
"""


class Canvas(object):
    def __init__(self, pixels):
        self.pixels = pixels

    def __str__(self):
        return '\n'.join(map(lambda row: ''.join(row), self.pixels))

    def fill(self, x, y, color):
        """
        Fills a region of color at a given location with a given color.

        :param x:  the x coordinate where the user clicked
        :param y: the y coordinate where the user clicked
        :param color: the specified color to change the region to
        """
        raise NotImplementedError  # Override this function in the Solution classes


class Solution1(Canvas):
    """
    http://en.wikipedia.org/wiki/Flood_fill#Scanline_fill
    The most efficient way.
    Alternatives:
    Recursion: Stack overflow problem
    Pixel by pixel (Solution2): at least 1 order of magnitude less efficient.
    """

    def fill(self, x, y, color):
        xsize, ysize = len(self.pixels), len(self.pixels[0])
        if x < 0 or x >= xsize or y < 0 or y >= ysize:
            raise ValueError("Wrong values for x,y. ")
        orig_color = self.pixels[x][y]

        stack = set(((x, y),))
        if color == orig_color:
            raise ValueError("Filling region with same value. "
                             "Did you already fill this region?")

        while stack:
            x, y = stack.pop()
            # Scan y1 to the left
            y1 = y
            while y1 >= 0 and self.pixels[x][y1] == orig_color:
                y1 -= 1
            y1 += 1

            # travel right (increase y1)
            east, west = False, False
            while y1 < ysize and self.pixels[x][y1] == orig_color:
                self.pixels[x][y1] = color
                if (not east) and x > 0 and self.pixels[x - 1][y1] == orig_color:
                    stack.add((x - 1, y1))
                    east = True
                elif east and x > 0 and self.pixels[x - 1][y1] != orig_color:
                    east = False

                if (not west) and x < xsize - 1 \
                        and self.pixels[x + 1][y1] == orig_color:
                    stack.add((x + 1, y1))
                    west = True
                elif west and x < xsize - 1 and self.pixels[x + 1][y1] != orig_color:
                    west = False
                y1 += 1


class Solution2(Canvas):
    """
    Queue based implementation.
    Initiatiate queue with starting point (x,y)
    Pop from queue:
        if color needs to be changed (ie, equals to original color):
            change it
            add neighbors to queue
    """

    def fill(self, x, y, color):
        xsize, ysize = len(self.pixels), len(self.pixels[0])
        if x < 0 or x >= xsize or y < 0 or y >= ysize:
            raise ValueError("Wrong values for x,y. ")
        orig_color = self.pixels[x][y]

        stack = set(((x, y),))
        if color == orig_color:
            raise ValueError("Filling region with same value. "
                             "Did you already fill this region?")

        while stack:
            x, y = stack.pop()
            if 0 <= x < xsize and 0 <= y < ysize \
                    and self.pixels[x][y] == orig_color:
                self.pixels[x][y] = color
                stack.add((x - 1, y))
                stack.add((x + 1, y))
                stack.add((x, y - 1))
                stack.add((x, y + 1))


def test_solution(impl):
    s = impl([
        ['O', 'X', 'X', 'X', 'X'],
        ['X', 'O', 'O', 'O', 'X'],
        ['X', 'O', '#', 'O', 'X'],
        ['X', 'O', 'O', 'O', 'X'],
        ['X', 'X', 'X', 'X', 'X'],
        ['X', 'X', 'X', '#', '#'],
        ['X', 'X', 'X', 'X', 'X']
    ])
    s.fill(0, 1, '*')
    s.fill(5, 4, 'O')
    s.fill(2, 2, '@')
    assert str(s) == 'O****\n' \
                     '*OOO*\n' \
                     '*O@O*\n' \
                     '*OOO*\n' \
                     '*****\n' \
                     '***OO\n' \
                     '*****'


def test_solution2(impl):
    def draw_circle(arr, a, b, r):
        import math
        EPSILON = r
        n = len(arr)
        for y in range(n):
            for x in range(n):
                # see if we're close to (x-a)**2 + (y-b)**2 == r**2
                if abs((x - a) ** 2 + (y - b) ** 2 - r ** 2) < EPSILON:
                    arr[y][x] = '#'

    n = 1000
    arr = [['.' for i in range(n)] for j in range(n)]
    draw_circle(arr, n / 2, n / 2, n / 3)
    draw_circle(arr, 3 * n / 4, n / 4, n / 20)

    s = impl(arr)
    s.fill(0, 1, '*')
    s.fill(300, 300, 'x')
    s.fill(250, 750, '@')
    # print(str(s))


if __name__ == '__main__':
    import time

    start_time = time.time()
    test_solution2(Solution1)
    print("--- %.3f seconds for Solution1 ---" % (time.time() - start_time))
    start_time = time.time()
    test_solution2(Solution2)
    print("--- %.3f seconds for Solution2 ---" % (time.time() - start_time))
    test_solution(Solution1)
    test_solution(Solution2)