SICPを読む(52) 問題2.29 モビール問題

Scheme

モビールというとベビーベッドの上にぶら下がっているアレを思い出すんですが、芸術性を極めればこんなにセクシーになるんですね。

僕もセクシーモビールが作りたくなってきてしまった。

問題2.29

イメージ

モビール問題を解く前に、イメージを固めておこう。

SICPの問題の場合、

これが全体。

   |
 1 |   2
 -L-R---
 |     |
 2     1

モビールと呼ばれる部分は縦棒。右と左がある。

   |
   |
  L-R

そして、長さのある棒と錘(またはモビール)

      2
   R---
      |
      1

によって構成されている。

左右の「棒の長さ * 錘(またはモビール)の全重量」が等しければ、モビールは釣合う。

イメージ重要。

モビールの定義

こんな感じのモビールを解いていくことにする。

(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list length structure))

(define m
  (make-mobile
    (make-branch 3 1)
    (make-branch 1
                 (make-mobile
                   (make-branch 1 2)
                   (make-branch 2 1)))))
a

色々返す。

(define (left-branch m)
  (car m))
(define (right-branch m)
  (cadr m))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (cadr b))

(branch-length (left-branch m)) ; 3
(branch-structure (right-branch m)) ; ((1 2) (2 1))
b

モビールの全重量を返す。

(define (branch-weight b)
  (let ((s (branch-structure b)))
    (if (not (pair? s))
        s
        (total-weight s))))
(define (total-weight m)
  (+ (branch-weight (left-branch m))
     (branch-weight (right-branch m))))

(total-weight m) ; 4

cの問題があったので2つの部分に分けた。

c

釣合っているか?

(define (balanced? m)
  (define (branch-balance b)
    (* (branch-length b) (branch-weight b)))
  (if (not (pair? m))
      #t
      (let ((l (left-branch m))
            (r (right-branch m)))
        (and (= (branch-balance l)
                (branch-balance r))
             (balanced? (branch-structure l))
             (balanced? (branch-structure r))))))

(balanced? m) ; #t

間違っていたので修正。案外長くなってしまった。

d

consに変えたときの修正範囲。

(define (right-branch m)
  (cdr m))
(define (branch-structure b)
  (cdr b))

アクサ部分を変えればいいだけ。

まとめ

最初は全くイメージが湧かなかったが、イメージが掴めれば簡単!