« 2010年9月 | トップページ | 2010年11月 »

2010年10月

2010年10月29日 (金)

Project Euler : Problem 53

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 まずは、brute force 版。何も考えず、問題を素直に解きました。

import ForEuler problem053 :: Int problem053 = length $ filter (> 1000000) combs where combs = [combinationSize n r | n <- [1 .. 100], r <- [1 .. n]] main :: IO () main = print problem053
 これでも、最適化オプションを付けてコンパイルすれば、うちの非力なノートパソコンでも約 0.1 秒ほどで答えが出ます。

 ここで一工夫。
 先ほどのコードでは、"combinationSizse 関数" の内部で階乗の計算が繰り返し行われています。そこで階乗の計算結果をメモ化してみました。

import Data.Array factorial :: Integer -> Integer factorial n = facts ! n where facts = listArray (0, 100) (1 : [factorial' x | x <- [1 .. 100]]) factorial' x = x * factorial (x - 1) combSize :: Integer -> Integer -> Integer combSize n r = div (factorial n) (factorial r * factorial (n - r)) problem053 :: Int problem053 = length $ filter (> 1000000) combs where combs = [combSize n r | n <- [1 .. 100], r <- [1 .. n]] main :: IO () main = print problem053
 これだと計算の無駄な繰り返しが無くなるので、うちのパソコンで約 0.03 秒で答えが出ます。かなり高速化されました。

 今度はちょっと考え方を変えてみます。
 次の結果を見てください。

> map (combinationSize 10) [0..10] > [1,10,45,120,210,252,210,120,45,10,1]
 組み合わせの式の定義からも分かることですが、nCr = nC(n-r) が成り立ちます。
 また、r が n/2 に達するまでは nCr は大きくなっていき、r が n/2 を越えると対照的に小さくなっていきます。
 このことから、r を 0 から小さい順に調べていって、nCr0 が初めて 1000000 を越えた場合、r0 ≦ r ≦ (n - r0) の範囲にある r では、必ず nCr > 1000000 が成立します。
 ということは、特定の n に対する r0 さえ見つけてしまえば、nCr > 1000000 が成立する場合の数が分かることになります。
import ForEuler -- nCr > m となる r の数 count :: Integer -> Integer -> Integer count n m = if null rs then 0 else n - 2 * (head rs) + 1 where -- rs : nCr > m となる r の集合の前半 rs = filter (\x -> combinationSize n x > m) [0 .. (div n 2)] problem053 :: Integer problem053 = sum $ map (`count` 1000000) [1 .. 100] main :: IO () main = print problem053
 今回は計算量が少ないので、階乗の計算をメモ化しなくても十分速いです。うちのパソコンで約 0.01 秒で答えが出ました。

 Project Euler って、コーディングの知識も要求されるけど、うまい解法を見つけることがもっと重要かも……。

2010年10月25日 (月)

Project Euler : Problem 52

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 これまた解法は "Ruby 版" と一緒なので、詳しくはこちらをご覧ください。

import ForEuler import Data.List check :: Integer -> Bool check n = and [ns == conv x | x <- map (* n) [2..6]] where conv = sort . dexToList ns = conv n problem052 :: Integer problem052 = head $ filter check [123456 ..] main :: IO () main = print problem052

2010年10月18日 (月)

Project Euler : Problem 51 ~ 8個の素数

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 アルゴリズムは「Ruby 版」とほぼ同じなので、考え方に関してはこちらをご覧ください。

import ForEuler -- findPos xs es -- * xs 内での es の各要素の位置を xs の index のリストで返す -- * ex: findPos [0,1,0,2,3] [0,1,2] => [[0,2], [1], [3]] findPos :: Eq a => [a] -> [a] -> [[Int]] findPos xs es = [i | i <- map (findPos' xs) es, i /= []] where findPos' xs e = [i | (x, i) <- zip xs [0 ..], x == e] -- setElems e xs is -- * xs 内の is で示される位置の要素を e に置き換える -- * ex: setElems 0 [1,2,3,4] [1,2] => [1,0,0,4] setElem :: a -> [a] -> [Int] -> [a] setElem e xs is = foldl (setElem' e) xs is where setElem' e xs i = as ++ (e : bs) where (as, _ : bs) = splitAt i xs -- makeNewPrimes n is -- * n の is で示される位置の数字を 0 〜 9 で置き換えたもののうち、素数 -- だけをリストにして返す -- * ex: makeNewPrimes 56003 [2,3] -- => [56003,56113,56333,56443,56663,56773,56993] makeNewPrimes :: Int -> [Int] -> [Int] makeNewPrimes n is = filter isPrime ns where ns = [listToDex xs | xs <- map func [0 .. 9], head xs /= 0] func e = setElem e (dexToList n) is problem051 :: [Int] problem051 = head $ filter ((== 8) . length) $ concatMap check primes where check p = map (makeNewPrimes p) $ findPos (dexToList p) [0,1,2] main :: IO () main = print problem051

 Haskell で「初めて〜になるものを探す」といった問題を解く場合、今回のコードのように、「無限リストを特定の条件で filter して、その先頭要素だけを取り出す」というパターンが使えるので、非常に重宝しています。

2010年10月14日 (木)

Project Euler : Problem 50

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 まず、問題にも書いてある 100 未満の場合で考えてみます。
 2 から始めて合計が 100 未満になる素数は [2,3,5,7,11,13,17,19] の 8 個になります。
 これらの数字から連続する部分を切り出し、合計を考えると

個数:(リスト, 合計) 8 個:([2,3,5,7,11,13,17,19], 77) 7 個:([2,3,5,7,11,13,17], 58), ([3,5,7,11,13,17,19], 75) 6 個:([2,3,5,7,11,13], 41), ([3,5,7,11,13,17], 56), ([5,7,11,13,17,19], 72) 5 個:([2,3,5,7,11], 28), ([3,5,7,11,13], 39), ([5,7,11,13,17], 53) ...
となっていきます。
 この中で 41 が初めて素数になるので、この場合の答えは 41 となります。

 この流れをそのままプログラミングしたのが次のコードです。

import ForEuler (primes, isPrime) -- ex : parts [1 .. 5] 3 => [[1,2,3],[2,3,4],[3,4,5]] parts :: [a] -> Int -> [[a]] parts xs n = take (length xs - n + 1) $ map (take n) $ iterate tail xs problem050 :: Int -> Int problem050 n = head $ filter isPrime $ map sum ps1 where ps1 = concatMap (parts ps2) $ reverse [1 .. length ps2] ps2 = take count primes count = length $ takeWhile (< n) primeSums where primeSums = tail $ scanl (+) 0 primes main :: IO () main = print $ problem050 1000000

2010年10月 7日 (木)

Project Euler : Problem 49

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 アルゴリズムは「Ruby 版」と同じなので、詳しい説明はこちらをご覧ください。

import ForEuler (primes, dexToList, combination) import Data.List (groupBy, sortBy, sort) import Data.Ord (comparing) -- nss = [[1021,1201,2011],[1013,1031,1103,1301,3011] .. ] nss :: [[Int]] nss = [map fst a | a <- groupBy pred ps2, length a >= 3] where pred (_, x) (_, y) = x == y -- ps1 : 四桁の素数のリスト ps1 = takeWhile (< 10000) $ dropWhile (< 1000) primes -- ps2 : 素数とその成分のタプルを成分順にソートしたリスト ps2 = sortBy (comparing snd) [(p, sort $ dexToList p) | p <- ps1] problem049 :: [(Int, Int, Int)] problem049 = concatMap func nss where func ns = [(a, b, c) | [a, b] <- combination ns 2, let c = 2 * b - a, elem c ns] main :: IO () main = print problem049

2010年10月 6日 (水)

Project Euler : Problem 48

 問題はこちらをご覧ください。

 

 Haskell は Ruby や Scheme と同様、整数の桁数に制限がありません。というわけで、今回も何の工夫もしていません。

problem048 :: Integer problem048 = rem (sum [x ^ x | x <- [1 .. 1000]]) (10 ^ 10) main :: IO () main = print problem048

« 2010年9月 | トップページ | 2010年11月 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ