« Project Euler : Problem 31 ~ 両替問題 | トップページ | Project Euler : Problem 33 »

2010年6月20日 (日)

Project Euler : Problem 32

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

 

 解き方は、以前の Ruby 版と同じです。
 まずは総当たりバージョン。

import Data.List -- Pandigital な String か? isPandigitalStr :: String -> Bool isPandigitalStr str = and $ zipWith (==) (sort str) "1234567890" findProduct :: [Int] -> [Int] -> [Int] findProduct as bs = [c | a <- as, b <- bs, let c = a * b, check a b c] where check a b c = c < 10000 && (isPandigitalStr $ concatMap show [a, b, c]) problem032 :: Int problem032 = sum $ nub $ xs ++ ys where xs = findProduct [1 .. 9] [1234 .. 9876] -- 1 桁と 4 桁の積 ys = findProduct [12 .. 98] [123 .. 987] -- 2 桁と 3 桁の積 main :: IO () main = print problem032

 

 次は「順列」を使って、数字が重複しないようにして「積」を求める方法。

import Data.List -- Pandigital な String か? isPandigitalStr :: String -> Bool isPandigitalStr str = and $ zipWith (==) (sort str) "1234567890" -- 順列 ( 辞書順 ) -- ex : permutation [1..3] 2 => [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]] permutation :: [a] -> Int -> [[a]] permutation ns n = perm n (length ns - 1) [(ns, [])] where perm 0 _ ts = [a | (_, a) <- ts] perm c n ts = perm (c - 1) (n - 1) $ concatMap (f n) ts f n (xs, ys) = [(as ++ bs, ys ++ [b]) | i <- [0 .. n], let (as, b : bs) = splitAt i xs] -- リストを整数に変換 listToDex :: Integral a => [a] -> a listToDex ns = foldl calc 0 ns where calc x y = x * 10 + y findProduct :: Int -> Int -> [Int] findProduct m n = [c | (a, b) <- makePair, let c = a * b, check a b c] where check a b c = c < 10000 && (isPandigitalStr $ concatMap show [a, b, c]) makePair = [(listToDex as, listToDex bs) | as <- perm1, bs <- perm2 as] perm1 = permutation [1 .. 9] m perm2 as = permutation ([1 .. 9] \\ as) n problem032 :: Int problem032 = sum $ nub $ (findProduct 1 4) ++ (findProduct 2 3) main :: IO () main = print problem032

« Project Euler : Problem 31 ~ 両替問題 | トップページ | Project Euler : Problem 33 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 32:

« Project Euler : Problem 31 ~ 両替問題 | トップページ | Project Euler : Problem 33 »

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

最近のトラックバック

無料ブログはココログ