Water collected between towers: Difference between revisions
(Added link to Stack Overflow discussion) |
(→{{header|JavaScript}}: Following cjk's haskell solution on Stack Overflow) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
;Task: |
|||
In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, |
In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, |
||
filling any convex enclosures in the chart with water. |
filling any convex enclosures in the chart with water. |
||
Line 21: | Line 22: | ||
(See, for example, [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Water collected between towers] on Stack Overflow, from which this example is taken). |
(See, for example, [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Water collected between towers] on Stack Overflow, from which this example is taken). |
||
<br><br> |
|||
=={{header|JavaScript}}== |
|||
===ES6=== |
|||
Following [http://stackoverflow.com/users/1416525/cdk cdk]'s Haskell solution at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Stack Overflow]: |
|||
<lang JavaScript>(() => { |
|||
'use strict'; |
|||
const waterCollected = xs => { |
|||
const maxToRight = scanr(max, 0, xs), |
|||
maxToLeft = scanl(max, 0, xs), |
|||
levels = zipWith(min, init(maxToLeft), tail(maxToRight)); |
|||
return zipWith((a, b) => a - b, levels, xs) |
|||
.filter(x => x > 0) |
|||
.reduce((a, b) => a + b, 0); |
|||
} |
|||
// GENERIC FUNCTIONS ---------------------------------------- |
|||
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
const zipWith = (f, xs, ys) => { |
|||
const ny = ys.length; |
|||
return (xs.length <= ny ? xs : xs.slice(0, ny)) |
|||
.map((x, i) => f(x, ys[i])); |
|||
} |
|||
// scanl :: (b -> a -> b) -> b -> [a] -> [b] |
|||
const scanl = (f, startValue, xs) => { |
|||
const lst = [startValue]; |
|||
return ( |
|||
xs.reduce((a, x) => { |
|||
const v = f(a, x); |
|||
return (lst.push(v), v); |
|||
}, startValue), |
|||
lst |
|||
); |
|||
}; |
|||
// scanr :: (b -> a -> b) -> b -> [a] -> [b] |
|||
const scanr = (f, startValue, xs) => { |
|||
const lst = [startValue]; |
|||
return ( |
|||
xs.reduceRight((a, x) => { |
|||
const v = f(a, x); |
|||
return (lst.push(v), v); |
|||
}, startValue), |
|||
lst.reverse() |
|||
); |
|||
}; |
|||
// max :: Ord a => a -> a -> a |
|||
const max = (a, b) => a > b ? a : b; |
|||
// min :: Ord a => a -> a -> a |
|||
const min = (a, b) => b < a ? b : a; |
|||
// init :: [a] -> [a] |
|||
const init = xs => xs.length ? xs.slice(0, -1) : undefined; |
|||
// tail :: [a] -> [a] |
|||
const tail = xs => xs.length ? xs.slice(1) : undefined; |
|||
// TEST --------------------------------------------------- |
|||
return [ |
|||
[1, 5, 3, 7, 2], |
|||
[5, 3, 7, 2, 6, 4, 5, 9, 1, 2], |
|||
[5, 5, 5, 5], |
|||
[5, 6, 7, 8], |
|||
[8, 7, 7, 6], |
|||
[6, 7, 10, 7, 6] |
|||
].map(waterCollected); |
|||
//--> [2, 14, 0, 0, 0, 0] |
|||
})();</lang> |
|||
{{Out}} |
|||
<lang>[2, 14, 0, 0, 0, 0]</lang> |
Revision as of 18:06, 6 December 2016
- Task
In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, filling any convex enclosures in the chart with water.
9 ██ 9 ██ 8 ██ 8 ██ 7 ██ ██ 7 ██░░░░░░░░██ 6 ██ ██ ██ 6 ██░░██░░░░██ 5 ██ ██ ██ ████ 5 ██░░██░░██░░████ 4 ██ ██ ████████ 4 ██░░██░░████████ 3 ██████ ████████ 3 ██████░░████████ 2 ████████████████ ██ 2 ████████████████░░██ 1 ████████████████████ 1 ████████████████████
In the example above, a bar chart representing the values [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has filled, collecting 14 units of water.
Write a function, in your language, from a given array of heights, to the number of water units that would be collected in this way, by a corresponding bar chart.
(See, for example, Water collected between towers on Stack Overflow, from which this example is taken).
JavaScript
ES6
Following cdk's Haskell solution at Stack Overflow:
<lang JavaScript>(() => {
'use strict';
const waterCollected = xs => { const maxToRight = scanr(max, 0, xs), maxToLeft = scanl(max, 0, xs), levels = zipWith(min, init(maxToLeft), tail(maxToRight));
return zipWith((a, b) => a - b, levels, xs) .filter(x => x > 0) .reduce((a, b) => a + b, 0); }
// GENERIC FUNCTIONS ----------------------------------------
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = (f, xs, ys) => { const ny = ys.length; return (xs.length <= ny ? xs : xs.slice(0, ny)) .map((x, i) => f(x, ys[i])); }
// scanl :: (b -> a -> b) -> b -> [a] -> [b] const scanl = (f, startValue, xs) => { const lst = [startValue]; return ( xs.reduce((a, x) => { const v = f(a, x); return (lst.push(v), v); }, startValue), lst ); };
// scanr :: (b -> a -> b) -> b -> [a] -> [b] const scanr = (f, startValue, xs) => { const lst = [startValue]; return ( xs.reduceRight((a, x) => { const v = f(a, x); return (lst.push(v), v); }, startValue), lst.reverse() ); };
// max :: Ord a => a -> a -> a const max = (a, b) => a > b ? a : b;
// min :: Ord a => a -> a -> a const min = (a, b) => b < a ? b : a;
// init :: [a] -> [a] const init = xs => xs.length ? xs.slice(0, -1) : undefined;
// tail :: [a] -> [a] const tail = xs => xs.length ? xs.slice(1) : undefined;
// TEST --------------------------------------------------- return [ [1, 5, 3, 7, 2], [5, 3, 7, 2, 6, 4, 5, 9, 1, 2], [5, 5, 5, 5], [5, 6, 7, 8], [8, 7, 7, 6], [6, 7, 10, 7, 6] ].map(waterCollected);
//--> [2, 14, 0, 0, 0, 0]
})();</lang>
- Output:
<lang>[2, 14, 0, 0, 0, 0]</lang>