More than 5 years have passed since last update.

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

Last updated at 2016-01-20Posted at 2016-01-13

概要

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

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

本記事では、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)

問題文

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

In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in red.

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

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

上の $20 \times 20$ の格子のうち, 斜めに並んだ4つの数字が赤くマークされている.

> それらの数字の積は $26 \times 63 \times 78 \times 14 = 1788696$ となる. > 上の $20 \times 20$ の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?

正答は、注釈³に記載する。

解法

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によっておこなう。

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

雑記

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

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

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up