カテゴリー: Haskell

module Main (main) where

euler031 :: [Int] -> Int -> Int
euler031 (x:[]) m | m `mod` x == 0 = 1
                 | otherwise = 0
euler031 (x:xs) m = sum $ map (\n -> euler031 xs (m - x*n)) [0..(m `div` x)]

main :: IO ()
main = putStrLn $ show $ euler031 [200,100,50,20,10,5,2,1] 200

^o^ >runhaskell euler031.hs
73682

1pのコインがない場合：

*Main> euler031 [200,100,50,20,10,5,2] 200
1784

今日は Problem 14。

　cf. Project Euler – Problem 14

コラッツ問題の数列を求めるのは以前にやったのを流用。あとは力任せに…

module Main (main) where

collatz :: Int -> [Int]
collatz 1 = 1 : []
collatz n | n `mod` 2 == 0 = n : collatz (n `div` 2)
          | otherwise = n : collatz (n * 3 + 1)

euler014 :: Int -> [Int]
euler014 n = snd $ foldl g (0, []) $ map f [1..n]
  where
    f x = ((length.collatz) x, x)
    g (x,zs) (l,z) | x < l = (l, z:[])
                   | x == l = (x, z:zs)
                   | otherwise = (x, zs)

main :: IO ()
main = mapM_ (putStrLn.show) $ euler014 1000000

やったらあえなくスタックオーバーフローに。ありゃ。

^o^ >runhaskell euler014.hs
*** Exception: stack overflow

100,000までだったらうまくいったので間違ってはいないと思う。たぶん数列がすごく長くなる数があるんだろうな。再挑戦はまた今度。

あと，ついでに書いておくと，各数の数列にはおなじ部分列が何度も出現する。これを覚えておけば計算量を少なくできるんだけど，メモ化のやり方がわからない。

今日は Problem 8。

　cf. Project Euler – Problem 8

module Main (main) where

import Data.List
import Data.Char

euler008 :: [Char] -> Int
euler008 n = maximum $ map euler008' $ nums n
  where
    nums = filter (\x -> length x > 4) . map (take 5) . tails
    euler008' = foldl1 (*) . map digitToInt

main :: IO ()
main = do n <- getContents >>= return . concat . lines
          putStrLn $ show $ euler008 n

^o^ >runhaskell euler008.hs < euler008.txt
40824

今日は Problem 13 をやってみた。これは簡単。

　cf. Project Euler – Problem 13

nums :: [Integer]
nums = [37107287533902102798797998220837590246510135740250,
        46376937677490009712648124896970078050417018260538,
        74324986199524741059474233309513058123726617309629,
        ...
        72107838435069186155435662884062257473692284509516,
        20849603980134001723930671666823555245252804609722,
        53503534226472524250874054075591789781264330331690]

euler013 :: String
euler013 = take 10 $ show $ sum nums

main :: IO ()
main = putStrLn euler013

^o^ >runhaskell euler013.hs
5537376230

追記：

数字をファイル（euler013.txt）から読み込むようにしてみた。

euler013 :: [Integer] -> String
euler013 = take 10 . show . sum

main :: IO ()
main = do nums <- getContents >>= return . lines
          putStrLn $ euler013 $ map read nums

^o^ >runhaskell euler013a.hs < euler013.txt
5537376230

今日は Problem 12をやってみた。

　cf. Project Euler – Problem 12
　via 自堕落系徒然日記 – Problem 12 三角数の約数

module Main where

import Data.List

triangleNumbers :: [Integer]
triangleNumbers = snd $ mapAccumL (\a x -> (a+x, a)) 1 [2..]

divisors :: Integer -> [Integer]
divisors n = concat [ z | x <- [1..floor (sqrt (fromInteger n))] , let (y,r) = n `divMod` x , r == 0 , let z = if x == y then [x] else [x,y]]
euler012 :: Integer euler012 = f $ euler012' where euler012' = find (\x -> (length . divisors) x > 500) triangleNumbers
f (Just x) = x

main :: IO ()
main = print euler012

約数を求める関数 divisors はこないだの nobsun さんのやつにちょっと手を入れた。
コンパイルしてから実行して数秒といったところ。もっと工夫できるのかも。

^o^ >ghc -o euler012 euler012.hs
^o^ >euler012
76576500

なるほど，unfold ってこういうふうに使えるのか。

　cf. ZOETROPEの日記 – Foundations of F#を読む(3)

Haskellでやってみる。

*Main> take 10 $ Data.List.unfoldr (\(n0,n1) -> Just (n0, (n1, n0+n1))) (1, 1)
[1,1,2,3,5,8,13,21,34,55]

unfoldr に与える関数は b -> Maybe (a, b) 型で，Nothing が返ると終端になるらしい。だから上の例では無限リストになって，最初の10個だけ取り出している。

今日は Probrem 21 をやってみた。

　cf. http://projecteuler.net/index.php?section=problems&id=21

数 n に対して約数（nを含まない）すべてを足しあわせる関数 d があるとして，d(a) = b かつ d(b) = a となるような a と b （ただしa≠b）を amicable pair，それぞれを amicable number という（んだそうだ）。で，10000未満の amicable number をすべて足しあわせろ，という問題。
内包表記大活躍……なのはいいけど，すっげー時間がかかる。10000未満なんてやったら待ってられないので，下のコードでは1000未満にしてある。いい方法はないだろうか。

module Main (main) where

d :: Int -> Int
d n = sum [x | x <- [1..(n `div` 2)], n `mod` x == 0]

euler021 :: Int -> Int
euler021 n = sum $ map (\(a,b) -> a + b) pairs
  where
    pairs = [(a,b) | a <- [1..n], b <- [1..n], a < b, d a == b, d b == a]

main :: IO ()
main = print $ euler021 1000

^o^ >euler021.exe
504

1000未満では 220 と 284 のペアしかないみたいだ。

追記：

いい方法はないだろうか，と書いたらコメントやらトラックバックやらでいろいろ教えてくれた。ありがとうございます。

　cf. http://haskell.g.hatena.ne.jp/nobsun/20080314/p1

おおっ，速い！

追記2：

ううっ，うっかりとエントリに上書きして消してしまった。できるだけ復元したけど元のエントリとは少し違ってるかも。

ってのがあるのか。

　cf. http://projecteuler.net/index.php
　via Life Goes On – はじめました

気が向いたときにはやってみるかな。
とりあえず Problem 1 を内包表記で。

euler0001 :: Int -> Int
euler0001 n = sum [x | x <- [1..(n-1)], or [x `mod` 3 == 0, x `mod` 5 == 0]]

main :: IO ()
main = print $ euler0001 1000

^o^ >runhaskell euler0001.hs
233168