From: Daniel Moore <yahivin@...>
Date: 2009-04-26T05:37:05+09:00
Subject: Re: [QUIZ] Flood Fill Visualization (#201)

This quiz was submitted by Martin DeMello [1] using the submission
form: http://rubyquiz.strd6.com/suggestions. Please do submit quiz
ideas, Ruby Quiz thrives with support from the community!

Martin Boese provided a solution that animates the filling process by
printing the output to the console.

The core of Martin B.'s solution is this recursive fill method.

    def fill(x, y, target_color, replacement_color)
        return unless self[y][x]	# valid point?

        return if self[y][x] != target_color
        return if self[y][x] == replacement_color

        (dump; sleep(0.2)) if @options[:animation]

        self[y][x] = replacement_color
        fill(x+1, y, target_color, replacement_color)
        fill(x-1, y, target_color, replacement_color)
        fill(x, y+1, target_color, replacement_color)
        fill(x, y-1, target_color, replacement_color)
    end

The method begins with a few checks to determine if it should return.
The first check exits the method if the point is outside of the
canvas. The next check exits if the current point's color does not
match the target color, we don't want to fill just anything. The third
check exits if the current point's color is equal to the replacement
color, if we didn't then we would fill forever!

This part: `(dump; sleep(0.2))` is responsible for printing the state
of the operation to the console and waiting a little bit.

Partially Complete [2]

Completed [3]

The final section sets the color of the current point and recursively
calls `fill` on all adjacent points.

Martin DeMello submitted a Shoes App solution. Although Martin D.'s
solution didn't work for me exactly as submitted, with a little
tweaking I was able to get it to run. The neat part about Martin D.'s
solution is that, aside from being colorful Shoes App, it allows you
to view the animation when the cells are placed in a stack or a queue.

Here are two images showing the difference in how the fills proceed
when using a stack or a queue:

Stack [4]

Queue [5]

In both solution the starting canvas data was represented as characters like so:

    data = <<END
    ##############
    #   #        #
    #   #        #
    #  #      #  #
    ###      #   #
    #        #   #
    ##############
    END

Together these two solutions cover the major possible implementations
of the Flood Fill algorithm: recursively with an implicit stack (the
call stack) and iteratively with an explicit stack or queue.

I hope you find these solutions interesting and that they help you out
when you are making your next graphics application (maybe a future
quiz!)

[1]: http://zem.novylen.net
[2]: http://rubyquiz.strd6.com/quizzes/201/floodfill_1.png
[3]: http://rubyquiz.strd6.com/quizzes/201/floodfill_2.png
[4]: http://rubyquiz.strd6.com/quizzes/201/stack.png
[5]: http://rubyquiz.strd6.com/quizzes/201/queue.png