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

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

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

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

# 実行環境
* Arch Linux (x86\_64, 4.5.4-1-ARCH)
* bash (4.3.42, POSIX互換モード)
* GNU coreutils (8.25)
* gawk (4.1.3)
<br>

* usp Personal Tukubai(20160402、別解のみ使用)

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

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

> Consider all integer combinations of $a^b$ for $2 \le a \le 5$ and $2 \le b \le 5$:
>
```math
2^2=4,\hspace{0.5em}2^3=8,\hspace{0.5em}2^4=16,\hspace{0.5em}2^5=32 \\
3^2=9,\hspace{0.5em}3^3=27,\hspace{0.5em}3^4=81,\hspace{0.5em}3^5=243 \\
4^2=16,\hspace{0.5em}4^3=64,\hspace{0.5em}4^4=256,\hspace{0.5em}4^5=1024 \\
5^2=25,\hspace{0.5em}5^3=125,\hspace{0.5em}5^4=625,\hspace{0.5em}5^5=3125
```

> If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
>
```math
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
```

> How many distinct terms are in the sequence generated by $a^b$ for $2 \le a \le 100$ and $2 \le b \le 100$?


[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2029](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2029))]
#### 個別のべき乗

> $2 \le a \le 5$ と $2 \le b \le 5$について, $a^b$ を全て考えてみよう:
>
```math
2^2=4,\hspace{0.5em}2^3=8,\hspace{0.5em}2^4=16,\hspace{0.5em}2^5=32 \\
3^2=9,\hspace{0.5em}3^3=27,\hspace{0.5em}3^4=81,\hspace{0.5em}3^5=243 \\
4^2=16,\hspace{0.5em}4^3=64,\hspace{0.5em}4^4=256,\hspace{0.5em}4^5=1024 \\
5^2=25,\hspace{0.5em}5^3=125,\hspace{0.5em}5^4=625,\hspace{0.5em}5^5=3125
```

> これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:
>
```math
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
```

> $2 \le a \le 100$, $2 \le b \le 100$ で同じことをしたときいくつの異なる項が存在するか?


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

# 解法
```sh
1	#!/bin/sh
2	
3	seq 2 100 \
4	| # aの候補列の生成
5	awk '{for(i=2; i<=100; i++){print $0,i}}' \
6	| # a候補列に対して、bの候補列を生成
7	tr ' ' '^' \
8	| # 各組み合わせに関して計算式$a^b$を生成
9	BC_LINE_LENGTH=0 bc \
10	| # 式の計算
11	sort -n \
12	| # 出力を数値順・昇順にソート
13	uniq \
14	| # 重複の除去
15	grep -c ''
16	  # 項数の出力
```

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

```sh
seq 2 100 | awk '{for(i=2; i<=100; i++){print $0,i}}' | tr ' ' '^' | BC_LINE_LENGTH=0 bc | sort -n | uniq | grep -c ''
```

## 解説
まず、解答方針を述べる。

今回の設問では、$a$と$b$の全組み合わせに関して$a^b$を列挙し、重複した値を取り除いた後、項数を求めれば良い。

- - -

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

まず、$a$の候補を生成する。
この処理は、3行目の`seq`を用いておこなう。

次に、生成した$a$の候補に対して、$b$の候補を生成する
この処理は、5行目の`awk`を用いておこなう。

そして、生成した$a$、$b$の組み合わせに対して、$a^b$を算出する。
この処理は、7行目の`tr`と9行目の`bc`を用いておこなう。
まず、各レコードに対して、`tr`で累乗記号を付加する。
その後、`bc`によって$a^b$を算出する。

最後に、一意な項数を求める。
この処理は、11行目の`sort`、13行目の`uniq`、15行目の`grep`を用いておこなう。
まず、重複したレコードを除去するための下準備として、`sort`によって入力を数値順に整列する。
次に、`uniq`によって重複したレコードを除去する。
そして、`grep`によってレコード数を出力する。


以上が、$2 \le a \le 1000$、$2 \le b \le 1000$の範囲において、重複しない$a^b$の項数を求める方法である。


# 参考にしたもの
(特に無し)

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

* @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
    - "Project Euler Problem 29 #シェル芸 - jarp," [http://jarp.does.notwork.org/diary/201602b.html#201602121](http://jarp.does.notwork.org/diary/201602b.html#201602121)
    - シェルのブレース展開を活用して、非常にシンプルな解答をしていらっしゃいます。
    - また、`ruby`によるワンライナー解答も投稿していらっしゃいます。
<br>
<br>

* 今回の問題は、シェルスクリプト(シェル芸)だと簡単！
    - 大量のデータを列挙・整列・重複除去するのは、シェルが得意とする処理だと思う。

* 別解として、usp Tukubaiコマンドを使うと、ちょっとだけシンプルになる...かも？

```sh
#!/bin/bash

loopx <(seq 2 100) <(seq 2 100) \
| # a,bの全組み合わせの列挙
gawk -M '$0=$1^$2' \
| # 各組み合わせに対してa^bを出力(桁数が大きくなるので、MPFRを有効にする)
sort -n \
| # 数値順にソート
uniq \
| # 重複の除去
gyo
  # 項数の出力
```

- - -


[^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]: 9183