Water collected between towers: Difference between revisions
→{{header|Phix}}
No edit summary |
|||
Line 1,397:
{{Out}}
<pre>(2 14 35 0 0 0 0)</pre>
=={{header|Phix}}==
=== inefficient one-pass method ===
<lang Phix>function collect_water(sequence heights)
integer res = 0
for i=2 to length(heights)-1 do
integer lm = max(heights[1..i-1]),
rm = max(heights[i+1..$]),
d = min(lm,rm)-heights[i]
res += max(0,d)
end for
return res
end function
constant tests = {{1,5,3,7,2},
{5,3,7,2,6,4,5,9,1,2},
{2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1},
{5,5,5,5},
{5,6,7,8},
{8,7,7,6},
{6,7,10,7,6}}
for i=1 to length(tests) do
sequence ti = tests[i]
printf(1,"%35s : %d\n",{sprint(ti),collect_water(ti)})
end for</lang>
{{out}}
<pre>
{1,5,3,7,2} : 2
{5,3,7,2,6,4,5,9,1,2} : 14
{2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1} : 35
{5,5,5,5} : 0
{5,6,7,8} : 0
{8,7,7,6} : 0
{6,7,10,7,6} : 0
</pre>
=== more efficient two-pass version ===
<lang Phix>function collect_water(sequence heights)
integer left_max = heights[1],
right_max = heights[$]
sequence left_height = heights,
right_height = heights
for i=2 to length(heights)-1 do
left_max = max(heights[i],left_max)
left_height[i] = left_max
right_max = max(heights[-i],right_max)
right_height[-i] = right_max
end for
sequence mins = sq_min(left_height,right_height),
diffs = sq_sub(mins,heights)
return sum(diffs)
end function</lang>
(same output)
=== pretty print routine ===
<lang Phix>procedure print_water(sequence heights)
integer res = 0, l = length(heights)
sequence towers = repeat(repeat(' ',l),max(heights))
for i=1 to l do
for j=1 to heights[i] do
towers[-j][i] = '#'
end for
if i>1 and i<l then
integer lm = max(heights[1..i-1]),
rm = max(heights[i+1..$]),
m = min(lm,rm)
for j=heights[i]+1 to m do
towers[-j][i] = '~'
res += 1
end for
end if
end for
printf(1,"%s\ncollected:%d\n",{join(towers,"\n"),res})
end procedure
print_water({5,3,7,2,6,4,5,9,1,2})</lang>
{{out}}
<pre>
#
#
#~~~~#
#~#~~#
#~#~#~##
#~#~####
###~####
########~#
##########
collected:14
</pre>
=={{header|PicoLisp}}==
| |||