Skip to content

Instantly share code, notes, and snippets.

@gswallow
Created October 31, 2013 19:53
Show Gist options
  • Save gswallow/7255968 to your computer and use it in GitHub Desktop.
Save gswallow/7255968 to your computer and use it in GitHub Desktop.
How much lava collects in valleys?
#!/usr/bin/env ruby
points = [ 1, 2, 1, 4, 1, 3, 2, 9, 7, 5, 10, 1, 2, 1, 2, 1 ]
l_max = 0
r_max = 0
l_lava = 0
r_lava = 0
lava = 0
l_peak = 0
r_peak = points.count - 1
0.upto((points.count / 2) - 1) do |i|
l = points[i]
r = points[points.count - i - 1]
if l < l_max then
l_lava = l_lava + l_max - l
else
lava = lava + l_lava
l_lava = 0
l_max = l
l_peak = i
end
if r < r_max then
r_lava = r_lava + r_max - r
else
lava = lava + r_lava
r_lava = 0
r_max = r
r_peak = points.count - i - 1
end
end
crest = (l_max - r_max).abs
width = (l_peak - r_peak).abs - 1
lava = lava + (l_lava + r_lava - (crest * width))
puts "lava = #{lava}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment