Water collected between towers: Difference between revisions

Content added Content deleted
(Added Tailspin solution)
(→‎JS :: ES6: Tidied, updated primitives.)
Line 1,289: Line 1,289:
<lang JavaScript>(() => {
<lang JavaScript>(() => {
'use strict';
'use strict';

// ---------- WATER COLLECTED BETWEEN TOWERS -----------


// waterCollected :: [Int] -> Int
// waterCollected :: [Int] -> Int
const waterCollected = xs => {
const waterCollected = xs =>
const
sum(filter(lt(0))(
maxToRight = scanr1(max, xs),
zipWith(subtract)(xs)(
maxToLeft = scanl1(max, xs),
zipWith(min)(
levels = zipWith(min, maxToLeft, maxToRight);
scanl1(max)(xs)
return sum(
)(
zipWith(difference, levels, xs)
scanr1(max)(xs)
.filter(x => x > 0)
)
);
)
};
));




// GENERIC FUNCTIONS -----------------------------------------------------
// ----------------------- TEST ------------------------
const main = () => [
[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]
].map(waterCollected);


// ---------------------- GENERIC ----------------------

// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});


// filter :: (a -> Bool) -> [a] -> [a]
const filter = p =>
// The elements of xs which match
// the predicate p.
xs => [...xs].filter(p);


// gt :: Ord a => a -> a -> Bool
const gt = x => y =>
'Tuple' === x.type ? (
x[0] > y[0]
) : (x > y);


// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
'GeneratorFunction' !== xs.constructor
.constructor.name ? (
xs.length
) : Infinity;


// lt (<) :: Ord a => a -> a -> Bool
const lt = a =>
b => a < b;


// difference :: (Num a) => a -> a -> a
const difference = (a, b) => a - b;


// max :: Ord a => a -> a -> a
// max :: Ord a => a -> a -> a
const max = (a, b) => a > b ? a : b;
const max = a =>
// b if its greater than a,
// otherwise a.
b => a > b ? a : b;



// min :: Ord a => a -> a -> a
// min :: Ord a => a -> a -> a
const min = (a, b) => b < a ? b : a;
const min = a =>
b => b < a ? b : a;



// scanl :: (b -> a -> b) -> b -> [a] -> [b]
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = (f, startValue, xs) => {
const scanl = f => startValue => xs =>
const lst = [startValue];
xs.reduce((a, x) => {
return (
const v = f(a[0])(x);
xs.reduce((a, x) => {
return Tuple(v)(a[1].concat(v));
}, Tuple(startValue)([startValue]))[1];
const v = f(a, x);

return (lst.push(v), v);
}, startValue),
lst
);
};


// scanl1 is a variant of scanl that has no starting value argument
// scanl1 :: (a -> a -> a) -> [a] -> [a]
// scanl1 :: (a -> a -> a) -> [a] -> [a]
const scanl1 = (f, xs) =>
const scanl1 = f =>
xs.length > 0 ? scanl(f, xs[0], xs.slice(1)) : [];
// scanl1 is a variant of scanl that has no
// starting value argument.
xs => xs.length > 0 ? (
scanl(f)(
xs[0]
)(xs.slice(1))
) : [];



// scanr :: (b -> a -> b) -> b -> [a] -> [b]
// scanr :: (b -> a -> b) -> b -> [a] -> [b]
const scanr = (f, startValue, xs) => {
const scanr = f =>
const lst = [startValue];
startValue => xs => xs.reduceRight((a, x) => {
return (
const v = f(x)(a[0]);
xs.reduceRight((a, x) => {
return Tuple(v)([v].concat(a[1]));
}, Tuple(startValue)([startValue]))[1];
const v = f(a, x);

return (lst.push(v), v);
}, startValue),
lst.reverse()
);
};


// scanr1 is a variant of scanr that has no starting value argument
// scanr1 :: (a -> a -> a) -> [a] -> [a]
// scanr1 :: (a -> a -> a) -> [a] -> [a]
const scanr1 = (f, xs) =>
const scanr1 = f =>
xs.length > 0 ? scanr(f, xs.slice(-1)[0], xs.slice(0, -1)) : [];
// scanr1 is a variant of scanr that has no
// seed-value argument, and assumes that
// xs is not empty.
xs => xs.length > 0 ? (
scanr(f)(
xs.slice(-1)[0]
)(xs.slice(0, -1))
) : [];


// sum :: (Num a) => [a] -> a
const sum = xs => xs.reduce((a, x) => a + x, 0);


// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
// subtract :: Num -> Num -> Num
const zipWith = (f, xs, ys) => {
const subtract = x =>
const ny = ys.length;
y => y - x;
return (xs.length <= ny ? xs : xs.slice(0, ny))
.map((x, i) => f(x, ys[i]));
};


// TEST ------------------------------------------------------------------
return [
[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]
].map(waterCollected);


//--> [2, 14, 35, 0, 0, 0, 0]
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);


// take :: Int -> [a] -> [a]
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => xs.slice(0, n);


// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => ((xs_, ys_) => {
const lng = Math.min(length(xs_), length(ys_));
return take(lng)(xs_).map(
(x, i) => f(x)(ys_[i])
);
})(xs, ys);

// MAIN ---
return main();
})();</lang>
})();</lang>
{{Out}}
{{Out}}
Retrieved from "https://rosettacode.org/wiki/Water_collected_between_towers"