Multiplicative Persistence

Multiplicative Persistence 11を求めたという話題があったので、Pythonで実装しましたが、Haskellでも実装してみました。私のPCで0.76秒くらい。こういうときには遅延評価は便利ですよね。Python版では探索空間をさらに減らすことで0.02秒を実現しています。

module Main where

import Data.Char (digitToInt)

mps :: [(Integer, Int)]
mps = map calcMP targets
  where
    calcMP :: Integer -> (Integer, Int)
    calcMP t = (t, calcMP' t)
    calcMP' :: Integer -> Int
    calcMP' t | t < 10    = 0
              | otherwise = let t' = foldr (*) 1 $ map (fromIntegral . digitToInt) $ show t
                            in calcMP' t' + 1
    targets :: [Integer]
    targets = 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : concatMap extend targets
    extend :: Integer -> [Integer]
    extend i = map (\j -> i * 10 + j) [fromIntegral (i `mod` 10)..9]

getMP :: Int -> (Integer, Int)
getMP limit = head $ dropWhile (\(_, mp) -> mp < limit) $ mps

main :: IO ()
main = print $ getMP 11
-- (277777788888899,11)