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

概要

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

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

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

問題文

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

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

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:

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)]

1000桁のフィボナッチ数

フィボナッチ数列は以下の漸化式で定義される:

F_n = F_{n-1} + F_{n-2},\ \text{ただし}\ F_1 = 1, F_2 = 1.

最初の12項は以下である.

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桁になる最初の項の番号を答えよ.

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

解法

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桁になる項数の出力

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

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
  
  

• (シンプルな問題なので、コメントすることは特に無し。)

• ただ、MPFRは、gawkのバージョン4.1.0以上のみ利用できる機能である点にご注意を。

  • Cent OS 6.xだと、gawkのバージョンは3.x.xなので、今回の解法は利用できない。
    
    

• 3行目のyesを使わなくても、5行目のgawkだけでフィボナッチ数列を生成出来たりする。

  • でも、シェル芸では、初めに入力を生成するようにしたい。個人的な主義だけれど...
  • 具体的には、cat、echo、yes等から開始するようにしたい。
  • 何かこう、無(?)に対して処理をおこなうのは、ちょっと気持ち悪い感じがするんだよね...
  • まず、入力データを作ってから、それに対してこねくり回すやり方が好き。
  • awkはあくまでフィルタとして使いたい。

---

---

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

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

3. 4782 ↩