Narcissistic decimal number: Difference between revisions

Content added Content deleted
(→‎Haskell reduced search: (used swap in digitList))
(→‎JS ES6: -> Generating the unordered digit combinations as their power sums)
Line 1,544: Line 1,544:


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.
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.

(Generating the unordered digit combinations directly as power sums allows faster testing later, and needs less space)
<lang JavaScript>(() => {
<lang JavaScript>(() => {
'use strict';
'use strict';


// DAFFODILS --------------------------------------------------------------
// GENERIC FUNCTIONS


// arrayEq :: [a] -> [a] -> Bool
// narcissiOfLength :: Int -> [Int]
const arrayEq = (xs, ys) => {
const narcissiOfLength = n =>
n > 0 ? filter(curry(isDaffodil)(n), digitPowerSums(n)) : [0];
const lngX = xs.length;

return (lngX !== ys.length) ? false : (
// Do the decimal digits of N, each raised to the power E, sum to N itself ?
lngX > 0 ? (

(() => {
// isDaffodil :: Int -> Int -> Bool
let i = lngX;
const isDaffodil = (e, n) => {
while (i--)
const
if (xs[i] !== ys[i]) return false;
return true;
powerSum = (n, xs) => xs.reduce((a, x) => a + Math.pow(x, n), 0),
})()
digitList = n => (n > 0) ? (
) : true
cons((n % 10), digitList(Math.floor(n / 10)))
);
) : [],
ds = digitList(n);
return e === ds.length && n === powerSum(e, ds);
};
};


// The subset of integers of n digits that actually need daffodil checking:
// concat :: [[a]] -> [a] | [String] -> String

const concat = xs => {
// (Flattened leaves of a tree of unique digit combinations, in which
if (xs.length > 0) {
// order is not significant. Digit sequence doesn't affect power summing)
const unit = typeof xs[0] === 'string' ? '' : [];

return unit.concat.apply(unit, xs);
} else return [];
// digitPowerSums :: Int -> [Int]
const digitPowerSums = nDigits => {
const
digitPowers = map(x => [x, pow(x, nDigits)], enumFromTo(0, 9)),
treeGrowth = (n, parentPairs) => (n > 0) ? (
treeGrowth(n - 1,
isNull(parentPairs) ? (
digitPowers
) : concatMap(([parentDigit, parentSum]) =>
map(([leafDigit, leafSum]) => //
[leafDigit, parentSum + leafSum],
take(parentDigit + 1, digitPowers)
),
parentPairs
))
) : parentPairs;
return map(snd, treeGrowth(nDigits, []));
};
};


// GENERIC FUNCTIONS ------------------------------------------------------

// enumFromTo :: Int -> Int -> Maybe Int -> [Int]
const enumFromTo = (m, n, step) => {
const d = (step || 1) * (n >= m ? 1 : -1);
return Array.from({
length: Math.floor((n - m) / d) + 1
}, (_, i) => m + (i * d));
};
// concatMap :: (a -> [b]) -> [a] -> [b]
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
Line 1,578: Line 1,607:
const cons = (x, xs) => [x].concat(xs);
const cons = (x, xs) => [x].concat(xs);


// 2 or more arguments
// curry :: Function -> Function
// curry :: Function -> Function
const curry = (f, ...args) => {
const curry = (f, ...args) => {
Line 1,586: Line 1,616:
return go([].slice.call(args, 1));
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]
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
const filter = (f, xs) => xs.filter(f);


// head :: [a] -> a
// map :: (a -> b) -> [a] -> [b]
const head = xs => xs.length ? xs[0] : undefined;
const map = curry((f, xs) => xs.map(f));


// isNull :: [a] -> Bool
// isNull :: [a] -> Bool
const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;


// map :: (a -> b) -> [a] -> [b]
// length :: [a] -> Int
const map = curry((f, xs) => xs.map(f));
const length = xs => xs.length;

// pow :: Int -> Int -> Int
const pow = Math.pow


// pure :: a -> [a]
// take :: Int -> [a] -> [a]
const pure = x => [x];
const take = (n, xs) => xs.slice(0, n);


// show :: a -> String
// show ::
// (a -> String) f, Num n =>
// a -> maybe f -> maybe n -> String
const show = JSON.stringify;
const show = JSON.stringify;


// sort :: Ord a => [a] -> [a]
// snd :: (a, b) -> b
const sort = xs => xs.sort();
const snd = tpl => Array.isArray(tpl) ? tpl[1] : undefined;


// 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 -------------------------------------------------------------------


// return length(concatMap(digitPowerSums, enumFromTo(0, 7)));
// TEST


// Narcissistic decimal numbers of digit length from 1 to 7:
return show(
return show(
concat(cons(0, map(narcissiOfLength, enumFromTo(1, 7))))
concatMap(narcissiOfLength, enumFromTo(0, 7))
);
);
})();</lang>
})();</lang>
Retrieved from "https://rosettacode.org/wiki/Narcissistic_decimal_number"