Re: Non-determinism

B. Pym wrote:

Problem 4.42 in SICP
 
Five school girls took an exam. As they think thattheir
parents are too much interested in their score, they promise
that they write one correct and one wrong informations to
their parents. Followings are parts of their letters
concerning their result:
 
Betty: Kitty was the second and I third.
Ethel: I won the top and Joan the second.
Joan: I was the third and poor Ethel the last.
Kitty: I was the second and Mary the fourth.
Mary: I was the fourth. Betty won the top.
 
Guess the real order of the five school girls.

newLISP

;; Iterate over all permutations of a list, and
;; call a function on each.
(define (permute permute.seq permute.func (permute.built '()))
  (if (null? permute.seq)
    (permute.func permute.built)
    (let (seq (copy permute.seq))
      (dotimes (i (length seq))
        (unless (zero? i) (rotate seq -1))
        (permute
          (rest seq)
          permute.func
          (cons (first seq) permute.built))))))

(define (xor a b) (if a (not b) b))

(define (find* x xs) (+ 1 (find x xs)))

(define (either a m  b n  lst)
  (xor (= m (find* a lst))
       (= n (find* b lst))))

(define (check answer)
  (if
    (and
      (either 'kitty 2  'betty 3  answer)
      (either 'kitty 2  'mary 4  answer)
      (either 'mary 4  'betty 1  answer)
      (either 'ethel 1  'joan 2  answer))
    (println answer)))

(permute '(kitty betty ethel joan mary) check)
  ===>
(kitty joan betty mary ethel)