【Haskell】 Project Euler Prblem4 を少し考えて解いてみた

環境   ghc 7.10.2 CentOS7.0

Problem 4 - PukiWiki

Euler problems/1 to 10 - HaskellWiki
だと結構力技なので、少し考えてみた。

  1 main :: IO ()
  2 main = print $ head [(x, y, z) | x <- palindromes dgt, y <- factors dgt, let z = x `div` y, x `mod` y == 0 && between z ]
  3     where dgt = 3
  4           between n = length (show n) == dgt
  5
  6 factorMax :: Int -> Int
  7 factorMax dgt = read . take dgt $ repeat '9' :: Int
  8
  9 factorMin :: Int -> Int
 10 factorMin dgt = read $ '1':(take (dgt - 1) $ repeat '0') :: Int
 11
 12 factors :: Int -> [Int]
 13 factors dgt = [fMax, fMax-1 .. fMin]
 14     where fMax = factorMax dgt
 15           fMin = factorMin dgt
 16
 17 palindromes :: Int -> [Int]
 18 palindromes dgt = filter isPalindrome [sqrMax, sqrMax-1..sqrMin]
 19     where sqrMax = factorMax dgt * factorMax dgt
 20           sqrMin = factorMin dgt * factorMin dgt
 21
 22
 23 isPalindrome :: Show a => a -> Bool
 24 isPalindrome x = s == reverse s
 25     where s = show x

https://gist.github.com/takafumi-s/dae0cb533bc9e0c2c10e#file-problem4-hs

前者の通常の回答をproblem4、上記のコードをproblem4'としてコンパイルする。

$ time ./problem4
906609

real    0m0.097s
user    0m0.094s
sys     0m0.003s

$ time ./problem4\'
(906609,993,913)

real    0m0.027s
user    0m0.026s
sys     0m0.000s

多少いい感じ。