« Project Euler : Problem 10 〜 200万以下の素数の和 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (1) »

2010年1月 2日 (土)

Project Euler : Problem 11

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

 

 このブログを見た人の中には、「なぜ、すでに Scheme や Ruby で解いた問題を、また Haskell で解き直しているのだろう?」と思われる方もいらっしゃるかもしれません。
 その理由は、「Haskell らしい考え方や、Haskell らしいコードの書き方」を探すことにあります。
 これまで Haskell で解いた問題では、解法のアルゴリズムは以前のものと変わっていないものがほとんどです。それでも、特定のアルゴリズムを Haskell でコーディングするには、当然 Scheme や Ruby とは違ったアプローチが必要になる事も多いです。
 また、「Haskell らしい書式」に関して、試行錯誤している段階でもあります。

 

 今回の問題ですが、まずは手っ取り早くデータを二次元リストに放り込んで解いてみました。

nums :: [[Int]] nums = [[08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08], [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00], [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65], [52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91], [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80], [24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50], [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70], [67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21], [24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72], [21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95], [78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92], [16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57], [86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58], [19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40], [04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66], [88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69], [04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36], [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16], [20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54], [01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]] -- 数列の生成 same :: Int -> [Int] same i = [i, i, i, i] plus :: Int -> [Int] plus i = [i + n | n <- [0 .. 3]] minus :: Int -> [Int] minus i = [i - n | n <- [0 .. 3]] -- 4 個の数の積 calc :: [Int] -> [Int] -> Int calc xs ys = product $ map ref $ zip xs ys where ref (x, y) = nums !! y !! x -- 横の積の集合 line1 :: [Int] line1 = [calc (plus x) (same y) | x <- [0 .. 16], y <- [0 .. 19]] -- 縦の積の集合 line2 :: [Int] line2 = [calc (same x) (plus y) | x <- [0 .. 19], y <- [0 .. 16]] -- 斜めの積の集合 line3 :: [Int] line3 = [calc (minus x) (plus y) | x <- [3 .. 19], y <- [0 .. 16]] -- 斜めの積の集合 line4 :: [Int] line4 = [calc (plus x) (plus x) | x <- [0 .. 16], y <- [0 .. 16]] problem011 :: Int problem011 = maximum (line1 ++ line2 ++ line3 ++ line4) main = print problem011
 わかりやすさに重点を置いたため、少々長いコードになりました。

 リストより配列の方がデータにアクセスする時間は短いだろうと思い、同じアルゴリズムで「配列版」も作ってみました。

import Data.Array nums :: Array (Int, Int) Int nums = listArray ((0, 0), (19, 19)) [08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08, 49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00, 81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65, 52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91, 22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80, 24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50, 32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70, 67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21, 24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72, 21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95, 78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92, 16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57, 86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58, 19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40, 04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66, 88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69, 04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36, 20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16, 20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54, 01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48] -- 数列の生成 same :: Int -> [Int] same i = [i, i, i, i] plus :: Int -> [Int] plus i = [i + n | n <- [0 .. 3]] minus :: Int -> [Int] minus i = [i - n | n <- [0 .. 3]] -- 4 個の数の積 calc :: [Int] -> [Int] -> Int calc xs ys = product $ map (nums !) $ zip xs ys -- 横の積の集合 line1 :: [Int] line1 = [calc (plus x) (same y) | x <- [0 .. 16], y <- [0 .. 19]] -- 縦の積の集合 line2 :: [Int] line2 = [calc (same x) (plus y) | x <- [0 .. 19], y <- [0 .. 16]] -- 斜めの積の集合 line3 :: [Int] line3 = [calc (minus x) (plus y) | x <- [3 .. 19], y <- [0 .. 16]] -- 斜めの積の集合 line4 :: [Int] line4 = [calc (plus x) (plus x) | x <- [0 .. 16], y <- [0 .. 16]] problem011 :: Int problem011 = maximum (line1 ++ line2 ++ line3 ++ line4) main = print problem011
 結果はと言うと……「リスト版」と「配列版」の実効速度はほとんど一緒でした。扱うデータの量がもっと多くなれば、結果も違ってくるのでしょうか?

 自分なりの「Haskell らしい書式」は、まだまだ見つかっていませんが、「実効速度や行数よりも、わかりやすさやメンテナンスのしやすさを優先していくほうがいいのかな?」という気はしてきています。

« Project Euler : Problem 10 〜 200万以下の素数の和 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (1) »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler : Problem 10 〜 200万以下の素数の和 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (1) »

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

最近のトラックバック

無料ブログはココログ