2
・0 pv・9 min read
【縦横斜めの最大積】一緒に考えませんか？ Project Euler
問11
以下の20×20グリッドで同じ方向（上、下、左、右、または斜め）に隣接する4つの数字の積の最大値は？
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
Project Euler ※解法の公開は問1～100のみ可
考え方
それぞれの値に座標をつけることで、縦横斜めに走査する
例 以下のグリッドを考える
A B C D
E F G H
I J K L
M N O P
1. 横に見る
[[A, B, C, D], [E, F, G, H], [I, J, K, L],[M, N, O, P]]
2. 縦に見る
[[A, E, I, M], [B, F, J, N], [C, G, K, O], [D, H, L, P]]
3. 右斜め下に見る
[[M], [I, N], [E, J, O], [A, F, K, P], [B, G, L], [D]]
4. 左斜め下に見る
[[A], [B, E], [C, F, I], [D, G, J, M], [H, K, N], [L, O], [P]]
これらのリストを連結してそれぞれのリストの中の最大積を求め、一番大きい値が答えになる
座標をつける
型に名前をつける
-- 座標 (x, y)
type Cell = (Int, Int)
-- 与えられた値に座標をつけたもの
type Grid = [(Cell, Int)]
先に[(0, 0), (0, 1)..]のような座標のリストを作ることでzipで簡単に作成できる
cells :: [Cell]
cells = [(x, y) | y <- [0..19], x <- [0..19]]
grid :: Grid
grid = zip cells $ map read (words gridString)
-- 与えられた数字の表
gridString :: String
gridString = "08 02 22 97 ～ 67 48"
4パターンのリストを作りたい
1. 横用のリストを作る
y座標が同じもので(横に)グルーピング
2. 縦用のリストを作る
x座標が同じもので(縦に)グルーピング
3. 右斜め下用のリストを作る
A B C D
E F G H ← x座標を1つマイナス
I J K L ←← x座標を2つマイナス
M N O P ←←← x座標を3つマイナス
こうずらしてx座標が同じもので(縦に)グルーピングすれば良い
→ が同じもの同士でグルーピングすれば良いと言うこと
4. 左斜め下用のリストを作る
3と同様に考え、が同じもの同士でグルーピングすれば良い
-- 4パターンに応じた型を定義する
data Coordinates = Horizon | Vertical | LowerR | LowerL
-- 指定した座標値を返す関数
select :: Coordinates -> (Int, Int) -> Int
select Horizon (x, y) = y
select Vertical (x, y) = x
select LowerR (x, y) = x + y
select LowerL (x, y) = x - y
同じ値でグルーピングするには、ソートして連続する値をまとめればいい
getRows :: Coordinates -> [((Int, Int), Int)] -> [[Int]]
getRows c = map (map snd) . groupBy (\(cell,_) (cell2, _) -> select c cell == select c cell2) . sortOn (\(cell, _) -> select c cell)
最後に適用しているmap (map snd)は座標の値は必要ないので捨てたかっただけ
リスト作成
-- 横で見る
horizon :: [[Int]]
horizon = getRows Horizon grid
-- 縦で見る
vertical :: [[Int]]
vertical = getRows Vertical grid
-- 右下に斜めで見る
lowerR :: [[Int]]
lowerR = getRows LowerR grid
-- 左下に斜めで見る
lowerL :: [[Int]]
lowerL = getRows LowerL grid
別にまとめて作ればいいのだが、わかりやすさのため
リストの中の連続する4つの数値での最大の積を取得する関数
簡潔に済ます
少し面白いアルゴリズムを
【積最大の隣接】
で作ったので今回は深く考えない
getMax :: [Int] -> Int
getMax xs = maximum $ map (product . take 4) $ tails xs
import Data.List (sortBy, sortOn, groupBy, tails)
-- 読み込み
gridString :: [Char]
gridString = "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"
type Cell = (Int, Int)
type Grid = [(Cell, Int)]
cells :: [Cell]
cells = [(x, y) | y <- [0..19], x <- [0..19]]
grid :: Grid
grid = zip cells $ map read (words gridString)
-- 座標で連結
data Coordinates = Horizon | Vertical | LowerR | LowerL
-- 指定した座標(x or y)のみを残す
select :: Coordinates -> (Int, Int) -> Int
select Horizon (x, y) = y
select Vertical (x, y) = x
select LowerR (x, y) = x + y
select LowerL (x, y) = x - y
-- ソートしてグルーピイング
getRows :: Coordinates -> [((Int, Int), Int)] -> [[Int]]
getRows c = map (map snd) . groupBy (\(cell,_) (cell2, _) -> select c cell == select c cell2) . sortOn (\(cell, _) -> select c cell)
-- 横で見るリスト
horizon :: [[Int]]
horizon = getRows Horizon grid
-- 縦で見るリスト
vertical :: [[Int]]
vertical = getRows Vertical grid
-- 右下に斜めで見るリスト
lowerR :: [[Int]]
lowerR = getRows LowerR grid
-- 左下に斜めで見るリスト
lowerL :: [[Int]]
lowerL = getRows LowerL grid
-- リストの中から連続する4つの積の最大値を取得する関数
getMax :: [Int] -> Int
getMax xs = maximum $ map (product . take 4) $ tails xs
-- 解答
solve :: Int
solve = maximum $ map getMax $ horizon ++ vertical ++ lowerR ++ lowerL
print solve70600674
末筆ながら
ご意見求む!!
型もうまく使えて、Haskell感のある解き方が出来た気がします
Haskellerさんへ
計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！
スキル指標
実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
- すごいH本
- 関数プログラミング実践入門
- 関数プログラミングの楽しみ (挫折中)
がんばって読み切ろう