Problem 122 解けたよ。 - GONE WITH THE MEDICINE

どもです。
さっき地震があったので思い出したのですが，
3月12日に大きい地震が来ると予想している whitypig さんです。
根拠?
オレが地震だった，3月12日か，もしくは，3月10日を狙うだろうから。
この日記にはまだ書いてなかったので書いておこっと。

defstruct でハマッてた。

時間はかかるは，メモリを喰うはで大変でしたが，なんとか。
power-tree っぽいのを作る build-power-tree と，
その木をトラバースする traverse-pt にわけないで，
一回で計算すればたぶんだいぶ速くなると予想。

(defun euler-problem-122-2 ()
  (reduce #'+ (coerce
               (subseq
                (traverse-pt (build-power-tree 11)
                             (make-array (list 201) :initial-element nil)
                             0)
                1)
               'list)))

(euler-problem-122-2)
;; (EULER-PROBLEM-122-2) took 35,157 milliseconds (35.157 seconds) to run 
;;                     with 4 available CPU cores.
;; During that period, 34,219 milliseconds (34.219 seconds) were spent in user mode
;;                     406 milliseconds (0.406 seconds) were spent in system mode
;; 30,360 milliseconds (30.360 seconds) was spent in GC.
;;  1,086,319,592 bytes of memory allocated.

最初，自分で考えて適当な関数をつくって，解いてみたが，
間違っていた。
しばらく考えて無理そうなので，ググった。
んで，power tree なるものの存在を知った。
で，重複を許した power tree を作ってみようと，
ノードを表す構造体として，

(defstruct pt-node
  (value 0 :type fixnum)
  (children nil :type list)
  (parent nil))

としたんです。
んで，作って色々したら，stack overflow condition とかいうエラーが出る。
理由がわからん。
ググってみるも，stackoverflow.com ばっかりひっかかって大変。
んでなんとなーくという理由で「lisp tree parent circular」とかで検索して，
やっと理由がわかった。

http://www.wutka.com/download/fibheap.lisp
から引用させてもらいます。

;; Need a special print function. The default print function goes
;; berzerk with the circular list
(defun print-fib-heap-node (n stream depth)
  (when (< depth 20)
    (if (null n)
	(print "NIL")
	(progn
	  (dotimes (d depth) (format stream " "))
	  (format stream "fib-heap-node(~a)~%" (fib-heap-node-data n))
	  (map-fib-heap-node-list #'(lambda (x) (print-fib-heap-node x stream (+ depth 1)))
				  (fib-heap-node-child n))))))

デフォルトの print function で循環リストを出力しようとすると，
ベルセルクって，ガッツになって，暴走して，シールケたんはぁはぁ状態になって，
そうこうしているうちに，某映画版が黒歴史になってゴッドに愛されるとか，
そういう風にベルセルクるので，自前の print function を用意しようと
いうことですね。あい。
ちなみに，ワタシは映画版を見てないし，興味ないし，見る予定もないです。
あい。

で，下記のように変更して解決。

(defstruct (pt-node (:print-function print-pt-node))
  (value 0 :type fixnum)
  (children nil :type list)
  (parent nil))

(defun print-pt-node (node stream depth)
  (when (< depth 20)
    (if (null node)
        (format stream "NIL")
        (progn
          (format stream (make-string depth :initial-element #\  ))
          (format stream "PT-NODE(~A): " (pt-node-value node))
          (if (pt-node-children node)
            (loop for n in (pt-node-children node)
                  do (format stream "~A " (pt-node-value n)))
            (format stream "NIL"))
          (terpri stream)
          (mapc (lambda (n) (print-pt-node n stream (1+ depth)))
                (pt-node-children node))))))

子を表示しようとする。
parent スロットを表示しようとする。
その parent スロットの children スロットを表示しようとする。
で，その children のうちの1つのノードの parent を表示しようとする。
以下繰り返し，あーんど，スタックオーバーフロー。
なるほどね。
親と子の両方を持つときには，print function を自前で用意しましょうということですね。
あい。