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

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

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

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

# 実行環境
* Arch Linux (x86\_64, 4.3.3-3-ARCH)
* bash (4.3.42, POSIX互換モード)
* GNU coreutils (8.24)
* gawk (4.1.3)

<!---
* bsd-games (2.17)
* curl (7.46.0)
--->

# 問題文
[原文 ([https://projecteuler.net/problem=25](https://projecteuler.net/problem=25))]
#### 1000-digit Fibonacci number

> The Fibonacci sequence is defined by the recurrence relation:
> 
> ```math
> F_n = F_{n−1} + F_{n−2},\ \text{where}\ F_1 = 1\ \text{and}\ F_2 = 1.
> ```
> Hence the first 12 terms will be:
> 
> ```math
> F_1 = 1 \\
> F_2 = 1 \\
> F_3 = 2 \\
> F_4 = 3 \\
> F_5 = 5 \\
> F_6 = 8 \\
> F_7 = 13 \\
> F_8 = 21 \\
> F_9 = 34 \\
> F_{10} = 55 \\
> F_{11} = 89 \\
> F_{12} = 144
> ```
> 
> The 12th term, $F_{12}$, is the first term to contain three digits.
> What is the index of the first term in the Fibonacci sequence to contain 1000 digits?


[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2025](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2025))]
#### 1000桁のフィボナッチ数

> フィボナッチ数列は以下の漸化式で定義される:
> 
> ```math
> F_n = F_{n-1} + F_{n-2},\ \text{ただし}\ F_1 = 1, F_2 = 1.
> ```
> 最初の12項は以下である.
>
> ```math
> F_1 = 1 \\
> F_2 = 1 \\
> F_3 = 2 \\
> F_4 = 3 \\
> F_5 = 5 \\
> F_6 = 8 \\
> F_7 = 13 \\
> F_8 = 21 \\
> F_9 = 34 \\
> F_{10} = 55 \\
> F_{11} = 89 \\
> F_{12} = 144
> ```
> 
> 12番目の項, $F_{12}$が3桁になる最初の項である.
> 1000桁になる最初の項の番号を答えよ.


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

# 解法
```sh
1	#!/bin/sh
2	
3	yes "高須クリニック" \
4	| # お約束のやつ
5	gawk -M 'BEGIN {a=1; b=1} {print a; c=a+b; a=b; b=c}' \
6	| # フィボナッチ数列の出力
7	awk 'length($0) == 1000 {print NR; exit}'
8	  # 初めて1000桁になる項数の出力
```

以下、コマンドライン上での実行用コードである。

```sh
yes "高須クリニック" | gawk -M 'BEGIN {a=1; b=1} {print a; c=a+b; a=b; b=c}' | awk 'length($0) == 1000 {print NR; exit}'
```

## 解説
フィボナッチ数列を列挙し、桁数が初めて1000を超える数値の項数を出力すれば良い。

ただし、今回の設問では、処理の過程で扱う数値が非常に大きくなる。
そのため、`nawk`や`mawk`では、正答を導出することができない。
そこで、5行目の`gawk`では、`-M`オプションを用いることで、高度な数値演算や桁数の多い数値を扱う拡張機能である、GNU MPFRを有効にしている。

その他の処理の詳細は、ソースコードに記載してあるコメントの通りである。

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

* (シンプルな問題なので、コメントすることは特に無し。)
* ただ、MPFRは、`gawk`のバージョン4.1.0以上のみ利用できる機能である点にご注意を。
    - Cent OS 6.xだと、`gawk`のバージョンは3.x.xなので、今回の解法は利用できない。  
<br>
* 3行目の`yes`を使わなくても、5行目の`gawk`だけでフィボナッチ数列を生成出来たりする。
    - でも、シェル芸では、初めに入力を生成するようにしたい。個人的な主義だけれど...
    - 具体的には、`cat`、`echo`、`yes`等から開始するようにしたい。
    - 何かこう、無(?)に対して処理をおこなうのは、ちょっと気持ち悪い感じがするんだよね...
    - まず、入力データを作ってから、それに対してこねくり回すやり方が好き。
    - `awk`はあくまでフィルタとして使いたい。

- - -

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