Assignment 11: Traversing a Cave, Escaping a Prison

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks, and Grading Guidelines. Above all, keep your work neat and honest.

1. (7pts) In this problem, you will implement a simple maze navigation game. The maze is a collection of caves. Each cave has a name, and may contain one item, e.g., coins, a loaf of bread, a compass, president Gillis, etc. It also has a number of doors that connect the cave to other caves.

   Task 1: Define a structure for caves and give a concise data definition for caves.
   Develop the function create-cave, which creates a cave from a name and an item. A brand-new cave has no connections. We suggest you use icons (on Linux: /usr/share/icons, or look into /usr/X11R6 on other Unixes) or your own favorite pictures (gif, xmp) instead of plain symbols for the items.
   Define the function connect-caves, which accepts two caves, c1 and c2 and connects them.
   A cave labeled 'Exit serves as exits from the maze.
   Test your functions with a small sample cave.

   As the player walks through the maze, he can collect up to two items in his two pockets. When the player enters a cave, he may pick up or exchange items. Specifically, if one of the pockets is empty, the player can put the cave's item into his pocket. If both pockets are filled with items, the player may exchange the content of one of his pockets with the item in the cave. Once the player is happy with the state of things, he moves on by choosing one of the exits out of the cave. The game is over when the player reaches the exit of the maze.

   Task 2: Define the function create-player, which accepts a cave and creates a player. The latter is a function that controls three properties, i.e. the player's current location and the contents of the two pockets, and deals with a number of messages:

   #| --------------------------------------------------------------- 
      Players    
      create-player : cave -> object
   
      Purpose: object deals with the following messages: 
        where -- the name of the current location 
        what  -- the item stored in the current location 
        show-next-exit -- shows one exit at a time, i.e., shows list in
               cicular fashion
        go! -- switch current-location to last cave seen 
        left  -- show contents of left pocket
        right -- show contents of right pocket
        switch-left -- switch contents of left pocket and item in current cave
        switch-left -- switch contents of right pocket and item in current cave
   |#   
   

   Here is a sample dialogue, based on the above sample cave definition:
   
   

   
   
   

   End of Problem This problem is open-ended and flexible. The design of the dialogue is up to you. You are in control of how you output descriptions of items, caves, or connections, if you choose to do so. It may be a simple text-based dialogue as above. It is acceptable to implement the minimum described above, but don't feel constrained by this standard; if you implement more, tell us. Be creative!
   
   

2. (Extra Credit: 3pts) In the kingdom of Tuhundredtenia, the jail system is extensive, with 150 cells all in a row. Each cell contains one prisoner. Each cell's door has a key, which when turned toggles the door's lock. That is, if the door was unlocked, then turning the key locks it; if locked, then turning unlocks it.

   At the start of the evening, all cells are locked, but the Royal Jailer has a curious habit. Every evening, he turns the key in every door---numbers 1 through 150. Then, he goes back and turns the key in every other door---numbers 2, 4, 6, ..., 150. Then, he goes back and turns the key in every third door---numbers 3, 6, 9, ..., 150. Then, he turns the key in every fourth door---numbers 4, 8, 12, ..., 148. And so on, until he finihes by turning the key in every 150th door (just number 150). After that, he falls asleep, and anybody in an unlocked cell can escape during the night.

   You and your friends have been framed, and falsely convicted of Meandering with Intent to Jay-walk, and are scheduled to be executed at dawn. Fortunately, each of you can name which cell to be locked away in. Which cell numbers do you ask for?

   Develop a program that computes the indices of all open cells in the prison, assuming there are CELL# prison cells. Start with CELL# defined as 10; at the end switch to 150.

   Your program does not need to consist of a single function. Instead, it should simply end in an expression that computes the open prison cells, followed by one that prints them. The sequence starts with 1. Why?

   Hint:Use the following abstraction:

   ;; all : N (N -> boolean) (N -> void) -> void
   ;; Effect: the effect of action on j, such that 0 < j <= i and (predicate j)
   (define (all size predicate action)
     (cond
       ((= size CELL#) (void))
       (else (begin
   	    (if (predicate size) (action size) (void))
   	    (all (add1 size) predicate action)))))
   

   You can use the abstraction as follows to print the open cells:

   ;; print the state of the vector 
   (all 0 
        (lambda (i) (= (vector-ref cells i) UNLOCK)) 
        (lambda (i) (printf "open ~s ~n" (+ i 1))))
   

   assuming cells is the name of the vector of cells.