; 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))
          ((positive? (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))

(test-max-prod-three)