Equilibrium index: Difference between revisions
Content added Content deleted
No edit summary |
(→JS ES6 Functional: Restored and updated a functional version which returns all equilibrium indices) |
||
Line 1,269: | Line 1,269: | ||
<lang JavaScript>[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]</lang> |
<lang JavaScript>[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]</lang> |
||
===ES6 |
===ES6 Procedural=== |
||
Two pass O(n), returning only the first equilibrium index. |
|||
<lang JavaScript>function equilibrium(arr) { |
<lang JavaScript>function equilibrium(arr) { |
||
let sum = arr.reduce((a, b) => a + b); |
let sum = arr.reduce((a, b) => a + b); |
||
Line 1,289: | Line 1,290: | ||
{{Out}} |
{{Out}} |
||
<lang JavaScript>3, -1, 1, 0, 0</lang> |
<lang JavaScript>3, -1, 1, 0, 0</lang> |
||
===ES6 Functional=== |
|||
A composition of pure generic functions, returning all equilibrium indices. |
|||
<lang javascript>(() => { |
|||
'use strict'; |
|||
// equilibriumIndices :: [Int] -> [Int] |
|||
const equilibriumIndices = xs => |
|||
zip(scanl1(add)(xs))( |
|||
scanr1(add)(xs) |
|||
).reduceRight((a, xy, i) => |
|||
xy[0] === xy[1] ? ( |
|||
[i, ...a] |
|||
) : a, []); |
|||
// ------------------------TEST------------------------ |
|||
const main = () => { |
|||
console.log(JSON.stringify( |
|||
[ |
|||
[-7, 1, 5, 2, -4, 3, 0], |
|||
[2, 4, 6], |
|||
[2, 9, 2], |
|||
[1, -1, 1, -1, 1, -1, 1], |
|||
[1], |
|||
[] |
|||
].map(equilibriumIndices) |
|||
)); |
|||
// -> [[3, 6], [], [1], [0, 1, 2, 3, 4, 5, 6], [0], []] |
|||
}; |
|||
// -----------------GENERIC FUNCTIONS------------------ |
|||
// Tuple (,) :: a -> b -> (a, b) |
|||
const Tuple = a => |
|||
b => ({ |
|||
type: 'Tuple', |
|||
'0': a, |
|||
'1': b, |
|||
length: 2 |
|||
}); |
|||
// add (+) :: Num a => a -> a -> a |
|||
const add = a => |
|||
// Curried addition. |
|||
b => a + b; |
|||
// scanl :: (b -> a -> b) -> b -> [a] -> [b] |
|||
const scanl = f => |
|||
// scanl is like foldl or reduce, but |
|||
// returns a succession of intermediate |
|||
// values, building from the left. |
|||
v => xs => xs.reduce((a, x) => { |
|||
const v = f(a[0])(x); |
|||
return Tuple(v)(a[1].concat(v)); |
|||
}, Tuple(v)([v]))[1]; |
|||
// scanr :: (b -> a -> b) -> b -> [a] -> [b] |
|||
const scanr = f => |
|||
// scanr is like foldr or reduceRight, but |
|||
// returns a succession of intermediate |
|||
// values, building from the right. |
|||
v => xs => xs.reduceRight((a, x) => { |
|||
const v = f(x)(a[0]); |
|||
return Tuple(v)([v].concat(a[1])); |
|||
}, Tuple(v)([v]))[1]; |
|||
// scanl1 :: (a -> a -> a) -> [a] -> [a] |
|||
const scanl1 = f => |
|||
// scanl1 is a variant of scanl that has no |
|||
// seed-value argument, and assumes that |
|||
// xs is not empty. |
|||
xs => xs.length > 0 ? ( |
|||
scanl(f)( |
|||
xs[0] |
|||
)(xs.slice(1)) |
|||
) : []; |
|||
// scanr1 :: (a -> a -> a) -> [a] -> [a] |
|||
const scanr1 = f => |
|||
// 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)) |
|||
) : []; |
|||
// zip :: [a] -> [b] -> [(a, b)] |
|||
const zip = xs => |
|||
ys => Array.from({ |
|||
length: Math.min(xs.length, ys.length) |
|||
}, (_, i) => [xs[i], ys[i]]); |
|||
// MAIN --- |
|||
return main(); |
|||
})();</lang> |
|||
{{Out}} |
|||
<pre>[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |