; maximum product of three
 
(define (take n xs)
  (let loop ((n n) (xs xs) (ys '()))
    (if (or (zero? n) (null? xs))
        (reverse ys)
        (loop (- n 1) (cdr xs)
              (cons (car xs) ys)))))
 
(define (last xs)
  (cond ((null? xs) (error 'last "empty input"))
        ((null? (cdr xs)) (car xs))
        (else (last (cdr xs)))))
 
(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 (max-prod-three xs)
  (let ((len (length xs)) (xs (sort xs <)))
    (cond ((< len 3) (error 'max-prod-three "insufficient input"))
          ((= len 3) (apply * xs))
          ((not (negative? (car xs)))
            (apply * (take 3 (reverse xs))))
          ((negative? (last xs))
            (apply * (take 3 (reverse xs))))
          ((and (negative? (car xs)) (positive? (cadr xs)))
            (apply * (take 3 (reverse xs))))
          ((and (negative? (cadr xs))
                (negative? (caddr (reverse xs))))
            (* (car xs) (cadr xs) (last xs)))
          ((and (negative? (cadr xs))
                (positive? (caddr (reverse xs))))
            (max (apply * (take 3 (reverse xs)))
                 (* (car xs) (cadr xs) (last xs))))
          (else (error 'max-prod-three "missed case")))))

(define (test-max-prod-three)
  (assert (+ 1 1) 3) ; testing assert
  (assert (max-prod-three '(1 2 3)) 6)
  (assert (max-prod-three '(-1 -2 -3)) -6)
  (assert (max-prod-three '(1 2 3 4)) 24)
  (assert (max-prod-three '(-1 2 3 4)) 24)
  (assert (max-prod-three '(1 -2 3 4)) 12)
  (assert (max-prod-three '(1 2 -3 4)) 8)
  (assert (max-prod-three '(1 2 3 -4)) 6)
  (assert (max-prod-three '(-1 -2 -3 -4)) -6)
  (assert (max-prod-three '(1 -2 -3 -4)) 12)
  (assert (max-prod-three '(-1 2 -3 -4)) 24)
  (assert (max-prod-three '(-1 -2 3 -4)) 24)
  (assert (max-prod-three '(-1 -2 -3 4)) 24)
  (assert (max-prod-three '(1 2 3 4 5)) 60)
  (assert (max-prod-three '(-1 -2 -3 -4 -5)) -6)
  (assert (max-prod-three '(1 2 -3 -4 -5)) 40)
  (assert (max-prod-three '(-1 -2 3 4 5)) 60)
  (assert (max-prod-three '(-1 -2 -3 4 5)) 30)
  (assert (max-prod-three '(1 -2 3 -4 5)) 40)
  (assert (max-prod-three '(-1 2 -3 4 -5)) 60)
  (assert (max-prod-three '(1 2 3 4 -5)) 24)
  (assert (max-prod-three '(-1 2 3 4 5)) 60)
  (assert (max-prod-three '(-1 -2 -3 -4 5)) 60)
  (assert (max-prod-three '(1 -2 -3 -4 -5)) 20)
  (assert (max-prod-three '(1 2 3 4 5 6 7)) 210)
  (assert (max-prod-three '(0 1 2 3)) 6)
  (assert (max-prod-three '(0 -1 -2 -3)) 0))
 
(test-max-prod-three)