AP CS Programming Test #3

0. (0 points) NAME________________________________________ PERIOD_________

INSTRUCTIONS

• Put your name on the test. Failure to do so will result in a loss of one point. (Let's face it, if you don't know your name, you probably have bigger problems than this test.)
• This test is closed book. No friends, no computer, just you, your brain, your test, and your pencil.
• Where possible, SHOW YOUR WORK! I don’t know how to assign partial credit to the void.
• Don't panic. It's just a test.

1. (5 points) Here is a constructor for a slot machine class, the function 3-of-a-kind?, and a Diceboy(tm) slot machine:

```(define (make-slot-machine balance)
(define (roll)    (set! balance (+ balance 1))    (let ((result (list (+ 1 (random 6)) (+ 1 (random 6)) (+ 1 (random 6)))))      (cond ((3-of-a-kind? result)   ; Jackpot!  (Insofar as 20 coins is a jackpot...)             (set! balance (- balance 20))             20)            ((2-of-a-kind? result)   ; Money is returned on a pair             (set! balance (- balance 1))             1)            (else "Ha ha, you lose!"))))  ; In the end, the house always wins  (define (dispatch m)    (cond ((eq? m 'roll) (roll))          ((eq? m 'balance) balance)          (else (error "Bad message"))))  dispatch)

(define (3-of-a-kind? )  (and (= (car lyst) (cadr lyst)) (= (car lyst) (caddr lyst))))

; This procedure was intentionally omitted from the diagram due to
; space considerations
(define (2-of-a-kind? lyst)

(define diceboy (make-slot-machine 1000))   ; Give the slot machine 1000 coins for payouts```

Now suppose that (diceboy 'roll) is called and result is bound to '(5 5 5). Draw the changes that occur on the environment diagram, below.

2. (10 points in 3 parts) (Adam Schmidt) In this problem, you will be writing a function, set-cxr!, first by analyzing it in box-and-pointer diagrams, then writing a helper function, and finally writing set-cxr! itself.

The function set-cxr! takes a pair, a value, and a list of directives as its inputs. Directives are either 'a or 'd. The first element of the directives list determines whether set-car! or set-cdr! will be performed. The remaining directives indicate how cars and/or cdrs should be used to get to the pair that will have set-car! or set-cdr! applied.

Below is the definition of a list and the corresponding box and pointer diagram:

`> (define x '(A (B C) D E))`

2A. (2 points) Draw the box-and-pointer diagram that results from the following four lines of code:

```> (set-cxr! x 'Q '(a d d))     ; Set the car of (cddr x) to 'Q
> (set-cxr! x 'R '(a d a d))   ; Set the car of (cdadr x) to 'R
> (set-cxr! x 'S '(d d a d))   ; Set the cdr of (cdadr x) to 'S
```

2B. (5 points) The function apply-directives takes two inputs, a pair and a list of directives. It applies the list of directives to the pair and returns the result.

Examples:

```> (define x '(A (B C) D E))
> (apply-directives x '(d d d))      ; Returns the cdddr of x
(E)
> (apply-directives x '(d a))        ; Returns the cadr of x (processing of directives goes left to right)
(B C)
> (apply-directives (cddr x) '(a))   ; Returns the car of (cddr x)
D```

Write apply-directives.

```(define (apply-directives pair list)
(cond ((null? list) pair)
(else (let ((dir (if (eq? (car list) 'a) car cdr)))
(apply-directives (dir pair) (cdr list))))))
```
```(define (apply-directives pair list)
(cond ((null? list) pair)
(else (let ((dir (if (eq? (car list) 'a) car cdr)))
(apply-directives (dir pair) (cdr list))))))
```

2C. (3 points) Now write set-cxr! by filling in the blanks. (Yes, you must fill in the blanks. No whining.)

```(define (set-cxr! pair value list-of-directives)
(let ((mutate-pair! (if (eq? (car list-of-directives) 'a) set-car! set-cdr!)))
(mutate-pair! (apply-directives pair (cdr list-of-directives)) value)))```

3. (5 points) (A variant of a proposed problem by Drew Brownlee) Suppose we have an abstraction for queues with the following procedures written:

```(make-queue)         ; creates a new, empty queue
(insert-queue! e q)  ; put element e into q
(delete-queue! q)    ; deletes first element from q and returns that element
(peek q)             ; returns the first element in q; q is unchanged```

And a person constructor like so:

```(define (make-person name subject)
(let ((penalized #f))
(define (discriminate) (set! penalized #t))
(define (get-out-of-jail) (set! penalized #f))
(define (oktopay?) (or (not (eq? subject 'stats)) penalized))
(lambda (msg)
(cond ((eq? msg 'discriminate) discriminate)
((eq? msg 'get-out-of-jail) get-out-of-jail)
((eq? msg 'name) name)
((eq? msg 'oktopay?) oktopay?)))))```

For this problem, fill in the blanks so that the following code:

```(define (paycashier! shoppingQueue)

(let ((payer (peek shoppingQueue)))    ; who is in the front of the queue?

(cond (((payer 'oktopay?))      ; will we let them pay?
((payer 'get-out-of-jail))        ; stats teacher no longer penalized
(display (cons ((delete-queue! shoppingQueue) 'name) '(has paid)))
(newline))

(else   ; a stats teacher who needs to be penalized!

((payer 'discriminate))      ; penalize person for being a stats teacher
(display (cons (payer 'name) '(has gone to the back of the line)))
(newline)

; Actually put the stats teacher in the back of the queue

(insert-queue! (delete-queue! shoppingQueue) shoppingQueue)))))

(define deggeller (make-person 'deggeller 'calculus))
(define virmani (make-person 'habib 'stats))
(define congress (make-person 'congress 'stats))
(define bell (make-person 'bell 'compsci))

(define shoppingQueue (make-queue))
(insert-queue! bell shoppingQueue)
(insert-queue! virmani shoppingQueue)
(insert-queue! congress shoppingQueue)
(insert-queue! deggeller shoppingQueue)
(paycashier! shoppingQueue)
(paycashier! shoppingQueue)
(paycashier! shoppingQueue)
(paycashier! shoppingQueue)
(paycashier! shoppingQueue)
(paycashier! shoppingQueue)```

...producing the following output:

```(bell has paid)
(habib has gone to the back of the line)
(congress has gone to the back of the line)
(deggeller has paid)
(habib has paid)
(congress has paid)```