Exercise 4.42

Read Exercise 4.42 ~ Solution

---

This is so much fun that I did both a normal scheme version and an amb version. The normal scheme version first, which is identical in structure to Exercise 4.41.

(define (liars)

  (define (invalid-solution permutation)
    (let ((betty (first permutation))
          (ethel (second permutation))
          (joan (third permutation))
          (kitty (fourth permutation))
          (mary (fifth permutation)))
      (and (betty-statement betty kitty)
           (mary-statement mary betty)
           (ethel-statement ethel joan)
           (joan-statement joan ethel)
           (kitty-statement kitty mary))))

  (map present-solution
       (filter invalid-solution
               (permutations (list 1 2 3 4 5)))))
 

The statements are encoded as boolean predicates. Remember one part is true and the other false, but we don’t know which.

(define (xor a b)
  (or (and a (not b))
      (and (not a) b)))

; Betty: Kitty was second in the examination. I was only third.
(define (betty-statement betty kitty)
  (xor (= kitty 2) (= betty 3)))

; Ethel: You'll be glad to hear that I was on top. Joan was second.
(define (ethel-statement ethel joan)
  (xor (= ethel 1) (= joan 2)))

; Joan: I was third, and poor old Ethel was bottom
(define (joan-statement joan ethel)
  (xor (= joan 3) (= ethel 5)))

; Kitty: I came out second. Mary was only fourth.
(define (kitty-statement kitty mary)
  (xor (= kitty 2) (= mary 4)))

; Mary: I was fourth. Top place was taken by Betty.
(define (mary-statement mary betty)
  (xor (= mary 4) (= betty 1)))

The only thing left to change is:

(define (present-solution solution)
  (map list
       '(betty ethel joan kitty mary)
       solution))

The same predicates are used in the amb version:

(define (amb-liars)
  (let ((betty (amb 1 2 3 4 5))
        (kitty (amb 1 2 3 4 5)))
    (require (betty-statement betty kitty))
    (let ((mary (amb 1 2 3 4 5)))
      (require (mary-statement mary betty))
      (require (kitty-statement kitty mary))
      (let ((joan (amb 1 2 3 4 5))
            (ethel (amb 1 2 3 4 5)))
        (require (ethel-statement ethel joan))
        (require (joan-statement joan ethel))
        (require (distinct? (list betty ethel joan kitty mary)))
        (present-solution (list betty ethel joan kitty mary))))))

The solution: ((betty 3) (ethel 5) (joan 2) (kitty 1) (mary 4))