HaskellでProject Euler #51

List comprehensioが便利だった.ideoneで<0.3secぐらい.

import           Data.List

-- PE #51
main :: IO ()
main = do
  let n = 8
  -- Suffice to check (11 - n) digits for n primes families
  let chars = take (11 - n) "0123456789"
  let primes = 2 : filter isPrime [3, 5 ..]
  let cands =
        [ variants
        | p <- primes
        , let repr = reverse (show p)
        , let idxMax = length repr - 1
        -- Do not alter ones digit
        , let places c = map fst . filter ((== c) . snd) . tail $ zip [0 ..] repr
        , c <- chars
        , idxs <- filter (not . null) $ subsequences (places c)
        , let variants =
                [ num
                | d <- [0 .. 9]
                -- Do not put zero in the first digit
                , d > 0 || maximum idxs < idxMax
                , let num = replaceDigits p idxs d
                , isPrime num
                ]
        ]
  let answer = head . filter ((== n) . length) $ cands
  print answer

isPrime :: Int -> Bool
isPrime q = q >= 2 && all notFactorOfQ (2 : [3, 5 .. s])
    where
      notFactorOfQ = (/= 0) . mod q
      s = ceiling $ sqrt (fromIntegral q :: Double)

replaceDigits :: Int -> [Int] -> Int -> Int
replaceDigits n [] _ = n
replaceDigits n (i:is) d = let
  unit = 10 ^ i
  d0 = (n `mod` (unit * 10)) `div` unit
  n1 = n + unit * (d - d0)
  in replaceDigits n1 is d