Assignment 11: Traversing a Cave (DRAFT)

###
Assignment 11: Traversing a Cave (DRAFT)

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. (5pts) 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., a bag of coins, a loaf of bread, a compass, a picture of president Gillis, etc. It also has a number of exits, each of which leads into a tunnel that connects to other caves or leads out of the maze altogether. All tunnels are one-way. If you want a two-way connection between two caves, use two one-way tunnels. In general, the connections between caves are arbitrary and may include tunnels from a cave to itself, several tunnels for connecting the same two rooms, etc. Task 1: Define the function create-cave, which creates caves from a name, and an item . Define the function connect-caves, which accepts two caves, c1 and c2, and a label lbl (symbol) and enters the pair (list lbl c2) as an exit into the exit list for cave c1. Finally, define the functions cave-name, cave-item, and cave-exits, which return the appropriate properties of a cave. Caves labeled 'Exit will serves as exits from the maze. You can test your functions with a small example cave. If you make extensive test cases and want to let other people use them, put a copy in your home directory and post to the newsgroup!

   As the player walks through the maze, she can collect two items. When the player enters a cave, she may pick up the item, if one of the pockets is empty or exchange one of the two items for the item in the cave. Once the player is happy with the state of the items, she moves on by choosing one of the exits out of the cave. The game is over when the player exits the maze.

   Task 2: Define the function create-player, which accepts a cave and creates a player who is in that cave and with nothing (empty) in their pockets. You will also need the functions player-left-pocket, player-right-pocket, and player-current-cave. Then define the function swap-items, which accepts a player, a cave (if you like), and one of the symbols `'left`, `'right`. It swaps the item (or `empty`) in the indicated pocket with the item in the cave. Swap-items has no (useful) return value.

   The walk is simulated with a simple generative recursive program. It prints a question and reads a typed response from the keyboard. The response is one of a pre-determined number of symbols: 'show-pockets, 'show-exits, 'swap-left, 'swap-right and 'leave. In the latter case, the program asks one more question which must be answered with a number. It then selects the exit from the current cave with this number and moves the player to this next cave.

   Task 3: Implement the dialogue. You may use the following functions:

   1. read, which takes no argument and returns the symbol it reads from the input (keyboard);
   2. printf, which takes a string and prints it to the current line in the evaluation window of DrScheme;
   3. newline, which takes no argument and ends the current line.
   For simplicity, you should implement each command as a one-symbol command.

   Here is a sample dialogue:

       You entered the cave LovettHall.  It contains water.
       What would you like to do next? swap-left
       You just put down shoes and picked up water.
       What would you like to do next? swap-right
       You just put down bread and picked up shoes.
       What would you like to do next? show-pockets
       You own water in the left and shoes in the right pocket.
       What would you like to do next? leave
       There are 5 exits. Which one would you like to take? 3
       ...

   (A better dialogue might list the names of the five exits.)
   The first line could be produced with

           (printf "You entered the cave ~s.  It contains ~s.~n" 'LovettHall 'water)

   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!

   ¹ While this skip-a-location approach isn't usually needed for vectors, the numeric properties of the jailer's walk make it convenient in this case. To think about: What is the extra space overhead incurred by this approach? Is it significant? [back]
2. (5pts) In the kingdom of Tuhundredtenia, the jail system is extensive, with 150 cells all in a row. 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.

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

   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?

   Hints:

   - The magic number 150 or 151 should not occur more than once in your code! If you need to re-use them, give the value a name. (For early testing, you may want to use a more manageable value, like 10, while writing the program.)
   - It's perfectly fine to use 151 vector locations (numbered zero through 150), and never happen to use the location numbered zero¹.
   - As ever, use auxiliary functions to accomplish well-defined subtasks.
   - Make sure you can call your function a second time, and still get a correct answer!
   - An output of 150 lines is not particularly helpful; you may want instead to output a list of door-numbers which are open, or something similarly concise.)
   To think about: Once your program tells you the answer, can you augment this with an explanation for the particular answer? (This is a nice illustration of the difference between knowing an answer, and understanding the answer.)

Matthias Felleisen | This page was generated on Sun Feb 21 23:37:16 CST 1999.