Project Euler Problem 25

problem_25.clj

(ns projecteuler.problem-25
  (:require [clojure.string :as str]
            [clojure.math.numeric-tower :as math])
  (:use clojure.test))

(defn fib-gen
  "フィボナッチ数を generate する関数。初期値[1 1]から iterate する前提。"
  [[a b]] [b (+' a b)])

(def fib-seq
  "フィボナッチ数とその項を返す。"
  (->> (iterate fib-gen [1 1])
       (map first)
       (map-indexed (fn [idx itm] [(inc idx) itm]))))

(defn find-min-fibs
  "lower 以上で最小のフィボナッチ数とそのindexを返す。"
  [lower]
  (first (drop-while #(<= (second %) lower) fib-seq)))

(defn problem-25
  "Project Euler Problem 25"
  ([] (problem-25 (math/expt 10 999)))
  ([lower] (first (find-min-fibs lower))))

;;(time (problem-25))
;;=> "Elapsed time: 5.387 msecs"

;; test
(is (= (find-min-fibs 100) [12 144]))

(is (= (problem-25 100) 12))

考え方とか感想とか

• フィボナッチ数は、lazyなシーケンスの形で作り出しています(あまり苦もなく作れるのが Clojure の良い所)。
• map-indexed でフィボナッチ数の項(index)を当て込んでいます。
• あとは、値n (上ソースでは lower) を超える最も小さいフィボナッチ数を求めるように drop-while し、最終的にはその項(index) を答えとして返します。
• 1000個のdigits を含む、は、10^99 以上の数値となるフィボナッチ数、と読み替えて処理をしています。10^99 を取得するのに clojure.math.numeric-tower/expt を使いました( [org.clojure/math.numeric-tower "0.0.2"] )。
• 性能面ではあまり心配していませんでしたが、予想通りレスポンスは早かったです。

👍 読みやすいです．

doc-string と解説, とても分かりやすいです.
解法も順当で何の問題も無いと思います.

さしたる別解も思い浮かばないので, 本当に些細な点で,

• fib-seq がインデクス付きシーケンスを返すことを doc-string に明記するだけでなく, 関数名にも反映 (indexed-fibs とか) するというのは如何でしょう.
• インデクスが 1から始まるのはプログラマから見れば特殊なので, doc-string に明記するか, map-indexed が付けてくれたインデクスを毎回 inc しているのがもったいないので, fib-seq が返すシーケンスのインデクスは 0から始めておいて, 解答を作るときに inc する. というのはどうでしょう.

覚え書き: フィボナッチ数(列)については @tnoda さん担当 Problem 2 も参照.

tnoda さん、kohyama さん

• コメントありがとうございます。
• indexed-fibs 、命名としてはこちらのほうがいいですね。いつも命名の仕方で迷います(結果失敗することも...)。
• インデックスを毎回 inc するのは、確かにもったいないですね。ご指摘ありがとうございます。
• Problem2、以前見たよりコメントが伸びてた...。この週末にでもみなさんの解答をもう一度おさらいしておきたいです(なかなか追いつかないので困ったもんです)。

Problem2、以前見たよりコメントが伸びてた...。この週末にでもみなさんの解答をもう一度おさらいしておきたいです(なかなか追いつかないので困ったもんです)。

他の問題もかなり伸びているので，ぜひ，もう一度見てコメントを追加してみてください．

コードにあえてコメントするとすれば、fib-seqがフィボナッチ数列の生成と、インデクシングをいっしょにしているのに違和感があります。 別にしたほうがきれいだと思います。

変数や関数の命名は僕もたいてい失敗します。
googleのlispのコーディング規約 にあるように、「中身(content)ではなく目的(intent)によって命名すべき」というのは頭にあってもつい xxx-list とかになってしまう。

take-while にして、 count するのもいいかと思いました。

(defn fibs [] (map first (iterate (fn [[x0 x1]] [x1 (+ x0 x1)])
                                  [1N 1N])))

(defn solve [limit-exclusive]
  (inc (count (take-while #(< % limit-exclusive) (fibs)))))

(solve (. (java.math.BigInteger. "10") pow 999))

この方法でやると、インデックスをプログラムからなくせます。

+' の存在、初めて知りました。勉強になります。

ypsilon-takai さん

• コメントありがとうございます。fib-seq の件、確かにその通りかもしれません。名前fib-seq と中身が一致してないから余計に違和感を増している感じですね。plaster さんのコメントにある fibs が fib-seq にふさわしいかも。
• google の lisp コーディング規約からの引用、ありがとうございます。日本語訳 は現在翻訳進行中ですが一応リンク貼っておきます( ソース )。

plaster さん

• コメントありがとうございます。
• 解法、目からうろこです。すっきりしていいですね。ありがとうございます。

@ponkore さん

日本語訳やってるんですね。しかもメンバーをやってらっしゃる。 githubでやってるんですねぇ。 おもしろそうだなぁ。 まだ訳されてないのがありますねぇ。 やってみようかなぁ。

@plaster さん

僕もインデックスなくせないかなぁと思ったんですが、出ませんでした。 思考が硬直してる証拠ですね。 おみごとです。

いや、ほんのちょびっとしか翻訳していないんです...偉そうにリンク出してしまったのですが、なんだか申し訳ない(暇できたらまたやります!!)。