Week 11 Set b
Due Date Thursday 11/14 at 9:00pm (Week 11)
Purpose To design functions over graphs and to further your implementation of Pacman.
Graded Exercises
; A Graph is a (make-graph [List-of Symbol] [Symbol -> [List-of Symbol]]) (define-struct graph [nodes neighbors]) ; and represents the nodes and edges in a graph. ; All of the symbols in nodes are assumed to be unique, as are the symbols in ; any list returned by neighbors, and all of the symbols returned by neighbors ; are assumed to be in nodes.
More Graph Manipulation
You should again use the following testing pattern when testing some function f that outputs a graph. Check the docs for check-satisfied for more info.
; graph=?/curried : Graph -> [Graph -> Boolean] ; Curried graph=? (define graph=?/curried (λ (g1) (λ (g2) (graph=? g1 g2)))) ; f : Graph ... -> Graph ; Do something to g (define (f g ...) ...) (check-satisfied (f some-input-graph ...) (graph=?/curried some-expected-graph))
As before, when you create and manipulate graphs, always be sure to uphold the assumptions we made about graphs in our data definition.
Exercise 1 Design the function swap, which swaps a graph’s nodes with its edges.
More formally, if the n1th node points to the n2th node in the graph, the new graph should have a node of the form 'n1->n2. If nodes 'n1->n2 and 'n3->n4 exist in this new graph, then 'n1->n2 points to 'n3->n4 if and only if n2 equals n3. We use this index-based naming convention as a way to avoid any possible difficulty with potentially problematic initial node names, such as 'a->b.
For example, here is a graph and its swapped verison:
(make-graph '(a b c) (λ (n) (cond [(symbol=? n 'a) '(b c)] [(symbol=? n 'b) '(b)] [(symbol=? n 'c) '(a)]))) (make-graph '(0->1 0->2 1->1 2->0) (λ (n) (cond [(symbol=? n '0->1) '(1->1)] [(symbol=? n '0->2) '(2->0)] [(symbol=? n '1->1) '(1->1)] [(symbol=? n '2->0) '(0->1 0->2)]))) You will find the following function helpful. Note that this is the only place in the homework any function from racket/string is allowed to be used.
(require racket/string) ; node-name->numbers : Symbol -> (list Nat Nat) ; Convert a symbol of the form 'n1->n2 to (list n1 n2) (define (node-name->numbers s) (map string->number (string-split (symbol->string s) "->"))) (check-expect (node-name->numbers '0->3) '(0 3)) Hint: A function you’ve previously designed will likely be of help here.
Exercise 2 Design close?, which takes a graph, two nodes, and a natural number, and determines if the second node is within that many steps of the first node. Assume both nodes are in the graph.
Exercise 3 Design find-all-paths, which finds all possible paths between two given nodes in a graph. Assume both nodes are in the graph. Some examples are illustrated below:
(define G1 (make-graph '(A B C D E F G) (λ (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) '()])))) (find-all-paths G1 'C 'C) -> '((C)) ; src = dest (find-all-paths G1 'C 'G) -> '() ; no paths from 'C to 'G (find-all-paths G1 'A 'B) -> '((A B)) (find-all-paths G1 'E 'G) -> '((E F G) (E A B F G)) (find-all-paths G1 'B 'G) -> '((B E F G) (B F G)) (find-all-paths G1 'A 'G) -> '((A B E F G) (A B F G) (A E F G))
Graph Properties
Use check-satisfied to test the following functions, on graphs which both do and don’t have the properties they are checking. You will have to do some slightly clever manipulation to test on graphs that don’t have the property in question, but it shouldn’t require defining a new, named function.
Exercise 4 Design the function connected? which determines if every node in a graph can reach every other node in a graph. Hint: A function you’ve previously designed will likely be of help here.
Exercise 5 Design undirected? which determines if each edge in the graph has a matching edge going the opposite direction. Hint: A function you’ve previously designed will likely be of help here.
Extra Credit - Graph Equality: Structural
The following exercise is extra credit. Not completing it will have no negative impact on your grade.
Exercise 6 Design graph-shape=?, which determines if two graphs have the same shapes. Here, we do not care about the names of the nodes being the same. Hint: A function you’ve previously designed will likely be of help here.
Pacman Strikes Back
Poor Pacman; he has nothing but his wits to defend himself against these zany ghosts. Let’s give him a hand by finally making use of those power pellets.
Now, when Pacman eats a power pellet, all of the ghosts should become frightened. When a ghost becomes frightened, it should immediately reverse the direction it is headed in. So Pacman knows the ghost is frightened, the ghost should go blue with fright (or some other color that a ghost could not be in your game).
When Pacman collides with a frightened ghost, the ghost should teleport back to its initial position and become unfrightened. Ghosts should also become unfrightened after at most ten seconds. Pacman colliding with unfrightened ghosts should behave as it previously did.
Note For the following, you can make our lives easier by adding an "UPDATED" comment above functions, data definitions, and tests when you change your existing Pacman code and an "ADDED" comment for new parts.
Exercise 7 Incorporate the feedback you received on your last Pacman assignment; make the suggested improvements and fix any bugs that may still exist.
Exercise 8 Update your data definitions, examples, and tests to support this new behavior.
Exercise 9 Update the behavior of your on-tick handler to support this behavior. The result of a single tick should be as if the parts of the game take place in the following order:
Pacman and Ghosts move.
Pacman eats a Ghost or a Ghost eats Pacman.
Ghosts change their frightened state. Note that if Pacman dies, ghosts should no longer be frightened.
Pacman eats any pellet in the position he just entered—
if he survived step 2.