Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #lang racket
- ;;;;;;;;;;
- ;; 4.35 ;;
- ;;;;;;;;;;
- (define (an-integer-between low high)
- (my-require (<= low high))
- (amb low (an-integer-between (add1 low) high)))
- ;; or equivalently:
- (define (an-integer-between2 low high)
- (an-element-of (range low (add1 high))))
- ;;;;;;;;;;
- ;; 4.36 ;;
- ;;;;;;;;;;
- ;; Depth-first search would search all k values before incrementing i or j. So we
- ;; would never see a triple like (1, 2, 2). We would only see (1, 1, 1), (1, 1, 2),
- ;; (1, 1, 3), etc.
- ;; Define the weight of a triple to be the sum of its indices. Then search through
- ;; triples by weight:
- (define (a-triple-of-weight n)
- (let* ([i (an-integer-between 1 n)]
- [j (an-integer-between i n)]
- [k (an-integer-between j n)])
- (my-require (= (+ i j k) n))
- (list i j k)))
- ;; Combine this with an-integer-starting-from to eventually get all triples:
- (define (an-integer-starting-from n)
- (amb n (an-integer-starting-from (add1 n))))
- (define (a-triple)
- (let ([n (an-integer-starting-from 3)])
- (a-triple-of-weight n)))
- ;;;;;;;;;;
- ;; 4.37 ;;
- ;;;;;;;;;;
- ;; Ben's solution will be much faster for large values of high. He searches for i
- ;; through the same range. He searches for j through a smaller range, because of the
- ;; hsq >= ksq requirement. And he doesn't search for k at all. He determines k from
- ;; i and j.
- ;; I think the first approach will be O(n^3) and Ben's will be O(n^2).
Advertisement
