#lang racket
(require csc151)
(require plot)
(require rackunit)
(require rackunit/text-ui)

;;; File:
;;;   000000.rkt
;;; Authors:
;;;   The student currently referred to as 000000
;;;   Titus Klinge
;;;   Samuel A. Rebelsky
;;; Contents:
;;;   Code and solutions for Exam 3 2018S
;;; Citations:
;;;

;; +---------+--------------------------------------------------------
;; | Grading |
;; +---------+

;; This section is for the grader's use.

;; Problem 1: 
;; Problem 2:
;; Problem 3:
;; Problem 4:
;; Problem 5:
;; Problem 6:
;;           ----
;;     Total:

;;    Scaled:
;;    Errors:
;;     Times:
;;          :
;;          :
;;          :
;;           ----
;;     Total:

;; +----------+-------------------------------------------------------
;; | Prologue |
;; +----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

;; +-----------+------------------------------------------------------
;; | Problem 1 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   partition-numbers
;;; Parameters:
;;;   numbers, a 
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define partition-numbers
  (lambda (numbers)
    (list numbers numbers numbers))) ; STUB

; Examples/Tests:

(define partition-numbers-tests
  (test-suite
   "tests of partition-numbers"
   (test-case 
    "values in order"
    (check-equal? (partition-numbers (list -3 -2 -1 0 1 2 3))
                  '((-3 -2 -1) (0) (1 2 3)))
    (check-equal? (partition-numbers (list -4 -3 -2 -1))
                  '((-4 -3 -2 -1) () ()))
    (check-equal? (partition-numbers (list 5 6 7 8))
                  '(() () (5 6 7 8))))
   (test-case
    "empty list"
    (check-equal? (partition-numbers null)
                  '(() () ())))
   (test-case
    "mixed values, all integers"
    (check-equal? (partition-numbers (list 6 4 0 0 -5 9 -11))
                  '((-5 -11) (0 0) (6 4 9)))
    (check-equal? (partition-numbers (list 5 1 -3 0 2 -4 8 0 3 -5))
                  '((-3 -4 -5) (0 0) (5 1 2 8 3))))
   (test-case
    "mixed values, mixed types"
    (check-equal? (partition-numbers (list -3.2 1/2 0 4.2 0.0 8/3 0 -7/2))
                  '((-3.2 -7/2) (0 0.0 0) (1/2 4.2 8/3))))
   (test-case
    "mixed order, all same sign"
    (check-equal? (partition-numbers (list -5 -1 -8 -3))
                  '((-5 -1 -8 -3) () ()))
    (check-equal? (partition-numbers (list 5 1 8 3))
                 '(() () (5 1 8 3))))
   (test-case
    "identical values"
    (check-equal? (partition-numbers (list -4 -4 -4))
                  '((-4 -4 -4) () ()))
    (check-equal? (partition-numbers (list 0 0 0 0 0))
                  '(() (0 0 0 0 0) ()))
    (check-equal? (partition-numbers (list 7 7 7))
                  '(() () (7 7 7))))))



;; +-----------+------------------------------------------------------
;; | Problem 2 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   remove-duplicates
;;; Parameters:
;;;   lst, 
;;; Purpose:
;;;   
;;; Produces:
;;;   
(define remove-duplicates
  (lambda (lst)
    lst)) ; STUB

; Examples/Tests:

(define remove-duplicates-tests
  (test-suite
   "tests of remove-duplicates"
   (test-case
    "examples from exam"
    (check-equal? (remove-duplicates '(d b a e b d f a q s f a a a b))
                  '(d b a e f q s))
    (check-equal? (remove-duplicates '(d b a e b d f a q s f a a a b 
                                       s a m r i s b o r e d))
                  '(d b a e f q s m r i o)))
   (test-case
    "empty list"
    (check-equal? (remove-duplicates null)
                  '()))
   (test-case
    "multiple types"
    (check-equal? (remove-duplicates (list 'a "a" 8 8 #t "a" 8 'a '(a)))
                  '(a "a" 8 #t (a)))
    (check-equal? (remove-duplicates (list '(a) '(b) '(a b) '(b) '(a) "eh"))
                  '((a) (b) (a b) "eh")))
   (test-case
    "all identical"
    (check-equal? (remove-duplicates (list 'a 'a 'a 'a 'a))
                  '(a)))
   (test-case
    "long list"
    (check-equal? (remove-duplicates (iota 1000))
                  (iota 1000))
    (check-equal? (remove-duplicates (append (iota 999) (iota 999) (iota 999)))
                  (iota 999))
    (check-equal? (remove-duplicates (append (make-list 500 'a) 
                                             (make-list 400 'b)
                                             (make-list 350 'a)))
                  '(a b)))))


;; +-----------+------------------------------------------------------
;; | Problem 3 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   palindrome?
;;; Parameters:
;;;   str, a 
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define palindrome?
  (lambda (str)
    #f)) ; STUB

; Examples/Tests:

(define palindrome-tests
  (test-suite
   "tests of palindrome?"
   (test-case
    "boring palindromes of even and odd lengths"
    (check-true (palindrome? "a"))
    (check-true (palindrome? "aa"))
    (check-true (palindrome? "aaa"))
    (check-true (palindrome? "aba"))
    (check-true (palindrome? "aaaa"))
    (check-true (palindrome? "abba"))
    (check-true (palindrome? "aaaaa"))
    (check-true (palindrome? "aacaa"))
    (check-true (palindrome? "abcba"))
    (check-true (palindrome? "abbba"))
    (check-true (palindrome? "aaaaaa"))
    (check-true (palindrome? "abaaba"))
    (check-true (palindrome? "aaccaa"))
    (check-true (palindrome? "abccba"))
    (check-true (palindrome? "abbbba")))
   (test-case
    "edge case: empty string"
    (check-true (palindrome? "")))
   (test-case
    "longer traditional palindromes"
    (check-true (palindrome? "civic"))
    (check-true (palindrome? "madamimadam"))
    (check-true (palindrome? "amanaplanacanalpanama")))
   (test-case 
    "edge case: long strings"
    (check-true (palindrome? (string-append (make-string 300 #\a)
                                            (make-string 500 #\b)
                                            (make-string 300 #\a))))
    (check-true (palindrome? (string-append "b"
                                            (make-string 500 #\a)
                                            "c"
                                            (make-string 500 #\a)
                                            "b"))))
   (test-case
    "near palindromes"
    (check-false (palindrome? "aaba"))
    (check-false (palindrome? "abaa"))
    (check-false (palindrome? "abcdba"))
    (check-false (palindrome? "xmadamimadamy")))
   (test-case
    "inconsistent case"
    (check-false (palindrome? "aaA"))
    (check-false (palindrome? "MadamImAdam"))
    (check-false (palindrome? "AManAPlanACanalPanama")))))


;; +-----------+------------------------------------------------------
;; | Problem 4 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   square-root
;;; Parameters:
;;;   n, a
;;;   epsilon, a 
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define square-root
  (lambda (n epsilon)
    n)) ; STUB

; Examples/Tests:

;;; Procedure:
;;;   check-square-root
;;; Parameters:
;;;   n, a real number greater than or equal to 1.
;;;   epsilon, a positive real number
;;; Purpose:
;;;   Checks whether the square-root procedure computes a square root
;;;   of n whose square is within epsilon of n.
;;; Produces:
;;;   [Nothing; called for potential side effects]
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * If (square (square-root n epsilon)) is within epsilon of n,
;;;     does nothing.
;;;   * Otherwise, throws an error.
(define check-square-root
  (lambda (n epsilon)
    (check-= (square (square-root n epsilon)) n epsilon)))

(define square-root-tests
  (test-suite
   "tests of square-root"
   (test-case
    "basic tests"
    (check-square-root 2 .1)
    (check-square-root 2 .01)
    (check-square-root 2 .001)
    (check-square-root 2 .0001)
    (check-square-root 4 .00000001)
    (check-square-root 9 .000001)
    (check-square-root 5 .001)
    (check-square-root 3.0 .0001))
   (test-case
    "edge case: large numbers"
    (check-square-root (expt 5 30) 1))
   (test-case
    "edge case: 1"
    (check-square-root 1 .0001))
   (test-case
    "fractions"
    (check-square-root 3/2 1/10000)
    (check-square-root 75/7 1/10000))))


;; +-----------+------------------------------------------------------
;; | Problem 5 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Provided code

;;; Procedure:
;;;   heads?
;;; Parameters:
;;;   [None]
;;; Purpose:
;;;   Flip a coin and determine whether or not it is heads.
;;; Produces:
;;;   is-heads?, a Boolean value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   The result is hard to predict.
(define heads?
  (lambda ()
    (zero? (random 2))))

;;; Procedure:
;;;   count-heads
;;; Parameters:
;;;   n, a positive integer
;;; Purpose:
;;;   Call `heads?` `n` times and report how many times we got heads.
;;; Produces:
;;;   head-count, a non-negative integer
(define count-heads
  (lambda (n)
    (cond
      [(zero? n)
       0]
      [(heads?)
       (+ 1 (count-heads (- n 1)))]
      [else
       (count-heads (- n 1))])))

; Solution:

;;; Procedure:
;;;   count-heads-study
;;; Parameters:
;;;   n, a positive integer
;;;   trials, a positive integer
;;; Purpose:
;;;   Determine whether the `count-heads` procedure provides a normal
;;;   distribution of results.
;;; Produces:
;;;   plot, a racket scatter plot object
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * plot represents an experiment in which we call 
;;;     `(count-heads n)` `trials` times.
(define count-heads-study
  (lambda (n trials)
    (plot (points (list '(1 1) '(2 3) '(3 5) '(4 3) '(5 1)))))) ; STUB

; Examples/Tests:

;; +-----------+------------------------------------------------------
;; | Problem 6 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Supplied code

; Solution:

; a.

;;; Procedure:
;;;   
;;; Parameters:
;;;   
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   

; b.

(define s
  (lambda (l)
    (let kernel ([a null]
                 [b null]
                 [c l])
      (cond
        [(null? c)
         (list (reverse a) (reverse b))]
        [(number? (car c))
         (kernel (cons (car c) a) b (cdr c))]
        [else
         (kernel a (cons (car c) b) (cdr c))]))))

; c. Why are there two calls to `reverse` in the base case?

; Examples/Tests: