sicp-ex-4.40



<< Previous exercise (4.39) | Index | Next exercise (4.41) >>


meteorgan

  
  
  
 (define (mutiple-dwelling) 
   (let ((cooper (amb 2 3 4 5)) 
         (miller (amb 3 4 5)))  
     (require (> miller cooper)) 
     (let ((fletcher (amb 2 3 4))) 
       (require (not (= (abs (- fletcher cooper)) 1))) 
       (let ((smith (amb 1 2 3 4 5))) 
         (require (not (= (abs (- smith fletcher)) 1))) 
         (let ((baker (amb 1 2 3 4))) 
           (require (distinct? (list baker cooper fletcher miller smith))) 
           (list (list 'baker baker) 
                 (list 'cooper cooper) 
                 (list 'fletcher fletcher) 
                 (list 'miller miller) 
                 (list 'smith smith))))))) 

Shaw

  
  
  
 (define (multiple-dwelling) 
   (let ((cooper (amb 2 3 4 5)) 
         (miller (amb 3 4 5))) 
     (require (> miller cooper)) 
     (let ((flether (amb 2 3 4))) 
       (require (not (or (= flether cooper) 
                         (= flether miller) 
                         (= (abs (- cooper fletcher)) 1)))) 
       (let ((smith (amb 1 2 3 4 5))) 
         (require (not (or (= smith cooper) 
                           (= smith miller) 
                           (= smith flether) 
                           (= (abs (- smith fletcher)) 1)))) 
         (let ((baker (amb 1 2 3 4))) 
           (require (distinct? (list baker cooper fletcher smith smiller))) 
           (list (list 'baker baker) 
                 (list 'cooper cooper) 
                 (list 'fletcher fletcher) 
                 (list 'miller miller) 
                 (list 'smith smith))))))) 

felix021

The use of 'an-integer-between' from 4-35 helps a lot here.

  
  
  
 (define (multiple-dwelling) 
     (let* ((baker (amb 1 2 3 4))  
           (cooper (amb 2 3 4 5))  
           (fletcher (amb 2 3 4))) 
         (require (not (= (abs (- fletcher cooper)) 1))) 
         (let* ((miller (an-integer-between (+ 1 cooper) 5))  
                (smith (amb 
                         (an-integer-between 1 (- fletcher 2)) 
                         (an-integer-between (+ fletcher 2) 5)))) 
             (require 
                 (distinct? (list baker cooper fletcher miller smith))) 
             (list 
                 (list 'baker baker) 
                 (list 'cooper cooper) 
                 (list 'fletcher fletcher) 
                 (list 'miller miller) 
                 (list 'smith smith))))) 

xdavidliu

I agree with SophiaG below: the exercise asks for a *nondeterministic* program, which means that you can only rule out possibilities using require, and not manually exclude them, even if they are trivial. (If you were allowed to manually exclude outcomes, there would be nothing stopping us from writing a trivial function that just directly outputs the single answer).

Anyways, here's my solution (there's no need to even use distinct? at all, since it's significantly more efficient, at the cost of a small number of extra lines of code, to just manually type out the equivalent require statements:

 (define (multiple-dwelling) 
   (let ((fletcher (amb 1 2 3 4 5))) 
     (require (not (= fletcher 5))) 
     (require (not (= fletcher 1))) 
     (let ((smith (amb 1 2 3 4 5))) 
       (require (not (= smith fletcher))) 
       (require (not (= 1 (abs (- smith fletcher))))) 
       (let ((cooper (amb 1 2 3 4 5))) 
         (require (not (= cooper 1))) 
         (require (not (= cooper smith))) 
         (require (not (= cooper fletcher))) 
         (require (not (= 1 (abs (- fletcher cooper))))) 
         (let ((miller (amb 1 2 3 4 5))) 
           (require (> miller cooper)) 
           (require (not (= miller fletcher))) 
           (require (not (= miller smith))) 
           (let ((baker (amb 1 2 3 4 5))) 
             (require (not (= baker 5))) 
             (require (not (= baker cooper))) 
             (require (not (= baker fletcher))) 
             (require (not (= baker miller))) 
             (require (not (= baker smith))) 
             (list (list 'baker baker) 
                   (list 'cooper cooper) 
                   (list 'fletcher fletcher) 
                   (list 'miller miller) 
                   (list 'smith smith)))))))) 
  

SophiaG

I'm not sure about these solutions. If you chop down the set of assignments to eliminate some of the requires you're: a) solving some of the problem for the program, and b) eliminating some of the search tree for later requires. For example, I would argue the requires with relations between two people should have full floor lists for both if one of them cannot occupy all floors. Otherwise, your solution may still work, but may not in modified cases such as Exercise 4.38. Given that interpretation, here's the best optimization I could come up with:

  
 (define (nested-multiple-dwelling) 
   (let ((fletcher (amb 1 2 3 4 5))) 
     (require (not (= fletcher 5))) 
     (require (not (= fletcher 1))) 
     (let ((cooper (amb 1 2 3 4 5)) 
           (baker (amb 1 2 3 4 5))) 
       (require (not (= baker 5))) 
       (require (not (= cooper 1))) 
       (let ((miller (amb 1 2 3 4 5))) 
         (require (> miller cooper)) 
         (let (smith (amb 1 2 3 4 5)) 
           (require (not (= (abs (- fletcher cooper)) 1))) 
           (require (not (= (abs (- smith fletcher)) 1))) 
           (require 
            (distinct? (list baker cooper fletcher miller smith))) 
           (list (list 'baker baker) 
                 (list 'cooper cooper) 
                 (list 'fletcher fletcher) 
                 (list 'miller miller) 
                 (list 'smith smith)))))))