Narcissistic decimal number: Difference between revisions
→JS ES6: Added a faster (restricted search) version
(→ES6: Relabelled exhaustive search example, switched to horizontal results) |
(→JS ES6: Added a faster (restricted search) version) |
||
Line 1,300:
})();</lang>
{{Out}}
<
====Reduced search (unordered digit combinations)====
{{Trans|Haskell}}
As summing the nth power of the digits is unaffected by digit order, we can reduce the search space by filtering digit combinations of given length and arbitrary order, rather than filtering a full integer sequence.
In this way we can find the 25th narcissistic number after '''sum(map(compose(length, digitGroups), enumFromTo(1, 7))) === 19447''' tests – an improvement on the exhaustive trawl through '''9926315''' integers.
<lang JavaScript>(() => {
'use strict';
// GENERIC FUNCTIONS
// arrayEq :: [a] -> [a] -> Bool
const arrayEq = (xs, ys) => {
const lngX = xs.length;
return (lngX !== ys.length) ? false : (
lngX > 0 ? (
(() => {
let i = lngX;
while (i--)
if (xs[i] !== ys[i]) return false;
return true;
})()
) : true
);
};
// concat :: [[a]] -> [a] | [String] -> String
const concat = xs => {
if (xs.length > 0) {
const unit = typeof xs[0] === 'string' ? '' : [];
return unit.concat.apply(unit, xs);
} else return [];
};
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// cons :: a -> [a] -> [a]
const cons = (x, xs) => [x].concat(xs);
// curry :: Function -> Function
const curry = (f, ...args) => {
const go = xs => xs.length >= f.length ? (f.apply(null, xs)) :
function () {
return go(xs.concat([].slice.apply(arguments)));
};
return go([].slice.call(args, 1));
};
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
// head :: [a] -> a
const head = xs => xs.length ? xs[0] : undefined;
// isNull :: [a] -> Bool
const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
// map :: (a -> b) -> [a] -> [b]
const map = curry((f, xs) => xs.map(f));
// pure :: a -> [a]
const pure = x => [x];
// show :: a -> String
const show = JSON.stringify;
// sort :: Ord a => [a] -> [a]
const sort = xs => xs.sort();
// NARCISSI
// narcissiOfLength :: Int -> [Int]
const narcissiOfLength = n => {
const isDaffodil = sortedDigits =>
arrayEq(sortedDigits, sort(digitList(powerSum(n, sortedDigits))));
return map(powerSum(n), filter(isDaffodil, digitGroups(n)));
};
// powerSum :: Int -> [Int] -> Int
const powerSum = curry((n, xs) =>
xs.reduce((a, x) => a + Math.pow(x, n), 0));
// Full list of sorted combinations of digits [0..9], with repetition.
// digitGroups :: Int -> [[Int]]
const digitGroups = nDigits => {
const
digits = enumFromTo(0, 9),
sortedCombinations = (n, xs) => (n > 0) ? (
sortedCombinations(n - 1,
isNull(xs) ? (
map(pure, digits)
) : concatMap(xxs =>
map(y => cons(y, xxs), enumFromTo(0, head(xxs))), xs
))
) : xs;
return sortedCombinations(nDigits, []);
};
// digitList :: Int -> [Int]
const digitList = n =>
(n > 0) ? cons((n % 10), digitList(Math.floor(n / 10))) : [];
// TEST
// Narcissistic decimal numbers of digit length from 1 to 7:
return show(
concat(cons(0, map(narcissiOfLength, enumFromTo(1, 7))))
);
})();</lang>
{Out}
<lang JavaScript>[0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084,548834,1741725,4210818,9800817,9926315]</lang>
=={{header|jq}}==
| |||