프로젝트 오일러 34 haskell 풀이

블로그스팟에 적던건데 그냥 이쪽으로 죄다 적어야겠다. 구글갓댐.

이건 정리된 버전...

import Data.Char(digitToInt)

main = print solve
       
fac n = foldr (*) 1 [1..n]      -- 팩토리얼 
mapDigits f n = map (f.digitToInt) (show n) -- 각 디짓 별로 map
curious n = n == sumOfDigitFact n           -- 34 번 문제의 조건에 맞는지 판단
sumOfDigitFact = sum . mapDigits fac        -- 각 디짓의 팩토리얼의 합
solve = filter curious [3..100000]          -- 이거.. 어퍼바운드 결정을 그냥 때려 맞춘것


아래는 풀이하면서 이것저것 해본 코드. foldl/foldl'/foldr 차이점은 아직 느낌이 잘 안오네..

      펼쳐두기..
  
{-
  http://projecteuler.net/index.php?section=problems&id=34

  이코드 만들면서 느낀점은..
  1. foldr 이 묘하게 빠르네. 잘 이해가 안간다. 관련문서 찾아보자.
  2. mapDigits 음.. 완전 삽질했다.
-}


import Data.Char(digitToInt)
    
-- fold 를 써서 만들어본 factorial 구현. 쓸데없이 리스트를 만든다는게
-- 눈에 거슬리지만 코드가 깔끔해진다는 장점이 있다.
fac :: Int -> Int
fac n = foldr (*) 1 [1..n]

-- 고전적인 테일리커시브를 이용한 팩토리얼. 어느 방법이 더 좋은지 잘
-- 모르겠네.
-- 음.. 돌려보니 fold 를 써서 구현한놈이 월등히 빠르다. 이유가 뭘까
fac2 :: Int -> Int
fac2 n = fac' 1 n
    where fac' acc 0 = acc
          fac' acc n = fac' (acc*n) (n-1)

curious :: Int -> Bool
curious n = n == sumOfDigitFact n

sumOfDigitFact :: Int -> Int
sumOfDigitFact = sum . mapDigits2 fac

-- 만들고 보니 오일러 문제 에서 자주 쓰일만한 함수네
-- mapDigits id 123456789
-- 를 돌려보면 대강 감잡을거다
-- 음 그런데 이 함수가 효율적인이 아닌지 잘 모르겠네
mapDigits :: (Integral a) => (a->b) -> a -> [b]
mapDigits f n = map [] n
    where map acc n =
              case divMod n 10 of
                (0, mod)  -> (f mod):acc
                (div,mod) -> map ((f mod):acc) div


-- 음 삽질했네. 10 으로 나눠대는 위 구현보다 이쪽이 더 빠르다.
mapDigits2 f n = map (f.digitToInt) (show n)
              
                             
-- 음 어퍼바운드를 얼마나 잡아야 하는지 모르겠네.  문제에서 수학적으로
-- 어퍼바운드가 산출이 가능한 모양인데 내머리론 불가능 그냥 적절히 큰값
-- 잡고 돌려보니 145 말고 값이 하나 떨어지길래(레이지한 특성때문에 값이
-- 떨어지는게 보인다!!!) 그값하고 문제의 145 를 더한 값을 넣어보니
-- 정답이라네..
solve = filter curious [3..50000]

main = print solve