LoginSignup
6
6

More than 5 years have passed since last update.

@gin_135

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

Last updated at Posted at 2016-01-19

概要

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

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

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

実行環境

  • 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=18)]

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, $3 + 7 + 4 + 9 = 23$.
Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

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

以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では $3 + 7 + 4 + 9 = 23$.
以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.

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

解法

prob_018.sh
1   #!/bin/bash
2   
3   (cat <<EOS
4   75
5   95 64
6   17 47 82
7   18 35 87 10
8   20 04 82 47 65
9   19 01 23 75 03 34
10  88 02 77 73 07 63 67
11  99 65 04 28 06 16 70 92
12  41 41 26 56 83 40 80 70 33
13  41 48 72 33 47 32 37 16 94 29
14  53 71 44 65 25 43 91 52 97 51 14
15  70 11 33 28 77 73 17 78 39 68 17 57
16  91 71 52 38 17 14 91 43 58 50 27 29 48
17  63 66 04 68 89 53 67 30 73 16 69 87 40 31
18  04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
19  EOS
20  ) \
21  | # 三角形の出力
22  tac > /tmp/$$_1_data;
23    # 三角形を逆順に出力
24  
25  for n in `seq 1 14`; do
26      awk '
27          ORS="";
28          NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}}
29          NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"}
30          2 < NR {ORS="\n"; print}
31          ' \
32      < /tmp/$$_${n}_data > /tmp/$$_$[${n}+1]_data;   # 三角形を底辺から順に大きい数値を合算
33  done;
34  
35  cat /tmp/$$_$[${n}+1]_data;  # 最大値の出力
36  rm /tmp/$$_*_data;      # 一時ファイルの削除

以下、コマンドライン上での実行用コードである。

(cat <<EOS
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
EOS
) | tac > /tmp/$$_1_data; for n in `seq 1 14`; do awk ' ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' < /tmp/$$_${n}_data > /tmp/$$_$[${n}+1]_data; done; cat /tmp/$$_$[${n}+1]_data; rm /tmp/$$_*_data

解説

初めに、解答方針を述べる。

今回の問題では、三角形を頂点からではなく、底辺から順に最大となる値を集計していく。
底辺から順に足しあわせていき、頂点に辿り着いた場合、その時の値は自ずと最大値となる。

具体例として、設問の三角形を4段に簡略化した、次のモデルで考える。

75
95  64
17  47  82
18  35  87  10

ここで、3段目と最下段(底辺)である4段目に着目する。
頂点から順に数を足し合わせて、3段目まで辿り着いたとする。
この場合、和を最大値にするには、4段目で隣り合う2値のうち、大きい方を3段目の値に足し合わせる必要がある。

例として3段目の最左にある17を挙げる。
17に足し合わせる4段目の候補は、18と35である。
この隣り合う2つの値のうち、大きい方は35である。
つまり、3段目の17に対して和を最大値とするためには、4段目の35を足し合わせれば良い。
同様にして、3段目の47と82にも、和が最大となる4段目の値を足し合わせる。

以下、3段目に対して和が最大となる4段目の値を足し合わせた状態の三角形である。

75
95  64
17+35  47+87  82+87

↓

75
95  64
52  134  169

3~4段目と同様にして、2段目に対しても演算をおこなう。
以下、2段目に対して和が最大となる3段目の値を足し合わせた状態の三角形である。

75
95+134  64+169

↓

75
229  233

最後に、1段目に対して演算をおこなう。
以下、1段目に対して和が最大となる2段目の値を足し合わせた状態の値である。

75+233

↓

308

このとき、1段目の値として算出された308は、自ずと頂点から最下段まで移動した際の、最大和となっている。
よって、4段の三角形の場合、最大値は308である。

今回の問題では、この手法を実装すれば良い。

次に、ソースコードの解説を述べる。

まず、設問の三角形を逆順に出力する。
これは、シェルスクリプト(シェル芸)では、データは基本的に上から下へと順に処理する為である。
この処理は、22行目のtacを用いておこなう。
(tacコマンドが利用できない場合は、@bsdhack さんのファイルの逆順出力の記事を参照してください。)
また、今回の解法1では、普通の手法では一連のコマンドをパイプで1つに接続することはできなかった。
そのため、tacで逆順に出力した結果を、一時ファイルへ書き込む。

そして、逆順に出力した三角形を、底辺(逆順に出力したため、正確には最上段)から、次の段が最大値となるように足し合わせる。
この処理は、25~33行目のawkを用いておこなう。
具体的には、入力の2段目(最上段の次の段)の各値において、1行目(その時点での最上段)の隣り合う値のうち、最大となる和を出力している。
また、この処理をfor構文によって(段数-1)回繰り返すことによって、頂点まで集計をおこなう。
各段における三角形の状態を保持するために、入力および演算結果は、一時ファイルを通じて読み書きする。

最後に、最大値を出力する。
この処理は、35行目のcatを用いておこなう。
具体的には、 $n=15$ (全段の演算が完了した状態)の一時ファイルを出力すれば良い。
この一時ファイルに書き込まれている値が、自ずと最大値となっている。

以上が、三角形を頂点から下まで移動するときの最大和を求める方法である。

解法2

prob_018_unicage.sh
1   #!/bin/sh
2   
3   (cat <<EOS
4   75
5   95 64
6   17 47 82
7   18 35 87 10
8   20 04 82 47 65
9   19 01 23 75 03 34
10  88 02 77 73 07 63 67
11  99 65 04 28 06 16 70 92
12  41 41 26 56 83 40 80 70 33
13  41 48 72 33 47 32 37 16 94 29
14  53 71 44 65 25 43 91 52 97 51 14
15  70 11 33 28 77 73 17 78 39 68 17 57
16  91 71 52 38 17 14 91 43 58 50 27 29 48
17  63 66 04 68 89 53 67 30 73 16 69 87 40 31
18  04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
19  EOS
20  ) \
21  | # 三角形の出力
22  tac \
23  | # 三角形を逆順に出力
24  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
25  | # 14段目における最大値の集計
26  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
27  | # 13段目の集計
28  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
29  | # 12段目の集計
30  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
31  | # 11段目の集計
32  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
33  | # 10段目の集計
34  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
35  | # 9段目の集計
36  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
37  | # 8段目の集計
38  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
39  | # 7段目の集計
40  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
41  | # 6段目の集計
42  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
43  | # 5段目の集計
44  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
45  | # 4段目の集計
46  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
47  | # 3段目の集計
48  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' \
49  | # 2段目の集計
50  awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}'
51    # 1段目の集計(最大値の出力)

以下、コマンドライン上での実行用コードである。

(cat <<EOS
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
EOS
) | tac |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}' |
awk 'ORS=""; NR == 1 {for(i=1; i<=NF; i++){arr[i]=$i}} NR == 2 {for(i=1; i<=NF; i++){print ($i+=(arr[i] > arr[i+1]) ? arr[i] : arr[i+1]), ""}; print "\n"} 2 < NR {ORS="\n"; print}'

解説2

解答方針自体は、解法1と同様である。

しかし、解法2では、ユニケージ開発手法(参考1)を参考にして、繰り返し構文を用いない記法としている。
具体的には、繰り返し構文の代わりに、ある段における最大値を求めるコードを14回実行している。
この手法によって、一時ファイルを利用する必要が無く、また平易なパイプラインを実現している。

参考にしたもの

  1. "ユニケージエンジニアの作法その一 forやwhileなどの繰り返し構文の使用は控える - UEC - usp engineers' community - UECジャーナル" 〈https://uec.usp-lab.com/JOURNAL/CGI/JOURNAL.CGI?POMPA=SAHOU_journal02〉

雑記

  • 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺

  • 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh

  • とうとうbash依存のスクリプトを書いてしまった:feelsgood:

    • しかも一時ファイルまで使ってしまった:finnadie:
    • POSIX原理主義ではないけれど、出来ればshのみで完結させたかったです...
    • 移植性、だいじ。
    • でも、何だかとっても負けた気分...

  • シェル芸って、再帰処理には向いていない(というか不可能？)な気がする。

    • シェル芸おじさんこと@ryuichiueda さんに、こんなアドバイスを頂きました。
    • ...が、僕のうんコーディング力では実現できなかった＞＜ せっかくアドバイスしてくださったのに、申し訳ないです...

  • ユニケージ開発手法にしたがって書いたコード、見た目がすごい...

    • ただ、コードの分かりやすさという点では、素晴らしい手法だと思う。
    • さすがに今回のは、ちょっと極端すぎるかもしれないけれど...

  • シェル芸、特にユニケージ開発手法って、ある意味とても抽象化されたプログラミング手法なのかもしれない。

    • 今回の解法で一番重要なコードは、最下段での最大値を求めるawkの部分。
    • このアルゴリズム部分さえ掴めれば、ある意味正答できたみたいなもの。
    • だからこそ、上から下への可読性を重視し、今回の肝であるawkコードに着目しているユニケージ開発手法は、プログラミングの本質を突いているように感じた。
    • (というポエムです:heart:)

  • (『ユニケージ原論』は買ったけれど、まだきちんと読んでいないです。ユニケージの理論を勘違いしていたらすみません...)

  1. About - Project Euler (https://projecteuler.net) ↩

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

  3. 1074 ↩

6
6
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
6