Magicode
1

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

## 問11

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)]


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座標$が同じもの同士でグルーピングすれば良いと言うこと #### 4. 左斜め下用のリストを作る 3と同様に考え、$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  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

## 末筆ながら

### スキル指標

• すごいH本
• 関数プログラミング実践入門
• 関数プログラミングの楽しみ (挫折中)
がんばって読み切ろう