Project Eulerをシェル芸で解いてみる(Problem 11)

# 概要
Project Euler[^pe]は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸[^def]による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。
<br>

本記事では、Project EulerのProblem 11を、シェル芸で解いた際の過程を述べる。

# 実行環境
* Arch Linux (x86\_64, 4.3.3-2-ARCH)
* bash (4.3.42, POSIX互換モード)
* GNU coreutils (8.24)
* gawk (4.1.3)

<!---
* bsd-games (2.17)
--->

# 問題文
[原文 ([https://projecteuler.net/problem=11](https://projecteuler.net/problem=11))]

> In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in red.
> 
<div align="center">
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08<br>
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00<br>
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65<br>
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91<br>
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80<br>
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50<br>
32 98 81 28 64 23 67 10 <font color=red>26</font> 38 40 67 59 54 70 66 18 38 64 70<br>
67 26 20 68 02 62 12 20 95 <font color=red>63</font> 94 39 63 08 40 91 66 49 94 21<br>
24 55 58 05 66 73 99 26 97 17 <font color=red>78</font> 78 96 83 14 88 34 89 63 72<br>
21 36 23 09 75 00 76 44 20 45 35 <font color=red>14</font> 00 61 33 97 34 31 33 95<br>
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92<br>
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57<br>
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58<br>
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40<br>
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66<br>
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69<br>
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36<br>
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16<br>
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54<br>
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
</div>
> The product of these numbers is $26 \times 63 \times 78 \times 14 = 1788696$ .
> What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the $20 \times 20$ grid?

[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011))]

> 上の $20 \times 20$ の格子のうち, 斜めに並んだ4つの数字が赤くマークされている.
> 
<div align="center">
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08<br>
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00<br>
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65<br>
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91<br>
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80<br>
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50<br>
32 98 81 28 64 23 67 10 <font color=red>26</font> 38 40 67 59 54 70 66 18 38 64 70<br>
67 26 20 68 02 62 12 20 95 <font color=red>63</font> 94 39 63 08 40 91 66 49 94 21<br>
24 55 58 05 66 73 99 26 97 17 <font color=red>78</font> 78 96 83 14 88 34 89 63 72<br>
21 36 23 09 75 00 76 44 20 45 35 <font color=red>14</font> 00 61 33 97 34 31 33 95<br>
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92<br>
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57<br>
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58<br>
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40<br>
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66<br>
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69<br>
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36<br>
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16<br>
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54<br>
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
</div>
> それらの数字の積は $26 \times 63 \times 78 \times 14 = 1788696$ となる.
> 上の $20 \times 20$ の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?


正答は、注釈[^ans]に記載する。

# 解法
```sh:prob_011.sh
1	#!/bin/sh
2	
3	(cat << EOS
4	08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
5	49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
6	81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
7	52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
8	22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
9	24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
10	32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
11	67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
12	24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
13	21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
14	78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
15	16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
16	86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
17	19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
18	04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
19	88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
20	04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
21	20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
22	20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
23	01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
24	EOS
25	) \
26	| # 20x20格子の出力
27	awk '
28	    {for(i=1; i<=NF; i++){arr[NR,i] = $i}}
29	    END{
30	        for(i=1; i<=NR; i++){for(j=1; j<=NF-3; j++){print arr[i,j], arr[i,j+1], arr[i,j+2], arr[i,j+3]}};
31	        for(i=1; i<=NF; i++){for(j=1; j<=NR-3; j++){print arr[j,i], arr[j+1,i], arr[j+2,i], arr[j+3,i]}};
32	        for(i=1; i<=NR-3; i++){for(j=1; j<=NF-3; j++){print arr[i,j], arr[i+1,j+1], arr[i+2,j+2], arr[i+3,j+3] "\n" arr[i,j+3], arr[i+1,j+2], arr[i+2,j+1], arr[i+3,j]}};
33	    }
34	    ' \
35	| # 横・縦・斜め(左上->右下、右上->左下)の4パターンの組合せの出力
36	tr ' ' '*' \
37	| # 積の算出式の出力
38	bc \
39	| # 積の出力
40	sort -n \
41	| # 積のソート
42	tail -n 1
43	  # 最大値の出力
```

## 解説
まず、横・縦・斜め(左上から右下へ、右上から左下へ)の4パターンについて、4つの数値を組として、格子の走査をおこなっていく。
この処理は、27~33行目のawkによっておこなう。
具体的には、格子を1数値毎に連想配列へ格納し、その連想配列に対して4パターンの走査をおこなうことによって、4つの数値の全組合せを出力している。

そして、出力された全組合せに対して、それぞれ積を求める。
この処理は、36~38行目のtrとbcによっておこなう。
この処理によって、全組合せに対する積を列挙することができる。

最後に、列挙された積のうち、最大値となる値を取り出す。
この処理は、40~42行目のsortとtailによっておこなう。
<br>


以上が、 $20 \times 20$ の格子のうち、上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものを求める方法である。


# 雑記
* 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
* 現在の進捗状況 -> [https://github.com/gin135/Project_Euler/tree/master/sh](https://github.com/gin135/Project_Euler/tree/master/sh)
<br>

* 今回の解法、いつもに増してエレガントじゃない気がする...
    - 27~33行目の数列出力、もっと賢いやり方があるような気がするんだよね...
    - とはいえ、少しググッてみた限りでは、これ以外のやり方は見つからなかった。どうなんだろう...

- - -

[^pe]: About - Project Euler ([https://projecteuler.net](https://projecteuler.net))
[^def]: シェル芸の定義 >> シェル芸 - 上田ブログ ([https://blog.ueda.asia/?page_id=1434](https://blog.ueda.asia/?page_id=1434))
[^ans]: 70600674