►zthomae’s SICP solutions
▼4 Chapter 4
    ← prev  up  next → 

4.41 Exercise 4.41

The nondeterminism created by amb can also be represented by lists (or streams) of values that we can "select" by filtering and flatmapping over them. Thus, the values in the list represent all of the possible values that a binding could have, and flatmapping over this list is akin to selecting an arbitrary one of them. (Obviously, the selection is not really arbitrary, because lists are ordered, but the answer will still be correct.)

We can use a mechanical transformation of amb and require operations into flatmap and filter sequences to translate the version of this program from Exercise 4.40. Note as well the similarities to the solution to the eight queens problem from Exercise 2.42.

(define (multiple-dwelling-4)
  (let* ((pick-floor (list 1 2 3 4 5))
         (baker-choices (filter (lambda (baker) (not (= baker 5))) pick-floor)))
    (flatmap
     (lambda (baker)
       (let ((cooper-choices (filter (lambda (cooper) (not (= cooper 1))) pick-floor)))
         (flatmap
          (lambda (cooper)
            (let ((fletcher-choices (filter (lambda (fletcher)
                                              (and (not (= fletcher 5))
                                                   (not (= fletcher 1))
                                                   (not (= (abs (- fletcher cooper)) 1))))
                                            pick-floor)))
              (flatmap
               (lambda (fletcher)
                 (let ((miller-choices (filter (lambda (miller) (> miller cooper)) pick-floor)))
                   (flatmap
                    (lambda (miller)
                      (let ((smith-choices (filter (lambda (smith) (not (= (abs (- smith fletcher)) 1))) pick-floor)))
                        (filter (lambda (result) (distinct? (map cadr result)))
                                (map (lambda (smith)
                                       (list (list 'baker baker)
                                             (list 'cooper cooper)
                                             (list 'fletcher fletcher)
                                             (list 'miller miller)
                                             (list 'smith smith)))
                                     smith-choices))))
                    miller-choices)))
               fletcher-choices)))
          cooper-choices)))
     baker-choices)))
> (pretty-display (multiple-dwelling-4))

{{{baker 3} {cooper 2} {fletcher 4} {miller 5} {smith 1}}}

Because there is only one solution to the puzzle, it doesn’t matter so much whether we use stream or lists of choices. However, lazy evaluation more accurately matches the semantics of amb than do strict lists.

    ← prev  up  next →