#lang racket

(require csc151)
(require rackunit)
(require racket/undefined)

;; CSC-151 (Fall 2021)
;; Lab: Vectors 
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

; +---------------+--------------------------------------------------
; | Provided code |
; +---------------+

;;; Procedure:
;;;   random-elt
;;; Parameters:
;;;   lst, a non-empty list 
;;; Purpose:
;;;   Unpredictably pick an element of lst.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * val is an element of lst.
;;;   * If lst contains more than one element, it is difficult to predict 
;;;     which element val is.
(define random-elt
  (lambda (lst)
    (list-ref lst (random (length lst)))))

;;; Procedure:
;;;   random-vector-elt
;;; Parameters:
;;;   vec, a non-empty vector
;;; Purpose:
;;;   Unpredictably pick an element of vec.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * val is an element of vec.
;;;   * If vec contains more than one element, it is difficult to predict
;;;     which element val is.
(define random-vector-elt
  (lambda (vec)
    (vector-ref vec (random (vector-length vec)))))

;;; (random-nums len max) -> listof integer?
;;;    len : non-negative-integer?
;;;    max : positive-integer?
;;; Make a list of length `len`, containing unpredictable numbers
;;; from the range [0..max).
(define random-nums
  (lambda (len max)
    (letrec ([helper
              (lambda (len so-far)
                (if (zero? len)
                    so-far
                    (helper (- len 1) (cons (random max) so-far))))])
      (helper len '()))))

;;; (ref-experiment collection rounds) -> void?
;;;   collection : (vectorof integer?) or (listof integer?)
;;;   rounds : natural?
;;;
;;; Look for integers selected randomly from the range between 
;;; 0 and the length of collection.  
;;;
;;; Returns nothing.  Used mostly for timing purposes.
(define ref-experiment
  (lambda (collection rounds)
    (let* ([ref (if (vector? collection) 
                    vector-ref 
                    list-ref)]
           [len (if (vector? collection) 
                    (vector-length collection)
                    (length collection))])
      (letrec ([kernel
                 (lambda (n)
                   (when (> n 0)
                     (ref collection (random len))
                     (kernel (- n 1))))])
        (kernel rounds)))))

;;; Value:
;;;   word-list
;;; Type:
;;;   list of strings
;;; Contents:
;;;   A sample list of strings, taken from one of the Project Gutenberg
;;;   collection.
;;; N.B., the file is our old friend, Jane Eyre, from Gutenberg:
;;;   https://www.gutenberg.org/cache/epub/1260/pg1260.txt
(define word-list
  (file->words "pg1260.txt"))

;;; Value:
;;;   word-vector
;;; Type:
;;;   vector of strings
;;; Contents:
;;;   A sample vector of strings, taken from one of the Project Gutenberg
;;;   collection.
(define word-vector
  (list->vector word-list))

;;; Procedure:
;;;   random-word
;;; Parameters:
;;;   words, a list or vector of strings
;;; Purpose:
;;;   Randomly select one element from words
;;; Produces:
;;;   word, a string
;;; Preconditions:
;;;   words is not empty
;;; Postconditions:
;;;   * word is an element of words.
;;;   * If words contains more than one element, word is difficult to
;;;     predict
(define random-word
  (lambda (words)
    (if (vector? words)
        (random-vector-elt words)
        (random-elt words))))
    
;;; Procedure:
;;;   random-words
;;; Parameters:
;;;   words, a list or vector of strings
;;;   n, a non-negative integer
;;; Purpose:
;;;   Randomly select n words from words.
;;; Produces:
;;;   some-words, a list of strings
;;; Preconditions:
;;;   words is not empty
;;; Postconditions:
;;;   * All elements of some-words appear in words.
;;;   * (length some-words) = n
;;;   * The elements and order of some-words is difficult to predict.
(define random-words
  (lambda (words n)
    (if (zero? n)
        null
        (cons (random-word words)
              (random-words words (- n 1))))))

;;; Procedure:
;;;   number-vector-increment-at!
;;; Parameters:
;;;   vec, a vector
;;;   index, an integer
;;; Purpose:
;;;   Increment the value at a vector position
;;; Produces:
;;;   [Nothing; called for side effect.]
;;; Preconditions:
;;;   (vector-ref vec index) is a number
;;; Postconditions:
;;;   Let val be (vector-ref vec index) before the procedure call. After the
;;    call (vector-ref vec index) produces val+1.
(define number-vector-increment-at!
  (lambda (vec index)
    (vector-set! vec 
                 index 
                 (+ 1 (vector-ref vec index)))))

#| AB |#

; +-------------------------+----------------------------------------
; | Exercise 0: Preparation |
; +-------------------------+

#|
a. If you have not done so, please conduct the normal "start of class
algorithm".  Introduce yourself to your partner.  Discuss work habits,
strengths, and areas to improve.  

b. Review the documentation for the supplied procedures to
ensure you understand what they are suposed to do.  If you're
not sure, feel free to experiment or to ask the staff.
|#

#| A |#

; +-------------------------------+----------------------------------
; | Exercise 1: Modifying vectors |
; +-------------------------------+

#|
Suppose we are considering two names for the same vector and want to
try to change the first element. Consider the following code. (That is,
*read it, don't enter it*.)

    > (define chinchilla (vector "a" "b" "c" "d"))
    > (define dingo chinchilla)
    > (define emu (vector-copy chinchilla))
    > (vector-set! chinchilla 0 "Z")

a. What do you expect the output of the following commands to be? (That
is, think about the answers and type the results; don't type the commands
in the Interactions pane.)

    > (vector-ref chinchilla 0)
    _____
    > (vector-ref dingo 0)
    _____
    > (vector-ref emu 0)
    _____
|#

#|
b. Check your answer experimentally. That is, type the commands in
the interactions pane now.  Then enter your answers.

    > (vector-ref chinchilla 0)
    _____
    > (vector-ref dingo 0)
    _____
    > (vector-ref emu 0)
    _____
|#

#|
c. What do you expect the results of the following to be?

    > (let* ([gibbon (vector "a" "b" "c" "d")]
             [hippo gibbon]
             [ibex (vector-copy gibbon)])
        (vector-set! gibbon 0 "Z")
        (list gibbon hippo ibex))

    <TODO: Enter expected output.>
|#

#|
d. Check your answer experimentally.

<TODO: Enter actual output>
|#

#|
e. What do your results of these experiments suggest about vectors in Scheme?

<TODO: Enter your notes.>
|#

; +---------------------------------------+--------------------------
; | Exercise 2: Selecting random elements |
; +---------------------------------------+

#|
a. Explain the difference between `random-elt`, `random-vector-elt`, 
and `random-word`.

<TODO: Enter your explanation.>
|#

#|
b. Using `random-words` and `word-list`, make a list of ten randomly
selected words.

<TODO: Enter your code and the output, copied from the interactions pane.>
|#

#|
c. Using `random-words` and `word-vector`, make a list of ten randomly
selected words.

<TODO: Enter your code and the output, copied from the interactions pane.>
|#

#| B |#

; +-------------------------------+----------------------------------
; | Exercise 3: Vector efficiency |
; +-------------------------------+

#|
We've claimed that vectors are much faster than lists.  Let's
conduct an experiment to see how much of a difference we see.

Here's a quick experiment that might give us a sense as to how
well `list-ref` works on a long list.

    (define size 10000)
    (define rounds 50000)
    (define list-of-values (range size))
    (define list-of-probes (random-nums rounds size))
    (define list-result 
      (time (map (section list-ref list-of-values <>) list-of-probes)))
|#

#|
a. Explain what it happening in this experiment.

<TODO: ENTER EXPLANATION>
|#

#|
b. Find values for `size` and `rounds` that make the computation
of `list-result` take around half a second (500 milliseconds). 

<TODO: ENTER NUMBERS AND RESULT TIME>
|#

#|
c. What do you expect to happen to the time for the computation of
`list-result` if we double the number of rounds (`rounds`)?  What
if we triple it?  

Check your answer experimentally and update as appropriate.  Make
sure to start with the values from b.

<TODO: ENTER YOUR EXPERIMENTS HERE, WITH NOTES AS TO SIZE>

<TODO: ENTER YOUR FINAL ANSWER HERE>
|#

#|
d. What do you expect to happen to the time for the computation if
we double the list size (`size`)?  What if we triple it?

Check your answer experimentally and update as appropriate.  Make
sure to start with the values from b.

Check your answer experimentally and update as appropriate.

<TODO: ENTER YOUR EXPERIMENTS HERE, WITH NOTES AS TO SIZE>

<TODO: ENTER YOUR FINAL ANSWER HERE>
|#

#|
e. Here's a followup experiment for vectors.

    (define vector-of-values (list->vector list-of-values))
    (define vector-result 
      (time (map (section vector-ref vector-of-values <>) list-of-probes)))

Will `vector-result` be the same as `list-result`?  Why or why not?

<ENTER YOUR ANSWER HERE>
|#

#|
f. Without changing `size`, find a value of `rounds` that makes
the computation of `vector-result` take about 50 milliseconds.  **Make
sure that you do not recompute list-result**.  
|#

#|
g. What do you expect to happen to the time for the computation of
`vector-result` if we double the number of rounds (`rounds`)?  What
if we triple it?

Check your answer experimentally and update as appropriate.

<TODO: ENTER YOUR EXPERIMENTS HERE, WITH NOTES AS TO SIZE>

<TODO: ENTER YOUR FINAL ANSWER HERE>
|#

#|
h. What do you expect to happen to the time for the computation if
we double the vector size (given by `size`)?  What if we triple
it?

Check your answer experimentally and update as appropriate.

<TODO: ENTER YOUR EXPERIMENTS HERE, WITH NOTES AS TO SIZE>

<TODO: ENTER YOUR FINAL ANSWER HERE>
|#

#|
i. What have you taken from these experiments?

<TODO: ENTER AN ANSWER HERE>
|#

#| A |#

; +------------------------------+-----------------------------------
; | Exercise 4: Tallying letters |
; +------------------------------+

#|
a. Fill in the missing parts of the documentation for the following
procedure.
|#

;;; (lowercase->number letter) -> ___
;;;   letter : char? (#\a through #\z)
;;; ____
(define lowercase->number
  (let ([a-num (char->integer #\a)])
    (lambda (letter)
      (- (char->integer letter) a-num))))

#|
b. Using `lowercase->number` and `number-vector-increment-at!`, write
a procedure, `(record-letter! tallies letter)`, that takes as input a
vector of integers (representing tallies of the 26 letters) and a letter,
and updates the appropriate entry in the tallies.

    > (define tallies (make-vector 26 0))
    > tallies
    '#(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
    > (record-letter! tallies #\c)
    > (record-letter! tallies #\z)
    > (record-letter! tallies #\c)
    > tallies
    '#(0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
|#

;;; (record-letter! tallies letter) -> void?
;;;   tallies : vectorof integer? (length 26)
;;;   letter : char? (#\a through #\z)
;;; Add to the tally for the given letter.
(define record-letter!
  (lambda (tallies letter)
    undefined))

#|
c. Finish the following definition of `tally-letters-in-string`, which
takes as input a string and returns a vector that tallies the letters
of the string.
|#

;;; (tally-letters-in-string str) -> vectorof integer?
;;;   str : string?
;;; Count how many time each lowercase letter appears in str.
(define tally-letters-in-string
  (lambda (str)
    (let ([tallies (make-vector 26 0)])
      (tally-letters-in-string/kernel str 
                                      tallies
                                      (- (string-length str) 1))
      tallies)))

;;; (tally-letters-in-string/kernel str tallies pos) -> (void)
;;;   str : string?
;;;   tallies : vectorof integer? (length 26)
;;;   pos : non-negative integer?
;;; Tallies the letters in str from 0 to pos (inclusive)
(define tally-letters-in-string/kernel
  (lambda (str tallies pos)
    (when (>= pos 0)
      (let ([ch (string-ref str pos)])
        (when (char<=? #\a ch #\z)
          undefined
          undefined)))))

; +-----------------------------+------------------------------------
; | Exercise 5: Summing vectors |
; +-----------------------------+

#|
Write a recursive procedure, `(vector-sum numbers)`, that takes one
argument, a vector of numbers, and returns the sum of the elements
of that vector.

You can use the recursion pattern(s) and `number-vector-largest`
from the reading as starting points. If you do, be sure to cite
your sources appropriately.

You may not convert your vector into a list.

Note: In case you hadn't noticed it yet, vector recursion is usually
a form of numeric recursion, where you are use the index in the
vector as the value you recurse over.
|#

(define vector-sum
  (lambda (nums)
    undefined))

#| B |#

; +-----------------------------+------------------------------------
; | Exercise 6: Filling vectors |
; +-----------------------------+

#|
Write a recursive procedure, `(my-vector-fill! vec val)`, that takes
two parameters, a mutable vector and a value, and puts that value
in every position of the vector.

> (define vec (vector 'a 'b 'c))
> vec
'#(a b c)
> (my-vector-fill! vec 0)
> vec
'#(0 0 0)
> (my-vector-fill! vec 'a)
> vec
'#(a a a)

Some implementations of Scheme come with vector-fill!. You may not
use that procedure.

Note: `my-vector-fill!` is supposed to modify an existing vector. It
is pointless to create a new vector.

Note: You may find that you want to do two things for a particular
position: fill the value at that position and recur. Remember that
when you want to sequence multiple actions if a test succeeds, you
should use a cond or when rather than an if.
|#

(define my-vector-fill!
  (lambda (vec val)
    undefined))

; +----------------------------------+-------------------------------
; | Exercise 7: Searching in vectors |
; +----------------------------------+

#|
Write a recursive procedure, `(vector-index-of vec elt)`, that looks
for `elt` in vector and returns the index of the first appearance
of `elt` if it appears in the vector and #f otherwise.

> (vector-index-of (vector 'a 'b 'c) 'b)
1
> (vector-index-of (vector 'a 'b 'c 'c 'b 'c) 'c)
2
> (vector-index-of (vector 'a 'b 'c) 'd)
#f
|#

(define vector-index-of
  (lambda (vec elt)
    undefined))

#| AB |#

; +---------------------------+--------------------------------------
; | For those with extra time |
; +---------------------------+

#|
If you find that you have time left at the end of lab, consider
doing one or more of the following problems.
|#

; +---------------------------+--------------------------------------
; | Extra 1: Rotating vectors |
; +---------------------------+

#|
Write a procedure, `(vector-rotate-l! vec)` that shifts the elements
in `vec` left by one position, moving the first element to the end.
That is, `vector-rotate-l!` puts the initial element of `vec` at the end,
the element at position 1 in position 0, the element at position 2
in position 1, and so on and so forth.
|#

(define vector-rotate-l!
  (lambda (vec)
    undefined))

; +----------------------------+-------------------------------------
; | Extra 2: Reversing vectors |
; +----------------------------+

#|
a. Write a procedure, `(vector-reverse vec)`, that creates a new
vector whose elements appear in the reverse order of the elements
in *`vec`*.
|#

(define vector-reverse
  (lambda (vec)
    undefined))

#|
b. Write a procedure, `(vector-reverse! vec`), that reverses *`vec`*
“in place”. That is, instead of producing a new vector, it rearranges
the elements within *`vec`*.
|#

(define vector-reverse!
  (lambda (vec)
    undefined))

; +--------------------------------------+---------------------------
; | Extra 3: Rotating vectors, revisited |
; +--------------------------------------+

#|
Write a procedure, `(vector-rotate! vec amt)`, that rotates
the values in `vec` by `amt` positions. That is, the first `amt`
values in `vec` move to the end, the value in position `amt` moves
to position 0, the value in position `amt`+1 moves to position 1,
and so on and so forth.
|#

(define vector-rotate!
  (lambda (vec amt)
    undefined))

; +--------------------------------+---------------------------------
; | Extra 4: Patterns of recursion |
; +--------------------------------+

#|
In a number of previous exercises, you wrote procedures that iterated over
the vector, changing values as you went. (For example, `vector-fill!`
had this form.) Summarize the form of a procedure that recurs over
vectors, setting the value at each position to a new value, much like
the recursion patterns given in the reading.
|#