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)
  (or (= (car lyst) (cadr lyst)) (= (car lyst) (caddr lyst)) (= (cadr lyst) (caddr 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)