Ccmmutty logo
Commutty IT
2
0 pv9 min read

【縦横斜めの最大積】一緒に考えませんか? Project Euler

https://cdn.magicode.io/media/notebox/c4768491-c517-4883-9424-3f0ddeebbe09.jpeg

問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座標が同じもので(縦に)グルーピングすれば良い
x座標+y座標x座標 + y座標が同じもの同士でグルーピングすれば良いと言うこと

4. 左斜め下用のリストを作る

3と同様に考え、x座標y座標x座標 - y座標が同じもの同士でグルーピングすれば良い
-- 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
haskell
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 solve

70600674

末筆ながら

ご意見求む!!

型もうまく使えて、Haskell感のある解き方が出来た気がします

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします!

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
  • すごいH本
  • 関数プログラミング実践入門
  • 関数プログラミングの楽しみ (挫折中)
がんばって読み切ろう

Discussion

コメントにはログインが必要です。