概要

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

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

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

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

問題文

[原文 (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:
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)]

硬貨の和

イギリスでは硬貨はポンド£とペンス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を作る方法は何通りあるか?

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

解法

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になる組み合わせの集計

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

(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

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

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

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

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	  # 組み合わせの総計の算出

ワンライナー版。

(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は行数を出力するコマンドです。

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

$ 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 」∠ )_

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

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