Pasted

#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).