#lang racket

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

;; CSC-151-01 (Spring 2021, Term 1)
;; Lab: NAME (Side A)
;;   https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT1/labs/pairs-and-vectors
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

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

;;; (count-cons-cells tree) -> integer?
;;;   tree : tree?
;;; Counts the number of cons cells that appear in tree.
;;; Does not look into vectors.
(define count-cons-cells
  (lambda (tree)
    (if (pair? tree)
        (+ 1
           (count-cons-cells (car tree))
           (count-cons-cells (cdr tree)))
        0)))

;;; (tree->code pair-struct) -> list?
;;;   tree : tree?
;;; Converts a tree into an approximation of the Scheme expression 
;;; that builds the tree.
(define tree->code
  (lambda (tree)
    (cond
      [(null? tree)
       'null]
      [(pair? tree)
       (list 'cons (tree->code (car tree)) (tree->code (cdr tree)))]
      [else
       tree])))

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

#| 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.  Make your 4:30 plans.

b. Review the documentation for the two 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.
|#

; +--------------------------------------+---------------------------
; | Exercise 1: Box and pointer diagrams |
; +--------------------------------------+

#|
a. Draw own box-and-pointer diagrams (on paper) for the following
expressions.  Each student should draw their own diagrams.

i. '(("x") "y" "z")
ii. '("x" ("y" "z"))
iii. '(("a") "b" ("c" ()))

b. Compare your answers to reach consensus.

c. Count the number of cons cells (pairs) in each.

d. Using `count-cons-cells`, determine how many cons cells (pairs) are
in each.  If the numbers differ, use `tree->code` to explore the code
used to build each.

There is nothing to submit for this problem, but make sure you 
understand the results.

Feel free to ask the lab staff to review your results.
|#

; +-----------------------------+------------------------------------
; | Exercise 2: Are they lists? |
; +-----------------------------+

#|
What do you think that `pair?` will return for each of the following?
How about `list?`. Attempt to confirm each answer experimentally and
explain any that you found particularly tricky.

i. (cons 'a 'b)
ii. (cons 'a (cons 'b 'c))
iii. (cons 'a null)
iv. null
v. (list 'a 'b 'c)
vi. (list 'a)
vii. (list)

There is nothing to submit for this problem, but make sure that you
can answer these questions.
|#

#| A |#

; +-------------------------------+----------------------------------
; | 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 list-size 100000)
> (define rounds 100)
> (define list-of-values (range list-size))
> (define list-of-probes (random-nums rounds list-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 `list-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 (`list-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 `list-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**.  (On my computer, it
required about 200000 rounds.)
|#

#|
g. 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.

<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 `list-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>
|#

; +-----------------------------+------------------------------------
; | Exercise 4: 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 as
a starting point. 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 using the index in the
vector as the value you recurse over.
|#

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

#| B |#

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

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

#| AB |#

; +----------------------------+-------------------------------------
; | Extra 1 : Trees to Strings |
; +----------------------------+

#|
a. Write a recursive procedure, `(intlist->string ints)`, that takes
as input a list of integers and returns a string that represents
the list.

> (intlist->string null)
"()"
> (intlist->string '(1))
"(1)"
> (intlist->string '(1 2 3))
"(1 2 3)"
> (intlist->string (cons 1 2))
BOOM!
|#

;;; (intlist->string ints) -> string
;;;   ints : a list of integers
;;; Convert a list of integers to a string.
(define intlist->string
  (lambda (ints)
    undefined))

#|
b. Write a similar procedure that accepts a pair of integers as the
last cons cell in the list.  (In a normal list, the last cons cell
has an integer and a null.)  When you reach the end of a list and
the `cdr` is not null, you should print a period and the cdr.

> (intseq->string null)
"()"
> (intseq->string (cons 1 2))
"(1 . 2)"
> (intseq->string (cons 1 (cons 2 3)))
"(1 2 . 3)"
|#

(define intseq->string
  (lambda (ints)
    undefined))

#|
c. Extend your procedure to handle nested pair structure.

> (intpairs->string null)
"()"
> (intpairs->string (list (list 1)))
"((1))"
> (intpairs->string (list 1 (list 2 3) 4))
"(1 (2 3) 4)"
> (intpairs->string (list 1 (cons 2 3) 4))
"(1 (2 . 3) 4)"
|#

(define intpairs->string
  (lambda (ints)
    undefined))