## Posted By

adino on 02/02/15

# Fill algorithm

/ Published in: Ruby

none

`class CraterFill  class Terrain    def initialize(h)      h.each { |key, value| send("#{key}=", value) }    end    attr_accessor :water, :earth  end   def display    @data.each { |x|      x.earth.times {putc('X')}      x.water.times {putc('~')}      puts    }  end   def initialize()    @data = []    [3,5,2,6,4,3,6,7,8,1,6,2,7,4,3,2,1].each {|x| @data << Terrain.new({earth: x, water: 0}) }  end   def fill()    # find rightmost max in O(N)    max_earth_idx = @data[0].earth    @data.each_with_index {|x,i| max_earth_idx = i if x.earth > @data[max_earth_idx].earth}    # fill left part in O(N)    fill_by_range(0, max_earth_idx, 1)    # fill right part in O(N)    fill_by_range(@data.size - 1, max_earth_idx, -1)  end   def fill_by_range(from, to, step)    my_max = @data[from].earth    from.step(to, step) { |i|      if @data[i].earth >= my_max then        my_max = @data[i].earth      else        @data[i].water = (my_max - @data[i].earth)      end    }  end  def water_units    return @data.inject(0) {|acc, x| acc += x.water}  endend cf = CraterFill.newcf.fillcf.displayputs "water units: #{cf.water_units}"  # prints following#XXX#XXXXX#XX~~~#XXXXXX#XXXX~~#XXX~~~#XXXXXX#XXXXXXX#XXXXXXXX#X~~~~~~#XXXXXX~#XX~~~~~#XXXXXXX#XXXX#XXX#XX#X#water units: 20`

You need to login to post a comment.