概要
Project Euler1は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。
しかし、シェル芸2による解答は、私が探した限りでは、ごく僅かしか見つからなかった。
そこで、私自身の勉強も兼ねて、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 1pHow 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を作る方法は何通りあるか?
正答は、注釈3に記載する。
解法
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 」∠ )_
- お、遅い......_(¦3 」∠ )_
-
シェル芸関連の話題として、ちょこっと宣伝。
- 第23回シェル芸勉強会は、2016年6月18日(土)開催です！
- "jus共催、第5回初心者向けとは言うものの午前のシェル勉強会/第23回梅雨でモワッとしたシェル芸勉強会 - USP友の会 | Doorkeeper" https://usptomo.doorkeeper.jp/events/44975
- また、大阪や福岡では、有志の方によってサテライト会場も設置されています。
- 当日はライブ配信もしてくださるそうです。興味のある方はぜひ！
-
About - Project Euler (https://projecteuler.net) ↩
-
シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩
-
73682 ↩