概要
Project Euler1は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。
しかし、シェル芸2による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。
本記事では、Project EulerのProblem 10を、シェル芸で解いた際の過程を述べる。
実行環境
-
Arch Linux (x86_64, 4.3.3-2-ARCH)
-
bash (4.3.42, POSIX互換モード)
-
GNU coreutils (8.24)
-
gawk (4.1.3)
-
bsd-games (2.17)
問題文
[原文 (https://projecteuler.net/problem=10)]
The sum of the primes below $10$ is $2 + 3 + 5 + 7 = 17$.
Find the sum of all the primes below two million.
[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2010)]
$10$ 以下の素数の和は $2 + 3 + 5 + 7 = 17$ である.
$200$万以下の全ての素数の和を求めよ.
正答は、注釈3に記載する。
解法1
1 #!/bin/sh
2
3 seq 1 2000000 \
4 | # 入力の生成
5 factor \
6 | # 素因数分解
7 awk 'NF == 2 {print $2}' \
8 | # 素数の抽出
9 tr '\n' '+' \
10 | # 数式の生成_1
11 sed -e 's/\+$/\n/' \
12 | # 数式の生成_2
13 bc
14 # 計算結果の出力
解説1
この解法による処理の詳細は、コードに記載してあるコメントの通りである。
また、bsd-gamesに含まれるprimesを用いたより短い解き方を、解法2として述べる。
解法2
1 #!/bin/sh
2
3 primes 2 2000000 \
4 | # 2000000以下の素数の列挙
5 awk '{sum+=$0} END {print sum}'
6 # 和の出力
解説2
この解法による処理の詳細は、コードに記載してあるコメントの通りである。
雑記
- 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
- 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
- 今回の問題も手抜き解説。
- いやでも、今回はこれ以上説明のしようが無いと思うので...
- 数式の生成に関しては、
tr '\n' '+' | sed -e 's/\+$/\n/'
とするよりも、xargs | tr ' ' '+'
としたほうがエレガントではある。- trで改行コードを演算子に変換する方法だと、末尾に余分な演算子がくっついてしまうので。
- けれど、xargs(正確にはOS)には、一度に扱える引数の総バイト数に上限がある >>
$ getconf ARG_MAX
- 今回の問題はその上限に引っかかってしまい、数式がうまく生成できないため、
tr '\n' '+' | sed -e 's/\+$/\n/'
にした。
- 先に解答されちゃった><
- ...ので、対抗してこちらも今日のうちにProblem 10も投稿することにするw - 1日1問のつもりなので、明日はお休みするかも?yes | sed -n = | factor | awk '$0=$2*!$3' | awk '$0>=2000000{exit}{s+=$0}END{print s}' Problem 10. sed -n =といういい話を聞いたので使ってみた #シェル芸
— 卒論まで21日のMasaki Waga (@MasWag) January 12, 2016
-
About - Project Euler (https://projecteuler.net) ↩
-
シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩
-
142913828922 ↩