#:g1: ArcでL-99 (P56 二分木が線対称な構成かを調べる)

Posted 2008-04-19 09:59:00 GMT

-(http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
バックトラックをどうしようか、と考えていたら全然進めなくなったので、それは置いておいて、まずは普通にリスト操作で解いて後で考えることにしました。
後ではやらない可能性もありますが…(笑)
mirrorという補助関数を定義して解いてみよう、ということなので、反転して同じ構成かを比較しろ、ということなのかと思い、そういう風に書いてみました。
個々の葉の要素が同じかではなく、構成が同じかどうか、ということなので、skeltonという構成をコピーする関数を定義して比較しています。

(symmetric? '(x nil (x (x (x nil nil) (x nil nil))
                       (x nil (x nil nil)))))
;=> nil

(symmetric? '(x (x (x (x nil nil) (x nil nil)) (x nil (x nil nil))) (x (x (x nil nil) nil) (x (x nil nil) (x nil nil))))) ;=> t

(def mirror (tree) (if no.tree () (let (rt l r) tree `(,rt ,mirror.r ,mirror.l))))

(def skelton (tree) (if no.tree () (let (rt l r) tree `(x ,(skelton l) ,(skelton r)))))

(def symmetric? (tree) (let skel (skelton tree) (iso skel (mirror skel))))

comments powered by Disqus