フィボナッチ文字列

オイラープロジェクト230問目。数値の加算の代わりに、文字列の結合によるフィボナッチ文字列というような感じの問題。

(ns euler
  (:use clojure.contrib.str-utils))

(def str-a "1415926535")
(def str-b "8979323846")

; (def str-a "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679")
; (def str-b "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196")

(defn fib-seq
  ([] (concat [str-a str-b] (fib-seq str-a str-b)))
  ([a b]
     (let [n (str-join "" [a b])]
       (lazy-seq
	(cons n (fib-seq b n))))))

(defn longer-n? [n]
  (fn [str] 
    (> (count str) n)))

(defn e230 [n]
   (nth 
    (first (filter (longer-n? n) (fib-seq)))
    (dec n)))

(defn func1 [n]
  (* (+ 127 (* 19 n))
     (Math/pow 7 n)))

(println
 (e230 35))

例題の答えはでるけど、本題である初期値がそれぞれ100桁の数字のものについては、あっという間にメモリが足りなくなる。メモリ効率のオーダーはfunc1で決まっていて、これはO(n^7)なのかな。答えに関係ないところを、n桁の数値というような桁数だけに置換したデータ構造にするとかすればいいような気もする。うーん。

lazy sequenceを作ってfilterをかけ、最初にfilterがtrueになるものを見つけてホゲホゲという流れって、こういうときには便利なのねと思った。