-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsection-4.3.2.rkt
146 lines (126 loc) · 4.44 KB
/
section-4.3.2.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#lang sicp
; ex 4.38
; 5
; ex 4.39
; The order doesn't affect the answer but affect the speed. Put distinct? at
; the bottom of the requires could speed up the process. The reason is
; distinct? has to loop over the list. Some combinations could be simply ruled
; out by simple equality check.
; ex 4.40
(define (multiple-dwelling)
(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))))))))
; ex 4.41
;
; A naive solution would be writing nested for loops.
; ex 4.42
;
; Should write a xor function.
(define (liars)
(let ([betty (amb 1 2 3 4 5)]
[ethel (amb 1 2 3 4 5)]
[joan (amb 1 2 3 4 5)]
[kitty (amb 1 2 3 4 5)]
[mary (amb 1 2 3 4 5)])
(require (and (or (and (= kitty 2) (not (= betty 3)))
(and (not (= kitty 2)) (= betty 3)))
(or (and (= ethel 1) (not (= joan 2)))
(and (not (= ethel 1)) (= joan 2)))
(or (and (= joan 3) (not (= ethel 5)))
(and (not (= joan 3)) (= ethel 5)))
(or (and (= kitty 2) (not (= mary 4)))
(and (not (= kitty 2)) (= mary 4)))
(or (and (= mary 4) (not (= betty 1)))
(and (not (= mary 4)) (= betty 1)))))
(require (distinct? (list betty ethel joan kitty mary)))
(list (list 'betty betty)
(list 'ethel ethel)
(list 'joan joan)
(list 'kitty kitty)
(list 'mary mary))))
; % ex 4.43
;
; What's the point of writing functions this way? The interpreter uses amb to
; choose values, yet I have to list all possible values in the penultimate
; require clause. The answer is alreay clear by then.
(define (father)
(let ([mary 'moore]
[melissa 'barnacle]
[lorna (amb 'downing 'hall 'parker)]
[rosalind (amb 'downing 'hall 'parker)]
[gabrielle (amb 'downing 'hall 'parker)])
(require (not (eq? lorna 'moore)))
(require (not (eq? rosalind 'hall)))
(require (not (eq? gabrielle 'barnacle)))
(require (cond [(eq? gabrielle 'downing) (eq? melissa 'parker)]
[(eq? gabrielle 'hall) (eq? rosalind 'parker)]
[else false]))
(require (distinct? (list mary melissa lorna rosalind gabrielle)))
(list (list 'mary mary)
(list 'melissa melissa)
(list 'lorna lorna)
(list 'rosalind rosalind)
(list 'gabrielle gabrielle))))
; 4.44
;
; It has to be runned in the amb evaluator. Racket's SICP package doesn't
; revert the assignment before choosing another branch.
(define (amb-list xs)
(require (not (null? xs)))
(amb (car xs) (amb-list (cdr xs))))
(define (check? x y)
(let ([ax (car x)]
[dx (cadr x)]
[ay (car y)]
[dy (cadr y)])
(or (= ax ay)
(= dx dy)
(= (abs (- ax ay)) (abs (- dx dy))))))
(define (range hi)
(define (loop lo)
(if (>= lo hi)
'()
(cons lo (loop (+ lo 1)))))
(loop 0))
(define (ormap f xs)
(cond
[(null? xs) false]
[(f (car xs)) true]
[else (ormap f (cdr xs))]))
(define (queens n)
(define answer '())
(define (loop col)
(cond
[(> col (- n 1)) (require (= (length answer) n)) answer]
[else (let ([row (amb-list (range n))])
(require (not (ormap (lambda (p) (check? (list row col) p)) answer)))
(set! answer (cons (list row col) answer))
(loop (+ col 1)))]))
(loop 0))
; ex 4.45
;
; 1. lectures -> to the student in the class with the cat
; 2. in the class, lectures with the cat -> to the student
; 3. in the class, lectures -> to the student with the cat
; 4. in the class (that is) with the cat, lectures -> to the student
; 5. lectures with the cat -> to the student in the class
; TODO ex 4.46
; TODO ex 4.47
; TODO ex 4.48
; TODO ex 4.49