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))))) 

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)))))))