4.40 Exercise 4.40

There are 5^5 = 3125 non-unique assignments of floors to residents and only 5! = 120 unique assignments. This means that the vast majority of the assignments that we will test, even ignoring the other requirements in the problem, will be failures. In addition to reducing the number of times we test for distinctness, we should be reducing the search space by testing our conditions as each assignment is generated, rather than after we have constructed a full assignment.

Borrowing the order of the requirements from the original solution (minus distinct?, which is moved to the end), we arrive at the following program:

(define (multiple-dwelling-3)

(let ((baker (amb 1 2 3 4 5)))

(require (not (= baker 5)))

(let ((cooper (amb 1 2 3 4 5)))

(require (not (= cooper 1)))

(let ((fletcher (amb 1 2 3 4 5)))

(require (not (= fletcher 5)))

(require (not (= fletcher 1)))

(require (not (= (abs (- fletcher cooper)) 1)))

(let ((miller (amb 1 2 3 4 5)))

(require (> miller cooper))

(let ((smith (amb 1 2 3 4 5)))

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

We can see that it generates the correct answer: