Final Honors HW Assignment

The goal of this problem set is to get practice with accumulator-style functions and graph problems, and to design distributed programs and evaluators.

REMINDER: Complete the TRACE survey for CS2500!

You should have received an email with information about how to access the TRACE survey. The survey will be available from Thursday, Nov 29 to Sunday, Dec 16, 11:55pm.

---

Accumulators

Design the following functions using an accumulator.

Exercise 1:

;; posn-sum : [Listof Posn] -> Posn
;; Compute a posn whose x coordinate is the sum of the x coordinates in ps
;; and whose y coordinates is the sum of the y coordinates in ps
(define (posn-sum ps) ...)

Exercise 2:

;; A Digit is a Number in the range [0-9]
;; digits->num : [Listof Digit] -> Number
;; Compute the number represented by the list of digits
(define (digits->num ds) ...)

;; Examples:
(digits->num (list 1 2 3))  -->  123
(digits->num empty) ---> 0

Exercise 3: Using the following data definition for a family tree, design the function below using an accumulator.

;; A FamilyTree is either:
;; - empty
;; - (make-node String FamilyTree FamilyTree)
(define-struct node (name mom dad))

;; second? : FamilyTree -> Boolean
;; Determine if any child has the same name as an ancestor of theirs.
(define (second? ft) ...)

---

Graphs

For this set of problems, use the following data definition for graphs.

;; A [Graph X] is:
;; (make-graph [Listof X] [X -> [Listof X]] [X X -> Boolean])
(define-struct graph (nodes neighbors node=?))

Exercise 4: Design the function find-paths.

;; find-paths : [Graph X] X X -> [Listof [Listof X]]
;; Find all of the paths in the graph from src to dest
(define (find-paths g src dest) ...)

Note that input graphs may contain cycles. Make sure that your code can handle cycles in the graph and doesn't loop forever. Below are some tests to clarify what we expect.

(define G1
  (make-graph '(A B C D E F G)
              (lambda (n)
                (cond [(symbol=? n 'A) '(B E)]
                      [(symbol=? n 'B) '(E F)]
                      [(symbol=? n 'C) '(D)]
                      [(symbol=? n 'D) '()]
                      [(symbol=? n 'E) '(C F A)]
                      [(symbol=? n 'F) '(D G)]
                      [(symbol=? n 'G) '()]))
              symbol=?))

(check-expect (find-paths G1 'C 'C) (list (list 'C))) ; src = dest
(check-expect (find-paths G1 'C 'G) empty) ; no paths from 'C to 'G
(check-expect (find-paths G1 'A 'B) 
              (list (list 'A 'B)))
(check-expect (find-paths G1 'E 'G)
              (list (list 'E 'F 'G) 
                    (list 'E 'A 'B 'F 'G)))
(check-expect (find-paths G1 'B 'G)
              (list (list 'B 'E 'F 'G) 
                    (list 'B 'F 'G)))
(check-expect (find-paths G1 'A 'G)
              (list (list 'A 'B 'E 'F 'G) 
                    (list 'A 'B 'F 'G) 
                    (list 'A 'E 'F 'G)))

Exercise 5: Design the function same-graph?

;; same-graph? : [Graph X] [Graph X] -> Boolean
;; Determine whether g1 and g2 have the same nodes,
;; and each node in g1 has the same neighbors as that node in g2.
;; Assume that both graphs have the same node equality function
;; and that this node equality function is symmetric.
(define (same-graph? g1 g2) ...)

;; Examples
(same-graph? (make-graph '() (lambda (x) '()) symbol=?)
             (make-graph '() (lambda (x) '()) symbol=?))
--> true

(same-graph? (make-graph '(a) (lambda (x) '()) symbol=?)
             (make-graph '() (lambda (x) '()) symbol=?))
--> false

(same-graph? (make-graph '(a) (lambda (x) '()) symbol=?)
             (make-graph '(a) (lambda (x) '()) symbol=?))
--> true

(same-graph? (make-graph '(b) (lambda (x) '()) symbol=?)
             (make-graph '(a) (lambda (x) '()) symbol=?))
--> false

(same-graph? (make-graph '(a b) (lambda (x) '()) symbol=?)
             (make-graph '(b a) (lambda (x) '()) symbol=?))
--> true

(same-graph? (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'a) '(b)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?)
             (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'b) '(a)] 
                             [(symbol=? x 'a) '()]))
                        symbol=?))
--> false
 
(same-graph? (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'a) '(a b)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?)
             (make-graph '(a b) 
                         (lambda (x)
                           (cond 
                             [(symbol=? x 'a) '(b a)] 
                             [(symbol=? x 'b) '()]))
                         symbol=?))
--> true

Exercise 6: Design the following function and use same-graph? to test it.

;; reverse-edge-graph : [Graph X] -> [Graph X]
;; Build a graph with the same nodes as g, but with reversed edges.
;; That is, if g has an edge from a to b then the result graph will 
;; have an edge from b to a.
(define (reverse-edge-graph g) ...)

Exercise 7: Design the following function.

;; undirected? : [Graph X] -> Boolean
;; Determine if each edge in g has a matching edge going the opposite direction
(define (undirected? g) ...)

---

RacketBot — Racket as a Chat User

Using the chat program you developed in lab and the evaluator we developed in class, write RacketBot: a program that poses as a chat user. When RacketBot is sent a message that is an expression, it should evaluate it and reply with its result.

You must first implement exercise 11 from lab, which adds private messages. When RacketBot receives a private message addressed to it, it should try to read the message as an s-expression and evaluate it. If the s-expression is a valid program, it responds with a private message to the original sender with the result of evaluation. If the message is not a valid program, RacketBot should respond that it did not understand.

The string->sexp function will come in handy, which given a string produces the corresponding s-expression, if there is one, and false otherwise. To add this function, save the string-to-sexp.rkt file to your homework directory and include (require "string-to-sexp.rkt") at the top of your program.

As an extra bonus worth no points: can you think of a message that you could send RacketBot that would make it totally unresponsive so that it never responds to your message, or anybody elses? Note that RacketBot, if designed properly, should never crash; but that doesn't mean it can't become very, very busy.

Chat Server for Testing RacketBot

Here is the advanced server that the TAs ran in lab. It supports all of the messages described in Exercises 4 through 7 and Exercise 11 on Lab 10h.

For those of you who would like to understand the chat server code or would like to know how to develop/extend your own chat server, see this page. It provides information on how to write a chat server and code that implements a simple server that you can modify. Note that the simple chat server can only interact with clients that send Messages as Strings.