« Project Euler : Problem 42 | トップページ | Project Euler : Problem 44 ~ 五角数 »

2010年8月14日 (土)

Project Euler : Problem 43

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

 

 まずは brute force 版です。

import Data.List (permutations) import ForEuler (listToDex) -- ex : convert [1,2,3,4,5,6,7,8,9,0] => [890,789,678,567,456,345,234] convert :: Integral a => [a] -> [a] convert xs = map listToDex $ loop xs [] where loop [a, b, c] prd = [a, b, c] : prd loop xs@(x : xs') prd = loop xs' (take 3 xs : prd) nums :: [Integer] nums = [listToDex xs | xs@(x : _) <- xss, x /= 0, check xs] where xss = permutations [0 .. 9] -- 辞書順である必要は無いので…… check ns = and [z == 0 | z <- zipWith (rem) (convert ns) divs] where divs = [17, 13, 11, 7, 5, 3, 2] problem043 :: Integer problem043 = sum nums main :: IO () main = print problem043
 10 桁の Pandigital な数を作るのに「順列」を使いました。
 今回は順列の結果が辞書順に並んでいる必要は無いので、自作の "permutation" ではなく "Data.List" モジュールの "permutations" を使いました(こちらの方が速いので……)。
 "convert" 関数はコメントにも書いてあるように [d1, d2, d3, d4, d5, d6, d7, d8, d9, d10] というリストを与えると [d8d9d10, d7d8d9, d6d7d8 .. d2d3d4] といったリストを返します。
 この解き方は順列の結果を総当たりするので非常に遅いです。

 次は Pandigital な数を作っていく方法です。

import Data.List ((\\)) import ForEuler (listToDex) -- 条件に合う Pandigital 数の集合 nums :: [Integer] nums = [listToDex (x : xs) | xs <- xss, let x = 45 - sum xs, x /= 0] where xss = foldl func yss [17, 13, 11, 7, 5, 3, 2] yss = [[a, b] | a <- [0 .. 9], b <- [0 .. 9], a /= b] func xss d = concatMap (makeList d) xss makeList d xs = [ys | x <- [0 .. 9] \\ xs, let ys = x : xs, check ys] where check ys = rem (listToDex $ take 3 ys) d == 0 problem043 :: Integer problem043 = sum nums main :: IO () main = print problem043
 こちらの方法では "makeNewList" 関数が非常に大事な役割を演じています。
 "makeNewList" 関数は整数 d と一桁の整数のリスト xs が与えられると、xs に含まれない数を一つずつ xs の先頭につけ足していって、新しいリストの先頭から 3 桁が d で割りきれるものだけを返します。
 具体的には
> makeNewList 3 [1,2,3] [[0,1,2,3],[6,1,2,3],[9,1,2,3]]
といった具合になります。
 新しいリストを作っていく過程で候補がどんどん絞られていくので、こちらの方法はかなり速く答えが出ます。

 次のように "nums" をちょっと書き換えて GHCi 上で実行すると、実際に候補が絞られていく様子が画面に表示されます。

import Debug.Trace import Data.List ((\\)) import ForEuler (listToDex) -- 条件に合う Pandigital 数の集合 nums :: [Integer] nums = [listToDex (x : xs) | xs <- xss, let x = 45 - sum xs, x /= 0] where xss = foldl func yss [17, 13, 11, 7, 5, 3, 2] yss = [[a, b] | a <- [0 .. 9], b <- [0 .. 9], a /= b] func xss d = trace (show xss) (concatMap (makeNewList d) xss) makeNewList d xs = [ys | x <- [0 .. 9] \\ xs, let ys = x : xs, check ys] where check ys = rem (listToDex $ take 3 ys) d == 0
Main> nums [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8]] [[9,0,1],[1,0,2],[2,0,4],[3,0,6],[4,0,8],[5,1,0],[6,1,2],[7,1,4],[8,1,6],[0,1,7],[9,1,8],[4,2,5],[5,2,7],[6,2,9],[7,3,1],[0,3,4],[9,3,5],[1,3,6],[2,3,8],[3,4,0],[7,4,8],[8,5,0],[0,5,1],[9,5,2],[1,5,3],[3,5,7],[4,5,9],[5,6,1],[7,6,5],[8,6,7],[0,6,8],[1,7,0],[3,7,4],[4,7,6],[5,7,8],[6,8,0],[7,8,2],[0,8,5],[9,8,6],[1,8,7],[2,8,9],[3,9,1],[4,9,3],[6,9,7]] [[3,9,0,1],[9,1,0,2],[5,2,0,4],[1,3,0,6],[3,5,1,0],[8,7,1,4],[4,8,1,6],[0,9,1,8],[0,5,2,7],[2,7,3,1],[7,9,3,5],[0,1,3,6],[9,2,3,8],[2,3,4,0],[1,9,5,2],[7,1,5,3],[8,4,5,9],[2,8,6,7],[6,3,7,4],[2,4,7,6],[4,6,8,0],[0,7,8,2],[2,0,8,5],[5,9,8,6],[7,2,8,9],[0,3,9,1],[1,6,9,7]] [[5,3,9,0,1],[8,9,1,0,2],[3,5,2,0,4],[9,1,3,0,6],[9,3,5,1,0],[7,4,8,1,6],[2,0,9,1,8],[6,0,5,2,7],[6,2,7,3,1],[7,9,2,3,8],[3,1,9,5,2],[6,7,1,5,3],[5,2,8,6,7],[9,2,4,7,6],[9,4,6,8,0],[4,0,7,8,2],[7,5,9,8,6],[5,7,2,8,9],[8,0,3,9,1]] [[7,3,5,2,0,4],[7,9,1,3,0,6],[6,9,3,5,1,0],[5,7,4,8,1,6],[4,2,0,9,1,8],[4,6,2,7,3,1],[6,7,9,2,3,8],[9,5,2,8,6,7],[3,9,2,4,7,6],[2,9,4,6,8,0],[1,4,0,7,8,2],[1,7,5,9,8,6],[3,5,7,2,8,9],[2,8,0,3,9,1]] [[0,9,5,2,8,6,7],[1,9,5,2,8,6,7],[3,9,5,2,8,6,7],[4,9,5,2,8,6,7],[0,3,5,7,2,8,9],[1,3,5,7,2,8,9],[4,3,5,7,2,8,9],[6,3,5,7,2,8,9]] [[3,0,9,5,2,8,6,7],[0,3,9,5,2,8,6,7],[6,0,3,5,7,2,8,9],[0,6,3,5,7,2,8,9]] [4130952867,1430952867,4160357289,1460357289,4106357289,1406357289]
 こんな風に内部データを見たいときには「trace 関数」 は便利ですね。

※「trace 関数」に関してはここを参考にさせて頂きました。

« Project Euler : Problem 42 | トップページ | Project Euler : Problem 44 ~ 五角数 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler : Problem 42 | トップページ | Project Euler : Problem 44 ~ 五角数 »

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

最近のトラックバック

無料ブログはココログ