<< Previous exercise (4.39) | Index | Next exercise (4.41) >>
(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)))))))
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)))))
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))))))))
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)))))))
Although I agree with your reasoning about not manually ruling combinations out, SofiaG, I don't think your solution actually changes the runtime of the program in any meaningful way: even though you've inserted a bunch of lets, the calls to amb would still be happening in the same order as in the original program from the text. I think the secret sauce is actually adding more requires, perhaps by calling distinct after every time that we define a new dweller, for example.
(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)))))))