;;Practice exam solutions:  CMPU 101 Exam 2 Practice exam, Spring 2013

; 
; Problem 1:
; 
;    Write a function PR-SQR that takes a string (str) and a number 
;    (n) as input and prints a n x n square of the str.  This 
;    function should not return anything, it should just have side-
;    effect printing.  Examples of running the function are given
;    below:
;    
;    > (pr-sqr "X" 4)
;    XXXX
;    XXXX
;    XXXX
;    XXXX
;    
;    > (pr-sqr "X " 5)
;    X X X X X
;    X X X X X
;    X X X X X
;    X X X X X
;    X X X X X
;    
;    Recall the print-upper-diagonal function you wrote in ***,
;    The final pr-sqr should use a helper function to print a
;    line of the given symbols and either a helper or an internal
;    function to call the function that prints a line.
;    


;; NOTE THAT THERE ARE MANY DIFFERENT SOLUTIONS TO THIS 
;; AND OTHER PROBLEMS.

;; Contract: (pr-sqr string num) -> side-effect printing
;; Header:   (define pr-sqr (lambda (str n) ... ))
;; Purpose: to print n rows and n columns of str

;; No pre-tests possible with side-effect printing

;; function:
(define pr-sqr 
  (lambda (str n)
    (pr-sqr-helper str n n)))
  

;; Contract: (pr-sqr-helper string num num) -> side-effect printing
;; Header:   (define pr-sqr-helper (lambda (str n i) ... ))
;; purpose: to print n rows and n columns of str using i as a counter

;; No pre-tests possible with side-effect printing

; function
(define pr-sqr-helper 
  (lambda (str n i)
    (cond 
      [(= i 0) (newline)]
      [else
       (begin
         (pr-ln str n)
         (pr-sqr-helper str n (- i 1)))])))

;; Contract: (pr-ln string num) -> side-effect printing
;; Header:   (define pr-ln (lambda (str n) ... ))
;; Purpose: to print a row of n copies of str 

;; No pre-tests possible with side-effect printing

;function:
(define pr-ln 
  (lambda (str n)
    (cond
      [(= n 0) (newline)]
      [else
       (begin
         (printf "~a" str)
         (pr-ln str (- n 1)))])))

; post-tests:
(display "\n(pr-ln \"X \" 8) => ")
(pr-ln "X " 8)
(display "\n(pr-ln \"O \" 4) => ") 
(pr-ln "O " 4)

; post-tests: Can't test pr-sqr-helper until pr-ln is written
(display "\n(pr-sqr-helper \"X \" 8 8) =>\n")
(pr-sqr-helper "X " 8 8)
(display "\n(pr-sqr-helper \"0 \" 7 7)) =>\n")
(pr-sqr-helper "0 " 7 7)
(display "\n(pr-sqr-helper \"ME \" 0 0)) =>\n")
(pr-sqr-helper "ME " 0 0)

; post-tests: Can't test pr-sqr until pr-sqr-helper is written
(display "\n(pr-sqr \"O \" 8))\n")
(pr-sqr "O " 8)
(display "\n(pr-sqr \"O \" 7))\n")
(pr-sqr "O " 7)
(display "\n(pr-sqr \"O \" 0))\n")
(pr-sqr "O " 0)

; 
; Problem 2:
; 
; (a) The sum of the squares of the natural numbers from 0 to n is  
;     given as 
;    
;              1^2 + 2^2 + 3^2 +...+ n^2
;              
;     Write a recursive function SUM-SQ that takes a natural number 
;     n and computes the sum of the squares up to n.
;     
; (b) Write the same function as in part (a), but use an accumula-
;     tor.
;    
;    
;    
; (b) The value computed in part (a) is equal to the following:
;     
;                    (n(n+1)(2n+1))/6
;                    
;     Write a function EQ-SQ that computes the equation given 
;     above and use check-expect statements to show the equality 
;     of the expressions from parts (a) and (b).
;    

; Contract: (sum-sq number) -> number
; Header:   (define sum-sq (lambda (n) ... ))
; Purpose:  Calculate the sum of squares from 1 to n.
; Pre-function tests:
(check-expect (sum-sq 4) 30)
(check-expect (sum-sq 5) 55)
(check-expect (sum-sq 0) 0)
; Function definition
(define sum-sq 
  (lambda (n)
    (cond
      [(= n 0) 0]
      [else
       (+ (sqr n) (sum-sq (sub1 n)))])))

(display "\n(sum-sq 4) => ")
(sum-sq 4)
(display "\n(sum-sq 5) => ")
(sum-sq 5)
(display "\n(sum-sq 0) => ")
(sum-sq 0)

; Contract: (sum-sq-acc number) -> number
; Header:   (define sum-sq-acc (lambda (n) ... ))
; Purpose:  Calculate the sum of squares from 1 to n.
; Pre-function tests:
(check-expect (sum-sq-acc 4) 30)
(check-expect (sum-sq-acc 5) 55)
(check-expect (sum-sq-acc 0) 0)
; Function definition
(define sum-sq-acc 
  (lambda (n)
    (local
      [(define helper 
         (lambda (n acc)
           (cond
             [(= n 0) acc]
             [else
              (helper (sub1 n) (+ (sqr n) acc))])))]
      (helper n 0))))

(display "\n(sum-sq-acc 4) => ")
(sum-sq-acc 4)
(display "\n(sum-sq-acc 5) => ")
(sum-sq-acc 5)
(display "\n(sum-sq-acc 0) => ")
(sum-sq-acc 0)

; Contract: (sum-sq-ho number) -> number
; Header:   (define sum-sq-ho (lambda (n) ... ))
; Purpose:  Calculate the sum of squares from 1 to n.
; Pre-function tests:
(check-expect (sum-sq-ho 4) 30)
(check-expect (sum-sq-ho 5) 55)
(check-expect (sum-sq-ho 0) 0)
; Function definition
(define sum-sq-ho 
  (lambda (n)
    (apply + (map sqr (build-list n add1)))))
  

(display "\n(sum-sq-ho 4) => ")
(sum-sq-ho 4)
(display "\n(sum-sq-ho 5) => ")
(sum-sq-ho 5)
(display "\n(sum-sq-ho 0) => ")
(sum-sq-ho 0)

;; Contract: (eq-sq number) -> number
;; Header:   (define eq-sq (lambda (n) ... ))
;; Purpose:  Same as part (a) (n(n+1)(2n+1))/6

; Pre-function tests:
(check-expect (eq-sq 4) 30)
(check-expect (eq-sq 5) 55)
(check-expect (eq-sq 0) 0)

; Function definition
(define eq-sq 
  (lambda (n)
    (/ (* n (+ n 1) (+ (* 2 n) 1)) 6))) 

(display "\n(eq-sq 4) => ")
(eq-sq 4)
(display "\n(eq-sq 5) => ")
(eq-sq 5)
(display "\n(eq-sq 0) => ")
(eq-sq 0)

(check-expect (eq-sq 4) (sum-sq 4))
(check-expect (eq-sq 0) (sum-sq 0))
(check-expect (eq-sq 14) (sum-sq 14))


; 
; Problem 3:
; 
;    Write a predicate function called SMALL-VALUE? that takes in a 
;    data item (any valid Racket entity) as input and that returns
;    #t if the input is a Boolean value or a number between 0 and 
;    20 (including 0 and 20).  For full credit, your solution 
;    should not use an if or a cond.  If you have trouble writing
;    a solution with no decision statements, try writing the 
;    function with a decision statement first and it might give 
;    you some insight into writing it without if or cond.
;    
;    > (small-value? 7)
;    #t
;    
;    > (small-value? #f) 
;    #t
;    
;    > (small-value? 'foo)
;    #f
;    


; Contract: (small-value? anything) -> boolean
; Header:   (define small-value? (lambda (thing) ... ))
; purpose:  Return true iff thing is boolean or 0 to 20

; pre-tests:
(check-expect (small-value? "Hi") #f)
(check-expect (small-value? #t) #t)
(check-expect (small-value? 0) #t)
(check-expect (small-value? 30) #f)

; function:
(define small-value? 
  (lambda (thing)
    (or (boolean? thing)
        (and (number? thing)
             (and (<= 0 thing) (>= 20 thing))))))

; post-tests:
(display "\n(small-value? true)) => ")
(small-value? true)
(display "\n(small-value? 10)) => ")
(small-value? 10)
(display "\n(small-value? 23)) => ")
(small-value? 23)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ALTERNATE VERSION using cond, if, and literal
; booleans.  NOTE: the function above uses much
; better coding practices!!

; pre-tests:
(check-expect (small-value-v2? "Hi") #f)
(check-expect (small-value-v2? #t) #t)
(check-expect (small-value-v2? 0) #t)
(check-expect (small-value-v2? 30) #f)

(define small-value-v2? 
  (lambda (thing)
    (cond
      [(boolean? thing) #t]
      [(number? thing)
       (if (and (<= 0 thing) (>= 20 thing))
           #t 
           #f
           )]
      [else #f])))

; post-tests:
(display "\n(small-value-v2? true)) ")
(small-value-v2? true)
(display "\n(small-value-v2? 10)) ")
(small-value-v2? 10)
(display "\n(small-value-v2? 23)) ")
(small-value-v2? 23)

; 
; Problem 4:
; 
;    Write a function called KEEP-SYMBOLS that takes a list of any  
;    length and containing any valid Racket types and returns a
;    list containing only the quoted symbols found in the input 
;    list.
;    
;    > (keep-symbols '(a b c))
;    (list 'a 'b 'c)
;    
;    > (keep-symbols empty)
;    empty
;    
;    > (keep-symbols '(3 4 6 a))
;    (list 'a)
;    

; Contract: (keep-symbols list-of-anything) -> list of symbols
; Header:   (define keep-symbols (lambda (listy) ... ))
; Purpose:  Create a list with only the symbols from listy

; pre-tests:
(check-expect (keep-symbols '(a b 5 6 d)) '(a b d))
(check-expect (keep-symbols '()) '())
(check-expect (keep-symbols '(000 000)) '())
(check-expect (keep-symbols '(emmy ooma kayslee 89)) 
              '(emmy ooma kayslee))

; function:
(define keep-symbols 
  (lambda (listy)
    (cond
      ;;Base case: return empty list
      [(empty? listy) empty]
      ;;Recursive case 1: cons symbol onto recursive call
      [(symbol? (first listy)) 
       (cons (first listy) (keep-symbols (rest listy)))]
      ;;Recursive case 2: cons nothing onto recursive call
      [else
       (keep-symbols (rest listy))])))

; post-tests
(display "\n(keep-symbols '(a b 5 6 d))) ")
(keep-symbols '(a b 5 6 d))
(display "\n(keep-symbols '())) ")
(keep-symbols '())
(display "\n(keep-symbols '(emmy ooma kayslee))) ")
(keep-symbols '(emmy ooma kayslee 89))

;; ALTERNATE VERSION USES AN ACCUMULATOR IN AN INTERNAL 
;; HELPER FUNCTION:

; Contract: (keep-symbols-wr list-of-anything) -> list of symbols
; Header:   (define keep-symbols (lambda (listy) ... ))
; Purpose: create a list with only the symbols from listy

; Pre-function tests:
(check-expect (keep-symbols-wr '(a b 5 6 d)) '(a b d))
(check-expect (keep-symbols-wr '()) '())
(check-expect (keep-symbols-wr '(000 000)) '())
(check-expect (keep-symbols-wr '(emmy ooma kayslee 89)) 
              '(emmy ooma kayslee))
;; Function definition:
(define keep-symbols-wr 
  (lambda (listy)
    (local
      [(define k-s-helper 
         (lambda (listy acc)
           (cond
             ;; Base case 1: listy is empty, return acc
             [(empty? listy) acc]
             ;; Recursive case 1: first listy is a symbol
             [(symbol? (first listy))
              (k-s-helper (rest listy) 
                          (append acc (list (first listy))))]
             ;; Recursive case 2: first listy is not a symbol
             [else
              (k-s-helper (rest listy) acc)])))]
    (k-s-helper listy empty))))

; post-tests
(display "\n(keep-symbols-wr '(a b 5 6 d))) ")
(keep-symbols-wr '(a b 5 6 d))
(display "\n(keep-symbols-wr '())) ")
(keep-symbols-wr '())
(display "\n(keep-symbols-wr '(emmy ooma kayslee 89))) ")
(keep-symbols-wr '(emmy ooma kayslee 89))

;; ALTERNATE ALTERNATE VERSION USES FILTER 

; Contract: (keep-symbols-filter list-of-anything) -> list of symbols
; Header:   (define keep-symbols-filter (lambda (listy) ... ))
; Purpose: create a list with only the symbols from listy

; Pre-function tests:
(check-expect (keep-symbols-filter '(a b 5 6 d)) '(a b d))
(check-expect (keep-symbols-filter '()) '())
(check-expect (keep-symbols-filter '(000 000)) '())
(check-expect (keep-symbols-filter '(emmy 5 ooma kayslee 89)) 
              '(emmy ooma kayslee))

; Function definition:
(define keep-symbols-filter
  (lambda (listy)
    (filter symbol? listy)))

(display "\n(keep-symbols-filter '(a b 5 6 d))) ")
(keep-symbols-filter '(a b 5 6 d))
(display "\n(keep-symbols-filter '())) ")
(keep-symbols-filter '())
(display "\n(keep-symbols-filter '(emmy ooma kayslee 89))) ")
(keep-symbols-filter '(emmy ooma kayslee 89))


;  
; Problem 5:
; 
; (a) Write a function called NAME-TO-DIGIT that consumes a quoted    
;     symbol and, if the input symbol is the name of a digit ('zero
;     through 'nine, in lowercase letters), the corresponding digit 
;     is returned.  Otherwise, the input value is returned 
;     unchanged.
; 
;       > (name-to-digit 'zero)
;       0
; 
;       > (name-to-digit 'eighty-two)
;       eighty-two
; 
;       > (name-to-digit 'four)
;       4
;       
;       > (name-to-digit 'SIX)
;       SIX
;       
;       
; (b) Write a function called SUM-ALL that takes a list as its
;     input.  This function computes the sum of the values 
;     specified in the list, and your solution should use the
;     NAME-TO-DIGIT function from part (A).  The list given as
;     input can contain any valid Racket entities, but should
;     only sum the items that are either numbers or quoted
;     symbols representing digits as specified in part (A).
;     
;     > (sum-all '(1 2 3 4))
;     10
;     
;     > (sum-all (list 'three 'TWO 'six 9))
;     18
;     
;     > (sum-all (list "three" "two" 'seven))
;     7
;     
;     > (sum-all empty)
;     0
;   


; Contract: (name-to-digit symbol) -> quoted-symbol or number
; Header:   (define name-to-digit (lambda (sym) ... ))
; Purpose:  to convert quoted symbols that match digits to numbers

; NOTE: Only works for lowercase quoted symbols

; Pre-function tests:
(check-expect (name-to-digit 'zero) 0)
(check-expect (name-to-digit 'eighty-two) 'eighty-two)
(check-expect (name-to-digit 'four) 4)
(check-expect (name-to-digit 'SIX) 'SIX)
(check-expect (name-to-digit 'eight) 8)

; Function Definition:
(define name-to-digit 
  (lambda (sym)
    (cond
      [(symbol? sym)
       (cond
         [(symbol=? sym 'zero) 0]
         [(symbol=? sym 'one) 1]
         [(symbol=? sym 'two) 2]
         [(symbol=? sym 'three) 3]
         [(symbol=? sym 'four) 4]
         [(symbol=? sym 'five) 5]
         [(symbol=? sym 'six) 6]
         [(symbol=? sym 'seven) 7]
         [(symbol=? sym 'eight) 8]
         [(symbol=? sym 'nine) 9]
         [else sym])])))

; Post-function tests:
(display "\n(name-to-digit 'one) => ")
(name-to-digit 'one)
(display "\n(name-to-digit 'ONE) => ")
(name-to-digit 'ONE)
(display "\n(name-to-digit 'eight) => ")
(name-to-digit 'eight)

; Contract: (sum-all list-of-anything) -> number
; header:   (define sum-all (lambda (listy) ... ))
; purpose: produce sum of adding all numbers or numbers from name-to-digit

; pre-tests:
(check-expect (sum-all (list 'zero)) 0)
(check-expect (sum-all (list 'eighty-two)) 0)
(check-expect (sum-all (list 5 7 #t "hello" '() 'four)) 16)
(check-expect (sum-all (list -1 -3 9 'SIX 'six 'nine)) 20)

; Function definition:
(define sum-all
  (lambda (listy)
    (cond
      ;; Base case: return 0 since no numbers on listy
      [(empty? listy) 0]
      ;; Recursive case 1: first listy number so add it to sum
      [(number? (first listy)) 
       (+ (first listy) (sum-all (rest listy)))]
      ;; Recursive cases 2 & 3: first listy is symbol
      [(symbol? (first listy))
       (if (number? (name-to-digit (first listy)))
           ;; helper function returns a number so add it to sum
           (+ (name-to-digit (first listy)) (sum-all (rest listy)))
           ;; helper function does not return a number
           (sum-all (rest listy)))]
      ;; Recursive case 4: first listy is neither a number or a symbol 
      [else
       (sum-all (rest listy))])))

; post-tests:
(display "\n(sum-all '(one two buckle my shoe 4 6 4)) => ")
(sum-all '(one two buckle my shoe 4 6 4))
(display "\n(sum-all '()) => ")
(sum-all '())
(display "\n(sum-all '(\"hi there\" \"number\" 'eight)) => ")
(sum-all '("hi there" "number" eight))


; 
;  Problem 6:
;  
;  Write down the value of each of the following Racket 
;  expressions, assuming that each expression is evaluated after    
;  the definition of the constant FOOD-GROUPS, shown below. If 
;  the evaluation of an expression results in an error, give a 
;  brief description of the cause of the error:
;  
;  (define FOOD-GROUPS '(sugar fat coffee chocolate))
;  
;  a) (cons (first (rest FOOD-GROUPS)) 
;           (list (first (rest (rest FOOD-GROUPS)))))
; 
;     '(fat coffee)
; 
;  b) (first (rest (rest (rest FOOD-GROUPS))))
;     
;     'chocolate
; 
;  c) (first (rest (rest (rest (rest FOOD-GROUPS)))))
; 
;     ERROR tried to call first on an empty list
; 
;  d) (append (list (first (rest (rest FOOD-GROUPS)))) '(salt))
; 
;     '(coffee salt)
; 
;  e) (cons (first FOOD-GROUPS) (cons (first (rest FOOD-GROUPS))
;           (cons 'oreos (rest (rest FOOD-GROUPS)))))
;    
;     (list 'sugar 'fat 'oreos 'coffee 'chocolate)
; 
; 
;  f) (rest (first FOOD-GROUPS))
; 
;     ERROR rest expects a non-empty list. given 'sugar
;     (NEVER CALL REST ON FIRST UNLESS FIRST IS A LIST)
; 


;  
;  Problem 7:
; 
; (a) Write a string-reverse function using explicit recursion over the 
;     input string.
; 
;     Do not use any list functions in your solution.
;     
; (b) Write a string-reverse function that uses list functions to
;     reverse the input string.
; 
; 


; Contract: (string-reverse string) -> string
; Header:   (define string-reverse (lambda (str) ... ))
; Purpose:  Produce the characters in a string in reverse

; Pre-function tests:
(check-expect (string-reverse "muppet") "teppum")
(check-expect (string-reverse "murder") "redrum")
(check-expect (string-reverse "") "")

; Function definition:
(define string-reverse
  (lambda (str)
    (local
      ;; helper function will do recursion over the string
      ;; using the position in the string and an accumulator.
      ;; This helper takes advantage of the way string-appending
      ;; a letter to the acc creates a string in reverse.
      [(define help-rev
         (lambda (pos acc)
           (cond
             ;; base case: when pos is > length of str, return acc
             [(= pos (string-length str)) acc]
             ;; recursive case: tail-recursive
             [else
              (help-rev 
               (add1 pos) 
               ;; string-ref returns a character at the given pos.
               ;; character is converted to string by string function
               ;; and then appended on to the front of the string acc.
               (string-append (string (string-ref str pos)) acc))])))]
      ;; initial call to helper uses first position in string and an 
      ;; empty string for the initial value of the acc.
      (help-rev 0 ""))))

; Post-function printfs:
(printf "(string-reverse \"murder\") => ~a~%" (string-reverse "murder"))
(printf "(string-reverse \"barbie\") => ~a~%" (string-reverse "barbie"))
(printf "(string-reverse \"skipper\") => ~a~%" (string-reverse "skipper"))

; Contract: (string->list-reverse string) -> string
; Header:   (define string->list-reverse (lambda (str) ... ))
; Purpose:  Produce the characters in a string in reverse

; Pre-function tests:
(check-expect (string->list-reverse "muppet") "teppum")
(check-expect (string->list-reverse "murder") "redrum")
(check-expect (string->list-reverse "") "")

; Function definition:
(define string->list-reverse
  (lambda (str)
    (implode (reverse (explode str)))))

; Post-function printfs:
(printf "(string->list-reverse \"murder\") => ~a~%" (string->list-reverse "murder"))
(printf "(string->list-reverse \"barbie\") => ~a~%" (string->list-reverse "barbie"))
(printf "(string->list-reverse \"skipper\") => ~a~%" (string->list-reverse "skipper"))


(newline)