Posted By

adino on 02/02/15


Tagged

ruby


Versions (?)

Fill algorithm


 / Published in: Ruby
 

none

  1. class CraterFill
  2. class Terrain
  3. def initialize(h)
  4. h.each { |key, value| send("#{key}=", value) }
  5. end
  6. attr_accessor :water, :earth
  7. end
  8.  
  9. def display
  10. @data.each { |x|
  11. x.earth.times {putc('X')}
  12. x.water.times {putc('~')}
  13. puts
  14. }
  15. end
  16.  
  17. def initialize()
  18. @data = []
  19. [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}) }
  20. end
  21.  
  22. def fill()
  23. # find rightmost max in O(N)
  24. max_earth_idx = @data[0].earth
  25. @data.each_with_index {|x,i| max_earth_idx = i if x.earth > @data[max_earth_idx].earth}
  26. # fill left part in O(N)
  27. fill_by_range(0, max_earth_idx, 1)
  28. # fill right part in O(N)
  29. fill_by_range(@data.size - 1, max_earth_idx, -1)
  30. end
  31.  
  32. def fill_by_range(from, to, step)
  33. my_max = @data[from].earth
  34. from.step(to, step) { |i|
  35. if @data[i].earth >= my_max then
  36. my_max = @data[i].earth
  37. else
  38. @data[i].water = (my_max - @data[i].earth)
  39. end
  40. }
  41. end
  42. def water_units
  43. return @data.inject(0) {|acc, x| acc += x.water}
  44. end
  45. end
  46.  
  47. cf = CraterFill.new
  48. cf.fill
  49. cf.display
  50. puts "water units: #{cf.water_units}"
  51.  
  52.  
  53. # prints following
  54. #XXX
  55. #XXXXX
  56. #XX~~~
  57. #XXXXXX
  58. #XXXX~~
  59. #XXX~~~
  60. #XXXXXX
  61. #XXXXXXX
  62. #XXXXXXXX
  63. #X~~~~~~
  64. #XXXXXX~
  65. #XX~~~~~
  66. #XXXXXXX
  67. #XXXX
  68. #XXX
  69. #XX
  70. #X
  71. #water units: 20

Report this snippet  

You need to login to post a comment.