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