; median of five

(define (permutations xs)
  (define (rev xs n ys)
    (if (zero? n) ys
      (rev (cdr xs) (- n 1) (cons (car xs) ys))))
  (let ((xs xs) (perms (list xs)))
    (define (perm n)
      (if (> n 1)
          (do ((j (- n 1) (- j 1)))
              ((zero? j) (perm (- n 1)))
            (perm (- n 1))
            (set! xs (rev xs n (list-tail xs n)))
            (set! perms (cons xs perms)))))
    (perm (length xs))
    perms))

(define-syntax assert
  (syntax-rules ()
    ((assert expr result)
      (if (not (equal? expr result))
          (for-each display `(
            #\newline "failed assertion:" #\newline
            expr #\newline "expected: " ,result
            #\newline "returned: " ,expr #\newline))))))

(define (median5 lt? a b c d e)
  (when (lt? b a)
    (let ((t a)) (set! a b) (set! b t)))
  (when (lt? e d)
    (let ((t d)) (set! d e) (set! e t)))
  (when (lt? d a)
    (let ((t a)) (set! a d) (set! d t))
    (let ((t b)) (set! b e) (set! e t)))
  (if (lt? b c)
      (if (lt? b d)
          (if (lt? c d) c d)
          (if (lt? b e) b e))
      (if (lt? d c)
          (if (lt? c e) c e)
          (if (lt? b d) b d))))

; no news is good news
(for-each (lambda (perm) (assert (apply median5 < perm) 3))
          (permutations '(1 2 3 4 5)))

(display (median5 < 1 2 3 4 5)) (newline)
(display (median5 < 5 4 3 2 1)) (newline)

3
3