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

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

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

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

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

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

# 問題文
[原文 ([https://projecteuler.net/problem=30](https://projecteuler.net/problem=30))]
#### Digit fifth powers

> Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:
>
<div align="center">
$1634 = 1^4 + 6^4 + 3^4 + 4^4$<br>
$8208 = 8^4 + 2^4 + 0^4 + 8^4$<br>
$9474 = 9^4 + 4^4 + 7^4 + 4^4$
</div>

> As $1 = 1^4$ is not a sum it is not included.
> The sum of these numbers is $1634 + 8208 + 9474 = 19316$.
> Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.


[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2030](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2030))]
#### 各桁の5乗

> 驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.
>
<div align="center">
$1634 = 1^4 + 6^4 + 3^4 + 4^4$<br>
$8208 = 8^4 + 2^4 + 0^4 + 8^4$<br>
$9474 = 9^4 + 4^4 + 7^4 + 4^4$
</div>

> ただし, $1=1^4$は含まないものとする. この数たちの和は $1634 + 8208 + 9474 = 19316$ である.
> 各桁を$5$乗した数の和が元の数と一致するような数の総和を求めよ.

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

# 解法
```sh
1	#!/bin/sh
2	
3	yes 高須クリニック \
4	| # お約束のやつ
5	awk '{s+=9^5; if(s<10^NR){exit}} END{print NR}' \
6	| # 各桁^5の総和の最大桁数の出力
7	awk '{for(i=1;i<=$0;i++){printf("9")}; print ""}' \
8	| # 探索範囲の終端の出力
9	xargs -Iend seq 0 end \
10	| # 0から999999までの整数の出力
11	grep -v '^1\{1,\}$' \
12	| # 例外(1のみで構成された値)の除去
13	awk -v FS='' '{s=0; for(i=1;i<=NF;i++){s+=$i^5}; print $0,s}' \
14	| # 整数および各桁^5の総和の出力
15	awk '$1==$2' \
16	| # 元の整数と累乗の総和が一致するレコードの抽出
17	awk '{s+=$1} END{print s}'
18	  # 抽出した整数の総和の出力
```

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

```sh
yes 高須クリニック | awk '{s+=9^5; if(s<10^NR){exit}} END{print NR}' | awk '{for(i=1;i<=$0;i++){printf("9")}; print ""}' | xargs -Iend seq 0 end | grep -v '^1\{1,\}$' | awk -v FS='' '{s=0; for(i=1;i<=NF;i++){s+=$i^5}; print $0,s}' | awk '$1==$2' | awk '{s+=$1} END{print s}'
```

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

今回の設問では、考えられる組み合わせを全て列挙し、その中から各桁を5乗した値の和が元の値と一致するものを抽出し、和を求めれば良い。
ただし、設問で記載されている情報だけでは、探索する範囲を定めることができない。
そのため、前準備として、各桁を5乗した値の和が、元の値を超えないための、最大桁数を調べる。

- - -

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

始めに、解答方針で述べたとおり、探索範囲を決定する。
この処理は、3行目の`yes`、5行目と7行目の`awk`を用いておこなう。
まず、`yes`によって、適当な入力を生成する。
次に、生成した入力を利用し、`awk`によって探索範囲を決定する。
具体的には、5行目の`awk`で、各桁を5乗した値の和が元の値を超えないための最大桁数を、7行目の`awk`で、探索範囲の終端を出力する。

そして、解答方針で始めに述べたとおりに処理を進める。

まず、考えられる組み合わせを、全て列挙する。
この処理は、9行目の`xargs`および`seq`を用いておこなう。
7行目の`awk`によって得られた探索範囲の終端を、`xargs`によって`seq`へ引数として渡し、全組み合わせを列挙する。

次に、設問で言及されている例外(1のみで構成された値)を除去する。
この処理は、11行目の`grep`を用いておこなう。

そして、各桁を5乗した値の和と、元の値が一致する組み合わせを抽出する。
この処理は、13行目と15行目の`awk`を用いておこなう。
13行目の`awk`で各桁を5乗した値の和を2フィールド目に出力した後、15行目の`awk`によって元の値と一致する組み合わせを抽出する。

最後に、抽出した組み合わせの総和を求める。
この処理は、17行目の`awk`を用いておこなう。


以上が、各桁を5乗した値の和が元の値と一致するものの総和を求める方法である。


# 参考にしたもの

(特に無し)

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

* @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
    - "Project Euler Problem 30 #シェル芸 - jarp," [http://jarp.does.notwork.org/diary/201602b.html#201602151](http://jarp.does.notwork.org/diary/201602b.html#201602151)
    - 該当する値が最大で6桁になることを利用し、`awk`でよりシンプルな解答をしていらっしゃいます。
<br>
<br>

* 今回の問題も、 @eban さんの解答と大部分が同じになってしまったorz
    - なので、完全なワンライナーにして、ちょっとだけオリジナリティを出してみた...つもり。
    - てか、`awk`に頼りすぎかも＞＜

* 今回問題を解くにあたり、`xargs`の`-I`オプションの`replace-str`に文字列が使用可能であることを、初めて知った。
    - @mutz0623 さんの資料↓によれば、`xargs`は特に指定されない限り、内部で`/bin/echo`を呼び出しているとのこと。
    - <blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">xargsコマンドの話.pdf <a href="https://t.co/36Gd6R5DEZ">https://t.co/36Gd6R5DEZ</a> <a href="https://twitter.com/hashtag/%E3%82%B7%E3%82%A7%E3%83%AB%E8%8A%B8?src=hash">#シェル芸</a></p>&mdash; むっつー (@mutz0623) <a href="https://twitter.com/mutz0623/status/543694644152782849">2014年12月13日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
    - きちんと調べてはいないけれど... `xargs`って、変数`replace-str`に引数を格納して、単に`echo`しているだけとか？

- - -

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