<< Previous exercise (4.38) | Index | Next exercise (4.40) >>
Note that this exercise can be solved purely using some elementary combinatorial calculations on pencil and paper, without running the code or even knowing how long it takes to run the distinct? procedure.
The first part, whether the ordering of requirements affects the final result, is clearly "no".
To answer the second part, let's define four "events", corresponding to the four require statements after the initial distinct? requirement:
1. baker = 5 2. cooper = 1 3. fletcher = 5 4. fletcher = 1
Note that the number of distinct outcomes is 5! = 120. Of those 120, the number that fail the first requirement, e.g. match event 1, we denote as N(1) = 4! = 24. The number that fail *either* the first or second requirement, e.g. match *either* event 1 or event 2, we denote as N(1 or 2). Using "the principle of inclusion and exclusion" (c.f. wikipedia), we have
N(1 or 2) = N(1) + N(2) - N(1 and 2) = 2 * 4! - 3! = 42
An easy way to think about this is we are adding up overlapping Venn diagram regions and correcting for double-counting overlaps.
Continuing, we have after some further calculation:
N(1 or 2 or 3) = 3 * 4! - 2 * 3! = 60 N(1 or 2 or 3 or 4) = 4 * 4! - 4 * 3! = 72
From these numbers we see that 24 outcomes fail the first requirement, 18 fail the second, 18 fail the third, and 12 fail the fourth. Hence, the total number of tests done on these failed requirements, during the four requirements examined here, is
1 * 24 + 2 * 18 + 3 * 18 + 4 * 12 = 162.
Now let's see what happens if we reorder the four events, which correspond to the four require statements in the code after the initial distinct? require statement:
1. fletcher = 5 2. fletcher = 1 3. baker = 5 4. cooper = 1
Performing a similar calculation as above (which I will leave as an exercise for the reader), we obtain the total number of tests done during the four requirements is 156.
Hence, assuming that our Scheme interpreter takes the same time to lookup each of the variables in the environment, having the two fletcher requirements *before* the baker and cooper requirements is *guaranteed* to be faster.
Note that we are able to compare these two orderings because everything that happens after the four requirements is the same for both.
If the restrictions were set, then the order of them does not matter to the answer.
As far as I'm concerned that the solution provided by meteorgan is not the most efficient one. However, meteorgan was right about one thing that we should move distinct? to the end of restrictions.
To Improve efficiency, one thing we need to know is how do multiple ambs search. I will give a simple example to illustrate:
;;; Amb-Eval input: (define (t) (list (amb 1 2) (amb 'a 'b))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (t) ;;; Starting a new problem ;;; Amb-Eval value: (1 a) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (1 b)
The following timing diagram depicts the search process above:
FIRST TIME:
/ <---- The first choice point
/ /\
/ / \
/ / \ alternative
/ / \
/ / \
search / / \
path / / \
/ / \
/ / \
/ -1 -2 <---- The second choice point
/ /\
/ / \
/ / \ alternative
/ / \
v / \
/ \
-a -b
SECOND TIME:
/ <---- The first choice point
/ /\
/ / \
/ / \ alternative
/ / \
/ / \
/ / \
+ / \
\ / \
\ \
-1\ -2 <---- The second choice point
/\ \ search
/ \ \path
vistied / \ \
/ \ \
/ \ v
/ \
-a -b
This is analogous to nested loop which try to run through the inner loop before picking up the next element of the outer loop. In that case, we take 1 as the first choice, and then explore all available choices. After finishing all attempts, we will go back to the first choice point, and select the alternative 2, and then perform a further search.
To avoid unnecessary searches, we need avoid making the wrong choice as soon as possible. If we find the early choice is wrong, it's too late to stop it, which means we must run through all further choices, even all of them are needless. So, all I do is try to find wrong choices early and stop them in time.
My solution is as follows:
(define (multiple-dwelling)
(let ([fletcher (amb 1 2 3 4 5)])
(require (not (= fletcher 1)))
(require (not (= fletcher 5)))
(let ([cooper (amb 1 2 3 4 5)])
(require (not (= cooper 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(let ([smith (amb 1 2 3 4 5)])
(require (not (= (abs (- smith fletcher)) 1)))
(let ([miller (amb 1 2 3 4 5)])
(require (> miller cooper))
(let ([baker (amb 1 2 3 4 5)])
(require (not (= baker 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))))))))
meteorgan