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

概要

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

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


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

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• zsh (5.2)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

[原文 (https://projecteuler.net/problem=2)]

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202)]

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

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

解法

#!/bin/sh

a=1; b=2;
# 初項の設定

while :; do
    c=$(echo "$a+$b" | bc | tr -d '\n\\');
    echo $a;
    a=$b;
    b=$c;
done \
| # フィボナッチ数列の生成
awk '$0 <= 4000000; $0 > 4000000 {exit}' \
| # 数列の項の値が400万以下の項の出力
awk '$0 % 2 == 0 {sum += $0} END {print sum}'
  # 偶数の総和の出力

解法の解説

この解法による処理の詳細は、コードに記載してあるコメントの通りである。

雑記

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

• フィボナッチ数列の生成に関しては、シェル芸勉強会等でもっとエレガントな方法が考案されているかもしれない。
  • シェル芸勉強会、参加してみたいけど、参加したことがない(地理的に参加できない)...(´・ω・`)
• 今回も解説が投げやりだ...
  • だって、今回もそのまんまなんだもん...

---

1. About - Project Euler (https://projecteuler.net) ↩

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

3. 4613732 ↩