From: Martin Boese <boesemar@...>
Date: 2009-04-20T13:47:22+09:00
Subject: Re: [QUIZ] Flood Fill Visualization (#201)

--=-nVC+9OKB03r5PKlxRA/b
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

My solution attached.

Thanks!
martin


On Sat, 2009-04-18 at 00:19 +0900, Daniel Moore wrote: 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> 
> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have elapsed from the time this message was
> sent.
> 
> 2.  Support Ruby Quiz by submitting ideas and responses
> as often as you can!
> Visit: <http://rubyquiz.strd6.com/suggestions>
> 
> 3.  Enjoy!
> 
> Suggestion:  A [QUIZ] in the subject of emails about the problem
> helps everyone on Ruby Talk follow the discussion.  Please reply to
> the original quiz message, if you can.
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> 
> ## Flood Fill Visualization (#201)
> 
> Bonjour Rubyists,
> 
> This week's quiz comes from [Martin DeMello][1]
> 
> [Flood fill][2] is a simple algorithm that colours in a connected
> region of a bitmap. The algorithm looks for all nodes which are
> connected to the start node by a path of the target color, and changes
> them to the replacement color. (Check out the Wikipedia page for more
> information.)
> 
> While simple, the algorithm is pretty satisfying to watch in action,
> which brings us to the quiz: have a program accept a bitmap and a
> starting point, and animate the algorithm as it floodfills the region
> containing that point.
> 
> Have Fun!
> 
> [1]: http://zem.novylen.net
> [2]: http://en.wikipedia.org/wiki/Flood_fill
> 

--=-nVC+9OKB03r5PKlxRA/b
Content-Disposition: attachment; filename="floodfill.rb"
Content-Type: application/x-ruby; name="floodfill.rb"
Content-Transfer-Encoding: 7bit


class FloodFill < Array
  def initialize(data, options = {})
     data.each_line { |s| self << s.strip.split(//) }
     @options = options
  end

  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
  def dump
    each { |l| puts l.join }
  end
end

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

b = FloodFill.new(data, :animation => true)

puts " START: "
b.dump

b.fill(5,3, ' ', 'O')

puts " DONE: "
b.dump

--=-nVC+9OKB03r5PKlxRA/b--