0votos

Emulando a Dik T. Winter en Haskell

por josejuan hace 5 años

Un par de pequeños speedup permiten mejorar la última versión de haskell a x2,2 (que es un poco mejor que la de C# con los mismos speedup).

Un número de N dígitos es narcisista si la suma de las potencias N-ésimas de sus dígitos es él mismo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
{-# LANGUAGE BangPatterns #-} 
import Data.List 
import System.Clock 
import Data.Array.Unboxed 
import System.Environment 
import qualified Data.Sequence as S 
import Data.Sequence ((<|),(|>)) 
import Data.Foldable (toList) 
 
calculate n = nub $ toList $ S.unstableSort $ S.filter (>=l) $ combinations 0 0 n S.empty 
  where powers = listArray (0, 9) $ map (^n) [0..9] :: UArray Int Int 
        l = 10^(n - 1) 
        isNarcissistic !m = m == sumDown m 0 
                            where sumDown !q !s = if s > m || q < 1 then s else sumDown d (powers!r + s) 
                                    where (d, r) = divMod q 10 
        combinations !acc !d !ds sq = if d == 10 then if isNarcissistic acc then acc <| sq else sq else rs 
                where b = d + 1 
                      p = powers!d 
                      rs = foldl' (\a i -> combinations (acc + i * p) b (ds - i) a) sq [0..ds] 
 
 
main = do 
    n <- getArgs >>= return . read . head 
    t0 <- getTime ProcessCPUTime >>= return . nsec 
    print $ calculate n 
    t1 <- getTime ProcessCPUTime >>= return . nsec 
    putStrLn $ (show ((t1 - t0) `div` 1000000)) ++ " miliS" 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.