Lab 9 Finding Your Way

Purpose: The purpose of this lab is to practice working with mutually recursive data.

Textbook references: Chapter 19.1: Trees, Chapter 19.4 Designing with Intertwined Data, Chapter 20: Incremental Refinement

S-Expressions

Exercise 1 Design the function depth. The function consumes an SExpr and determines its depth. An Atom has a depth of 1. The depth of a list of SExprs is the maximum depth of its items plus 1. Be sure to use list abstractions where appropriate.

Exercise 2 Design the function substitute. It consumes an SExpr s and two Strings, old and new. The result is like s with all occurrences of old replaced by new.

Dig a Tunnel

Consider the following representation of these caverns and tunnels:

; A TunnelMaze is one of:

; - "you win!"

; - "you lose"

; - Cavern

(define-struct cave [north south east west])

; A Cavern is a (make-cave MaybeDoor MaybeDoor MaybeDoor MaybeDoor)

; representing a room with four possible trap doors (in the north, south, east, and west of the cavern)

; A MaybeDoor is one of:

; - false (representing the fact that there is no trapdoor here)

; - TunnelMaze (representing a trapdoor leading you down to more of the maze)

Note that once you go down through a trapdoor you cannot get back up again. We’ll figure out how to get out of these tunnels later. After we acquire some treasure.

Let’s design our game! The player will start in some cavern and can make their way through trap doors by pressing the arrow key in the direction of that door (so for example, pressing the "left" arrow key would allow you to jump through a trap door on the west side of the cavern). The game ends when the player reaches either a room full of treasure ("you win!") or a room with a deadly monster in it ("you lose").

Step 1: What stays the same?

Exercise 3 Define constants to represent the things that are not changing in the game.

Step 2: What changes?

Luckily, we already have a data definition to work with! What a crazy random happenstance.

Exercise 4 Create templates for the given data definitions. When designing with intertwined data, following the template is essential so that you don’t get lost.

Exercise 5 Create a few example TunnelMazes to work with.

Step 3: Which handlers do we need?

Exercise 6 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create.

Step 4: Design your handlers

Exercise 7 Design the handlers you decided on in the last step. Remember to follow all the steps of the function design recipe. These steps will help you ensure that your functions all work together the way you expect.

Step 5: Put it all together!

Exercise 8 Design a function that uses big-bang to create your program, inserting the functions you defined above into the appropriate clauses.

Stretch Goals - Improving the Game

Exercise 9 Update your program so that instead of taking in an initial TunnelMaze, it creates a random maze for the user to navigate. That way you don’t already know which trap doors to jump through. The adventure is so much more exciting!

Exercise 10 Update your random TunnelMaze generation to ensure that there are no dead ends (Caverns with no available trap doors).

Exercise 11 Update your TunnelMaze generation to ensure that there is at least one treasure room somewhere in the maze. We just don’t like certain death. It’s no fun at all.