SICPゼミ第59回

練習問題4.41

(define (generate-list n)
  (define (pow n k)
    (if (= k 0)
      1
      (* n (pow n (- k 1)))
    )  
  )
  (define (int-to-list m n k)
    (if (= k 0)
      (list)
      (cons (remainder m n) (int-to-list (/ (- m (remainder m n)) n) n (- k 1)))
    )
  )
  (define (list-generation-itr k)
    (if (< k 0)
      (list)
      (cons (int-to-list k n n) (list-generation-itr (- k 1)))
    )
  )
  (list-generation-itr (- (pow n n) 1))
)

で解の候補をすべて列挙したリストを作れる．これにフィルターをかければOK.

練習問題4.42

(define (liar-game)
  (let ((betty (amb 1 2 3 4 5))
        (ethel (amb 1 2 3 4 5))
        (joan (amb 1 2 3 4 5))
        (kitty (amb 1 2 3 4 5))
        (mary (amb 1 2 3 4 5)))
    (require
      (distinct? (list betty ethel joan kitty mary)))
    (require (xor (= kitty 2) (= betty 3)))
    (require (xor (= ethel 1) (= joan 2)))
    (require (xor (= joan 3) (= ethel 5)))
    (require (xor (= kitty 2) (= mary 4)))
    (require (xor (= mary 4) (= betty 1)))
    (list (list 'betty betty) (list 'ethel ethel)
          (list 'joan joan) (list 'kitty kitty)
          (list 'mary mary))))

'((betty 3) (ethel 5) (joan 2) (kitty 1) (mary 4))

おしまい。 by tube

練習問題4.43

(define (father-determination)
  (let ((mary (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (gabrielle (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (lorna (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (rosalind (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (melissa (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker))))
    (require
      (distinct? (list (car mary) (car gabrielle) (car lorna) (car rosalind) (car melissa))))
    (require
      (distinct? (list (cdr mary) (cdr gabrielle) (cdr lorna) (cdr rosalind) (cdr melissa))))
    (require (not (eq? (car gabrielle) (cdr gabrielle))))
    (require (not (eq? (car lorna) (cdr lorna))))
    (require (not (eq? (car rosalind) (cdr rosalind))))
    (require (not (eq? (car melissa) (cdr melissa))))
    (require (not (eq? (car mary) (cdr mary))))
    (require (eq? (car gabrielle) 'barnacle))
    (require (eq? (car lorna) 'moore))
    (require (eq? (car rosalind) 'hall))
    (require (eq? (car melissa) 'downing))
    (require (eq? (cdr melissa) 'barnacle))
    (require (eq? (cdr mary) 'moore))
    (require (cond ((eq? (cdr gabrielle) 'parker) (eq? (car gabrielle) (cdr gabrielle)))
                   ((eq? (cdr lorna) 'parker) (eq? (car lorna) (cdr gabrielle)))
                   ((eq? (cdr rosalind) 'parker) (eq? (car rosalind) (cdr gabrielle)))
                   ((eq? (cdr melissa) 'parker) (eq? (car melissa) (cdr gabrielle)))
                   ((eq? (cdr mary) 'parker) (eq? (car mary) (cdr gabrielle)))))
    (list (list 'gabrielle gabrielle) (list 'lorna lorna)
          (list 'rosalind rosalind) (list 'melissa melissa)
          (list 'mary mary))))

> (father-determination)
'((gabrielle (barnacle . hall))
  (lorna (moore . downing))
  (rosalind (hall . parker))
  (melissa (downing . barnacle))
  (mary (parker . moore)))
> (amb)
. . amb tree exhausted
> 

高速化は次回！