久しぶりに1発でとけた。

Lisp

どもです。
とうとう例のチョコ飴が残り1粒となりました。
相方さんに持っていって食わせたところ，
「おいしい。駄菓子屋のチョコの味がする。」
というなんとも微妙な感想が。
追加発注しちゃおっかなぁー。

Project Euler Problem 114

最初，なんか式を導けないかなぁーと手を動かしながら考えたけど，
無理そうだったので，再帰った。
できた関数に 7 をいれたら 17 が帰ってきたので，50 の場合で実行。
もっそい時間がかかった(20分くらいか)けど，答えが出た。
んで，サブミットしたら正解だった。
その後，というか答えが出るのをまっている間にメモ化できないかなーと
トレースを見ていたらできそうだったので，してみた。
ほしたら，即だった。

;; table は，2次元配列。
;; table[i][j], 0 <= i <= len, j = 1 when prev-is-red, 0 otherwise
(defun put-blocks (len prev-is-red table)
  ;;(declare (optimize (debug 3)))
  (cond ((zerop len)
         1)
        (prev-is-red
         ;; 前は赤。
         ;; 黒を1つ置く。
         (or (aref table (1- len) 0) (setf (aref table (1- len) 0)
                                           (put-blocks (1- len) nil table))))
        (t
         ;; 前は黒。
         ;; 黒を1つ置いて次へ行く場合と，
         ;; 赤を並べる場合を足す。
         (+ (put-blocks (1- len) nil table)
            (loop for red from 3 to len
                summing (or (aref table (- len red) 1)
                            (setf (aref table (- len red) 1)
                                  (put-blocks (- len red) t table))))))))

(defun euler-problem-114 (n)
  (put-blocks n nil (make-array (list (1+ n) 2) :initial-element nil)))

CL-USER> (time (euler-problem-114 50))
(EULER-PROBLEM-114 50) took 0 milliseconds (0.000 seconds) to run 
                    with 4 available CPU cores.
During that period, 0 milliseconds (0.000 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 6,912 bytes of memory allocated.


んで，毎度の如くフォーラム入ったら，漸化式的なモノが書いてあって，
うはー，かしこいなーみんなと驚嘆しているわけです。
理解はまだ，してません。腹減ったので。