Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-04-19

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

| 18:59 | ArcでL-99 (P56 二分木が線対称な構成かを調べる) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P56 二分木が線対称な構成かを調べる) - わだばLisperになる

バックトラックをどうしようか、と考えていたら全然進めなくなったので、それは置いておいて、まずは普通にリスト操作で解いて後で考えることにしました。

後ではやらない可能性もありますが…(笑)

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))))