« Project Euler : Problem 50 | トップページ | Project Euler : Problem 52 »

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 して、その先頭要素だけを取り出す」というパターンが使えるので、非常に重宝しています。

« Project Euler : Problem 50 | トップページ | Project Euler : Problem 52 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/49777135

この記事へのトラックバック一覧です: Project Euler : Problem 51 ~ 8個の素数:

« Project Euler : Problem 50 | トップページ | Project Euler : Problem 52 »

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            
フォト

最近のトラックバック

無料ブログはココログ