#lang racket
(require gigls/unsafe)

;;; File:
;;;   exam4.rkt
;;; Authors:
;;;   The student currently referred to as 000000
;;;   Charlie Curtsinger
;;;   Titus Klinge
;;; Contents:
;;;   Code and solutions for Exam 4 2016F
;;; 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:

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

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define read-dictionary
  (lambda (filename)
    0))

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define is-resilient?
  (lambda (word dictionary)
    0))

; Extra Credit Solution:

; Examples/Tests:


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

; Time Spent: 

; Citations:

; Solution:
;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define count-pairs
  (lambda (value)
    0))

; Examples/Tests:


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

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define print-tree!
  (lambda (root)
    0))

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define print-reverse-tree!
  (lambda (root)
    0))

; Examples/Tests:


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

; Time Spent: 

; Citations:

; Provided Code:

; Documentation for counter-new appears later in the exam, but this procedure
; must appear before the counters below.
(define counter-new
  (lambda (name)
    (vector name 0)))

(define cons-counter (counter-new "cons"))
(define car-counter (counter-new "car"))
(define cdr-counter (counter-new "cdr"))
(define null?-counter (counter-new "null?"))

;;; Procedure:
;;;   reset-counters!
;;; Parameters:
;;;   none
;;; Purpose:
;;;   reset the counters used for problem 4
;;; Produces:
;;;   nothing
;;; Preconditions:
;;;   no additional
;;; Postconditions:
;;;   the values of the four counters used in problem 4 will be zero
(define reset-counters!
  (lambda ()
    (counter-reset! cons-counter)
    (counter-reset! car-counter)
    (counter-reset! cdr-counter)
    (counter-reset! null?-counter)))

;;; Procedure:
;;;   print-counters!
;;; Parameters:
;;;   none
;;; Purpose:
;;;   display the current values of the counters for problem 4
;;; Produces:
;;;   nothing
;;; Preconditions:
;;;   no additional
;;; Postconditions:
;;;   the values of the four counters used in problem 4 will be printed
(define print-counters!
  (lambda ()
    (counter-print! cons-counter)
    (counter-print! car-counter)
    (counter-print! cdr-counter)
    (counter-print! null?-counter)))

(define $cons
  (lambda (first second)
    (counter-count! cons-counter)
    (cons first second)))

(define $car
  (lambda (pair)
    (counter-count! car-counter)
    (car pair)))

(define $cdr
  (lambda (pair)
    (counter-count! cdr-counter)
    (cdr pair)))

(define $null?
  (lambda (val)
    (counter-count! null?-counter)
    (null? val)))

(define $make-list
  (lambda (len val)
    (if (zero? len)
        null
        ($cons val ($make-list (- len 1) val)))))

(define $iota
  (lambda (n)
    (let kernel [(i 0)]
      (if (= i n)
          null
          ($cons i (kernel (+ i 1)))))))

(define $map1
  (lambda (fun lst)
    (if ($null? lst)
        null
        ($cons (fun ($car lst))
              ($map1 fun ($cdr lst))))))

(define $map2
  (lambda (fun lst1 lst2)
    (if (or ($null? lst1) ($null? lst2))
        null
        ($cons (fun ($car lst1) ($car lst2))
              ($map2 fun ($cdr lst1) ($cdr lst2))))))

(define $map3
  (lambda (fun lst1 lst2 lst3)
    (if (or ($null? lst1) ($null? lst2) ($null? lst3))
        null
        ($cons (fun ($car lst1) ($car lst2) ($car lst3))
              ($map3 fun ($cdr lst1) ($cdr lst2) ($cdr lst3))))))

; Solution:

; a. Update the procedure below to use the counted versions of cons, car,
;    cdr, map, make-list, null?, and iota.

(define many-circles
  (lambda (n)
    (map vshift-drawing
         (map *
              (make-list n 10)
              (map modulo
                   (iota n)
                   (make-list n 10)))
         (map hshift-drawing
              (map *
                   (make-list n 5)
                   (iota n))
              (map scale-drawing
                   (map increment
                        (map modulo
                             (iota n)
                             (make-list n 7)))
                   (make-list n drawing-unit-circle))))))

; b.
;
;         cons        car        cdr          null?
;     +-----------+---------+------------+-------------+
;   5 |           |         |            |             |
;     +-----------+---------+------------+-------------+
;  10 |           |         |            |             |
;     +-----------+---------+------------+-------------+
;  20 |           |         |            |             |
;     +-----------+---------+------------+-------------+
;  40 |           |         |            |             |
;     +-----------+---------+------------+-------------+


; c.
;
;         cons        car        cdr          null?
;     +-----------+---------+------------+-------------+
;   n |           |         |            |             |
;     +-----------+---------+------------+-------------+

; d.
(define new-many-circles
  (lambda (n)
    (list drawing-unit-circle)))

; Examples/Tests:


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

; Time Spent: 

; Citations:

; Solution:

;; Modify and document the procedure below according to the exam's instructions.

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define    daffy
(lambda (  puddles        )
  (let ([  darkwing       (lambda (
           donald
           huey
           count-duckula  ) (let ([
           louie          (vector-ref
           donald
           huey           )][
           dewey          (vector-ref
           donald
           count-duckula  )]) (vector-set!
           donald
           huey
           dewey          )(vector-set!
           donald
           count-duckula
           louie          )))]) (map (l-s
    apply  darkwing       )(map list (make-list (quotient (vector-length
           puddles        ) 2)
           puddles        )(iota (quotient (vector-length
           puddles        ) 2))(map (r-s - 1) (map (l-s - (vector-length
           puddles        )) (iota (quotient (vector-length
           puddles        ) 2)))))))
           puddles        ))

; Examples/Tests:


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

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   nest
;;; Parameters:
;;;   n, an integer
;;;   fun, a procedure
;;; Purpose:
;;;   nest creates a new procedure than nests n calls to fun
;;; Produces:
;;;   nested, a procedure
;;; Preconditions:
;;;   The value of n must be greater than or equal to zero.
;;;   The procedure fun must accept one parameter, and must return a
;;;   value that can be used as a parameter to a subsequent call to fun.
;;; Postconditions:
;;;   calling nested on a parameter is equivalent to nesting n calls to
;;;   fun, where the parameter to nested is passed as the parameter to
;;;   the innermost call to fun.
;;;   For example, for the result of (nest 3 square), calling (nested x)
;;;   is equivalent to calling (square (square (square x))).
(define nest
  (lambda (n fun)
    0))

; Examples/Tests:


; ===================================================================

; THE CODE BELOW THIS LINE WAS SUPPLIED WITH THE EXAM.  PLEASE LEAVE
; IT IN PLACE IN THE ELECTRONIC VERSION OF THE EXAM!

; +-----------------+------------------------------------------------
; | Tree Procedures |
; +-----------------+

; + --- Tree Constructors -----------------------

;;; Name:
;;;   empty
;;; Type:
;;;   tree
;;; Value:
;;;   The empty tree
(define empty 'empty)

;;; Procedure:
;;;   leaf
;;; Parameters:
;;;   val, a value
;;; Purpose:
;;;   Make a leaf node.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents tree) = val
;;;   (left tree) = empty
;;;   (right tree) = empty
(define leaf
  (lambda (val)
    (node val empty empty)))

;;; Procedure:
;;;   node
;;; Parameters:
;;;   val, a value
;;;   left-subtree, a tree
;;;   right-subtree, a tree
;;; Purpose:
;;;   Create a node in a binary tree.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (node? tree) holds.
;;;   (left tree) = left-subtree.
;;;   (right tree) = right-subtree.
;;;   (contents tree) = val.
(define node
  (lambda (val left right)
    (vector 'node val left right)))

; + --- Tree Observers -----------------------

;;; Procedure:
;;;   contents
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the contents of node.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents (node val l r)) = val
(define contents
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "contents requires a node, received" nod)]
      [else
       (vector-ref nod 1)])))

;;; Procedure:
;;;   left
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the left subtree of nod.
;;; Produces:
;;;   l, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (left (node val l r)) = l
(define left
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "left requires a node, received" nod)]
      [else
       (vector-ref nod 2)])))

;;; Procedure:
;;;   right
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the right subtree of nod.
;;; Produces:
;;;   r, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (right (node val l r)) = r
(define right
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "right requires a node, received" nod)]
      [else
       (vector-ref nod 3)])))

; + --- Tree Observers -----------------------

;;; Procedure:
;;;   empty?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val represents an empty tree.
;;; Produces:
;;;   is-empty?, a Boolean 
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   is-empty? is true (#t) if and only if val can be interpreted as
;;;   the empty tree.
(define empty? 
  (l-s eq? empty))

;;; Procedure:
;;;   leaf?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val is a tree leaf
;;; Produces:
;;;   is-leaf?, a Boolean
(define leaf?
  (lambda (val)
    (and (node? val)
         (empty? (left val))
         (empty? (right val)))))

;;; Procedure:
;;;   node?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val can be used as a tree node.
;;; Produces:
;;;   is-node?, a Boolean
(define node?
  (lambda (val)
    (and (vector? val)
         (= (vector-length val) 4)
         (eq? (vector-ref val 0) 'node))))

; +--------------------------------+----------------------------------
; | Generalized Counter Procedures |
; +--------------------------------+

;;; Procedure:
;;;   counter-new
;;; Parameters:
;;;   name, a string
;;; Purpose:
;;;   Create a counter associated with the given name.
;;; Produces:
;;;   counter, a counter
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   counter can be used as a parameter to the various counter
;;;   procedures.
;;; Process:
;;;   Counters are two element vectors.  Element 0 is the name, and
;;;   should not change.  Element 1 is the count, and should change.

; The implementation of this procedure appears in the section for problem 4

;;; Procedure:
;;;   counter-count!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   count the counter
;;; Produces:
;;;   counter, the same counter, now mutated
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives a number one higher than it 
;;;   did before.
(define counter-count!
  (lambda (counter)
    (vector-set! counter 1 (+ 1 (vector-ref counter 1)))
    counter))

;;; Procedure:
;;;   counter-get
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Get the number of times that counter-count! has been called
;;;   on this counter.
;;; Produces:
;;;   count, a non-negative integer
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the counter procedures.
;;; Postconditions:
;;;   count is the number of calls to counter-new on this counter since
;;;   the last call to counter-reset! on this counter, or since the
;;;   counter was created, if there have been no calls to counter-reset!
(define counter-get
  (lambda (counter)
    (vector-ref counter 1)))

;;; Procedure:
;;;   counter-reset!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   reset the counter
;;; Produces:
;;;   counter, the same counter, now set to 0
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the other counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives 0.
(define counter-reset!
  (lambda (counter)
    (vector-set! counter 1 0)
    counter))

;;; Procedure:
;;;   counter-print!
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Print out the information associated with the counter.
;;; Produces:
;;;   counter, the same counter
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the various counter procedures.
;;; Postconditions:
;;;   counter is unchanged.
;;;   The output port now contains information on counter.
;;; Ponderings:
;;;   Why does counter-print! have a bang, given that it doesn't mutate
;;;   it's parameter?  Because it mutates the broader environment - we
;;;   call counter-print! not to compute a value, but to print something.
(define counter-print!
  (lambda (counter)
    (display (vector-ref counter 0))
    (display ": ")
    (display (vector-ref counter 1))
    (newline)))