haskell 로 프로젝트 오일러의 25번 문제를 풀어봤다

http://www.haskell.org/haskellwiki/Memoization 읽어보자.
오일러 포럼에는 수학적으로 푼 넘들도 많은데 헐.. 
어릴때 공부 안한게 후회스러울 따름.
http://www.haskell.org/haskellwiki/Euler_problems/21_to_30#Problem_25
도 참고해보자.. 그런데 읽기 어렵네. 어쨌건 돌려보니 내거하곤 성능차이가..
한글위키피디아에 이런 페이지도 있다.


import Data.List(findIndex)

-- 간단한 구현. 이건 속도때문에 꽝. 코드가 트리형태로 전개되기 때문에
-- 매우 느리다.
fibBad 1 = 1
fibBad 2 = 1
fibBad n = fib (n-1) + fib (n-2)
                               

-- 헐 쫌더 나은 버전일랑가.
-- 함수형 언어라면 간지나게 memoize 등을 써서 푸는게 맞을거 같은데
-- 간단히 Data.Map 하나 두고 캐시처럼 써먹는 모듈을 짜보려고 했으나
-- 실패. 이거뭐.. 어떻게 시작해야 할지도 모르겠더라. 일단 문제는 풀어야
-- 겠으니 익숙한 식대로 루프돌렸다.
fib 1 = 1
fib 2 = 1
fib n = f 3 1 1 2
    where f step older old cur
              | step == n = cur
              | otherwise = let newstep  = step+1
                                newolder = old
                                newold   = cur
                                newcur   = newolder+newold
                            in f newstep newolder newold newcur

-- fib 함수로 리스트 생성
fibs = map fib [1..]

-- 자릿수
digits :: (Num a) => a -> Int
digits = length . show

-- 풀이. 리스트는 0 base 이고 위 fib 는 1 base 이므로 1 만큼 보정을 했다.
solve = (+1) `fmap` findIndex ((==1000) . digits) fibs

-- 우왕국
-- 현재 내 PC 에서는 대략 2 초정도에 끝난다.
main = print solve        

haskell 로 프로젝트 오일러의 22번 문제를 풀어봤다

-- http://projecteuler.net/index.php?section=problems&id=22

import Data.List(sort)
import Data.Char(ord)

-- 으험.. 스플릿 함수가 안보이네. 직접 만들어봤는데 좀 추해보인다.
split :: Char -> String -> [String]
split c s = split' [] s
    where split' acc [] = acc
          split' acc s  = let (tok, remains) = break (==c) s
                          in split' (tok:acc) (safeTail remains)
          safeTail []   = []
          safeTail x    = tail x

-- 문자열들을 받아서 , 로 스플릿 하고 앞뒤에서 한글자씩 잘라냈다.
-- 따옴표 제거
names s = map (tail . init) $ split ',' s

nth x = (ord x) - (ord 'A') + 1                          -- 'A' 에서 몇번째 문자냐
scoreName = sum . map nth                                -- 이름의 점수
scoreIndexedName (name,index) = (scoreName name) * index -- 점수에 인덱스 곱

solve input =
    let splitted = names input                  -- 쪼개고
        sorted   = sort splitted                -- 정렬하고
        indexed  = zip sorted [1..]             -- 인덱스붙여서
        scores   = map scoreIndexedName indexed -- 점수내고
    in sum scores                               -- 합

main = do
  input <- readFile "/tmp/h/names.txt"
  print $ solve input

프로젝트 오일러 30 haskell 풀이

import Data.Char(digitToInt)

main = print $ sum solve    

sumOfPowers :: Int -> Int -> Int           
sumOfPowers n = sum . mapDigits (^n)

sumOfFifthPowers   = sumOfPowers 5

-- 음.. 어퍼바운드가 역시나 산술적으로 나오는 모양인데.. 난 그냥 적절히
-- 큰수로 박았다. 쩝
solve = filter surprise candidates
    where surprise n = sumOfFifthPowers n == n
          candidates = [2..999999]

-- 전에 만들어둔 함수. 역시나 오일러에서는 자주쓰이네
mapDigits f n = map (f.digitToInt) (show n)

프로젝트 오일러 20 haskell 풀이

이전에는 fold 안썼는데 이번에 답 옮기면서 fold 로 짜봤다.

아직 어색해서 그런건지.. 가독성이 더 안좋아 보이는데...
반복로직을 fold 가 가져가서 읽기 편하다고 주장들을 하던데
뭐 틀린말은 아닌거 같지만 아직 fold 를 보는순간 머리에서 루프가
안그려져서 읽는게 좀 곤혹스럽다.

import Data.Char(digitToInt)

fac n = product [1..n]
sumOfDigits = foldr (\x acc -> (digitToInt x)+acc) 0 . show
              
main = print $ sumOfDigits $ fac 100              

프로젝트 오일러 48 haskell 풀이

haskell 로는 거저먹는 문제.
쉬운문제 찾다보니.. 낄낄.

-- 흠. fold 의 묘미를 아직 잘 모르겠지만 쉽게 풀긴 했다. foldr 을
-- 쓰기에 적당한 상황이었는지 모르겠네.
f n = foldr (\x acc->acc+(x^x)) 0 [1..n]
solve = f 1000 `mod` 10^10

main = print solve        

프로젝트 오일러 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