AP CS Programming Test #3

0. (0 points) NAME________________________________________ PERIOD_________


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))
((2-of-a-kind? result) ; Money is returned on a pair
(set! balance (- balance 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.


> (define x '(A (B C) D E))
> (apply-directives x '(d d d))      ; Returns the cdddr of x
> (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)

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

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