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

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

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

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

# 実行環境
* Arch Linux (x86\_64, 4.6.2-1-ARCH)
* bash (4.3.42)
* GNU coreutils (8.25)
* gawk (4.1.3)
<br>
* usp Personal Tukubai (20160402、別解のみ使用)

<!---
<br>
* bsd-games (2.17)
* curl (7.47.0)
* usp Personal Tukubai (20160402)
--->

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

> In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
> $\hspace{3em}$1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
> It is possible to make £2 in the following way:
> 
> ```math
> 1\times £1 + 1\times 50p + 2\times 20p + 1\times 5p + 1\times 2p + 3\times 1p
> ```
> How many different ways can £2 be made using any number of coins?


[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031))]
#### 硬貨の和

> イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
> 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
> 以下の方法で£2を作ることが可能である．
> $1\times £1 + 1\times 50p + 2\times 20p + 1\times 5p + 1\times 2p + 3\times 1p$
> これらの硬貨を使って£2を作る方法は何通りあるか?


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

# 解法
```sh
1	#!/bin/sh
2	
3	(\
4	    awk 'BEGIN{for(i=0;i<=200;i++){print i}}' \
5	    | # 1p組の生成
6	    awk '{for(i=0;i<=200;i+=2){print $0,i}}' \
7	    | # 2p組の生成
8	    awk '{for(i=0;i<=200;i+=5){print $0,i}}' \
9	    | # 5p組の生成
10	    awk '{for(i=0;i<=200;i+=10){print $0,i}}' \
11	    | # 10p組の生成
12	    awk '{for(i=0;i<=200;i+=20){print $0,i}}' \
13	    | # 20p組の生成
14	    awk '{for(i=0;i<=200;i+=50){print $0,i}}' \
15	    | # 50p組の生成
16	    awk '{for(i=0;i<=200;i+=100){print $0,i,0}}';
17	      # 100p組の生成
18	    echo 0 0 0 0 0 0 0 200
19	      # 200p組の生成
20	) \
21	|
22	awk '{s=0;for(i=1;i<=NF;i++){s+=$i};cnt[s]++} END{print cnt[200]}'
23	  # 合計が200になる組み合わせの集計
```

以下、コマンドライン上での実行用コードである。
**※このコードは、実行結果が出るまで、非常に時間が掛かります！**

```sh
(awk 'BEGIN{for(i=0;i<=200;i++){print i}}' | awk '{for(i=0;i<=200;i+=2){print $0,i}}' | awk '{for(i=0;i<=200;i+=5){print $0,i}}' | awk '{for(i=0;i<=200;i+=10){print $0,i}}' | awk '{for(i=0;i<=200;i+=20){print $0,i}}' | awk '{for(i=0;i<=200;i+=50){print $0,i}}' | awk '{for(i=0;i<=200;i+=100){print $0,i,0}}'; echo 0 0 0 0 0 0 0 200) | awk '{s=0;for(i=1;i<=NF;i++){s+=$i};cnt[s]++} END{print cnt[200]}'
```

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

今回の問題では、**愚直な**方法を用いる。
単純に、考えられる組み合わせを列挙し、その中から合計が200となるものの数を求める。

- - -

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

まず、考えられる組み合わせを列挙する。
各硬貨につき、単独で200pを超えない金額を生成し、それらを総掛けする。
この処理は、3~20行目において、`awk`と`echo`を用いておこなう。
ここでは単純に、`awk`を利用して、1pから順に総掛けをおこなっている。
ただし、200p(€2)を用いる組み合わせは、200p硬貨一枚のみである。
そのため、200pは総掛けをおこなわず、単純に`echo`で200pのみを用いる組み合わせを生成している。

そして、列挙した組み合わせに対して、合計が200となるものの数を集計する。
この処理は、22行目の`awk`を用いておこなう。

以上が、イギリスで使用されている硬貨を用いて、合計が€2となる組み合わせを求める方法である。

# 参考にしたもの

(特に無し)

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

* @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
    - "Project Euler Problem 31 #シェル芸 - jarp," [http://jarp.does.notwork.org/diary/201602b.html#201602141](http://jarp.does.notwork.org/diary/201602b.html#201602141)
    - 部分和問題として捉えることで、非常に簡潔かつ高速な解答をしていらっしゃいます。
<br>
<br>

* 今回は部分和集合の問題。
    - 解法が確立されている問題なので、本来はきちんと解くべきなのだけれど...
    - @eban さんの解答がシンプルかつ的確すぎて、あれ以上スマートな解き方を思いつかなかったorz
    - なので、今回は愚かな方法でお茶を濁すことに...／(^o^)＼

* 本文中の解答だと、あまりに遅いので... Tukubaiコマンドを利用した、もう少しマシな速さの別解をば。

    ```sh
    1	#!/bin/bash
    2	
    3	(loopx <(seq 0 1 200) <(seq 0 2 200) <(seq 0 5 200) <(seq 0 10 200) <(seq 0 20 200) <(seq 0 50 200) <(seq 0 100 200); echo 0 0 0 0 0 0 0 200) \
    4	| # 全組み合わせの生成
    5	ysum \
    6	| # 各組み合わせの合計の出力
    7	self NF \
    8	| # 余分なフィールドの除去
    9	grep '^200$' \
    10	| # 合計が200になる組み合わせの抽出
    11	gyo
    12	  # 組み合わせの総計の算出
    ```
    - ワンライナー版。

    ```sh
    (loopx <(seq 0 1 200) <(seq 0 2 200) <(seq 0 5 200) <(seq 0 10 200) <(seq 0 20 200) <(seq 0 50 200) <(seq 0 100 200); echo 0 0 0 0 0 0 0 200) | ysum | self NF | grep '^200$' | gyo
    ```
    - ちなみに、`loopx`は複数ファイルの各レコードを総掛けする、`ysum`は各レコードに関して横集計する、`self`は特定フィールドのみを出力する、`gyo`は行数を出力するコマンドです。

* 参考として、実行時間は以下のようになりました。

    ```sh
    $ cat /proc/cpuinfo | grep 'model name' | uniq
    model name      : AMD FX(tm)-8320 Eight-Core Processor

    # 本文中の解答
    $ time (awk 'BEGIN{for(i=0;i<=200;i++){print i}}' | awk '{for(i=0;i<=200;i+=2){print $0,i}}' | awk '{for(i=0;i<=200;i+=5){print $0,i}}' | awk '{for(i=0;i<=200;i+=10){print $0,i}}' | awk '{for(i=0;i<=200;i+=20){print $0,i}}' | awk '{for(i=0;i<=200;i+=50){print $0,i}}' | awk '{for(i=0;i<=200;i+=100){print $0,i,0}}'; echo 0 0 0 0 0 0 0 200) | awk '{s=0;for(i=1;i<=NF;i++){s+=$i};cnt[s]++} END{print cnt[200]}'
    73682

    real    123m35.140s
    user    188m19.912s
    sys     3m0.320s

    # Tukubaiを用いた別解
    $ time (loopx <(seq 0 1 200) <(seq 0 2 200) <(seq 0 5 200) <(seq 0 10 200) <(seq 0 20 200) <(seq 0 50 200) <(seq 0 100 200); echo 0 0 0 0 0 0 0 200) | ysum | self NF | grep '^200$' | gyo
    73682

    real    34m10.048s
    user    64m52.083s
    sys     1m45.183s
    ```
    - お、遅い......\_(¦3 」∠ )_ 
<br>
<br>

* シェル芸関連の話題として、ちょこっと宣伝。
    - **第23回シェル芸勉強会は、2016年6月18日(土)開催です！**
    - "jus共催、第5回初心者向けとは言うものの午前のシェル勉強会/第23回梅雨でモワッとしたシェル芸勉強会 - USP友の会 | Doorkeeper" [https://usptomo.doorkeeper.jp/events/44975](https://usptomo.doorkeeper.jp/events/44975)
    - また、大阪や福岡では、有志の方によってサテライト会場も設置されています。
        + 大阪会場: [https://5f01b3bc1d81c1fae2378cdc89.doorkeeper.jp/events/45741](https://5f01b3bc1d81c1fae2378cdc89.doorkeeper.jp/events/45741)
        + 福岡会場: [https://atnd.org/events/77677](https://atnd.org/events/77677)
    - 当日はライブ配信もしてくださるそうです。興味のある方はぜひ！

- - -

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