Labyrinth Escape

Where am I?

You are trapped in a labyrinth and your only hope of escape is to cast the magic spell that will free you from its walls. Scattered within the labyrinth are three magical items:

• The Spellbook (📕), which contains the script for the escape spell.
• The Potion (🧪), containing the arcane compounds that power the spell.
• The Wand (⚡️), which concentrates your focus to make the spell work. (Or is it actually Nick Parlante's legendary wand of dereferencing?)

Collecting all three magical items will allow to cast the spell to escape to safety.

A pointer labyrinth

This is, of course, no ordinary labyrinth. It’s a pointer labyrinth. It is a linked arrangement of MazeCells. The MazeCell struct is defined in the labyrinth.h file and reproduced here:

struct MazeCell {   
    string contents;   /* Value is either "", "Spellbook", "Potion", or "Wand" */
    MazeCell* north;   /* The cell to the north, or nullptr if no cell to the north. */
    MazeCell* south;   /* The cell to the south, or nullptr if no cell to the south. */
    MazeCell* east;    /* The cell to the east, or nullptr if no cell to the east. */
    MazeCell* west;    /* The cell to the west, or nullptr if no cell to the west. */
};

The diagram to the right is an example 4 × 4 labyrinth. The starting location is marked with a smiley face and the location of the three items with similarly cute emojis. The MazeCell containing the smiley face has north, south, east, and west pointers pointing to the MazeCell located one step in each of those directions. The MazeCell containing the book (📕) has north, east, and west pointers set to nullptr, and only its south pointer would point to another MazeCell (specifically, to the cell in the bottom-left corner).

Each MazeCell has a field named contents that indicates the item at that location. If the cell contains no item, its contents field is an empty string. A cell that holds the Spellbook, Potion, or Wand item would contain the string "Spellbook", "Potion", or "Wand", respectively.

Once dropped into this labyrinth at the starting location, you can roam around to find the items you need to cast the escape spell. There are many paths you can take; here are two of them:

• ESNWWNNEWSSESWWN
• SWWNSEENWNNEWSSEES

Each path is represented as a sequence of letters (N for north, W for west, etc.) that, when followed from left to right, trace out the steps. Starting from the smiley-face, the first path steps East, then South (collects Potion from this cell), then North, then West, and so on.

Trace the two paths above through the example labyrinth and confirm that you understand how each is a valid path that gathers all three magical items. Then, answer the following question:

Confirming a path to freedom

Write a function that steps through a path to determine if it is valid and will successfully collect all items in the needed set.

bool isPathToFreedom(MazeCell* start, string path, Set<string> needed)

The function arguments are a pointer to a MazeCell where to begin exploration, a string of characters 'N', 'S', 'E', and 'W' representing a path of steps, and a Set of items to collect (items are represented as strings). The function begins at the start cell, steps through the path, and collects items from each visited cell. The function returns true if path is valid and collected all needed items, false otherwise.

A path successfully escapes the labyrinth if:

1. Each step in the path is legal, i.e. valid direction to move from current cell to neighbor cell.
2. Every item in the needed set is collected along the path.

Function Specifications

• Your function should work for any start cell in any labyrinth, not just the example above. You may assume that the provided start pointer is not nullptr.
• Your function should work for any size Set of any items; not just exactly the three item set in the example.
• The function should operate by iterating over the characters in the path string and attempting to move the direction for each step.
  • If the next step attempts to move through a non-existent link (pointer in that direction is nullptr), such as trying to move East from the cell containing the wand in the example labyrinth, the function should stop and return false. Your function should not crash if the path attempts to traverse a link that does not exist.
  • If the next step is an invalid character (any character other than 'N', 'S', 'E', or 'W'), use the error() function to report the problem and exit.
• As you visit each cell, collect the item it contains.
  • If collecting this item is the last one you needed, success! Return true. Any remaining steps in path are ignored.
• It is allowable for a path to visit the same cell more than once.
• You should not allocate any new MazeCell objects. You can declare variables of type MazeCell* (pointers to existing MazeCell objects), but you should not use the new keyword.

Testing

Constructing test cases for labyrinth can be a bit of a chore given the complex setup. To help you out, we supply a comprehensive suite of provided tests.

• Our provided test cases construct a labyrinth from a custom string representation and call your isPathToFreedom on various valid and invalid paths.
• Review these provided test cases to understand what they test and how.
• If you pass all provided tests, you should be good to go. You are welcome to add student tests of your own, but it is not expected that you do so.

Escaping from your personal labyrinth

Now you are ready to find the escape path from your own personal labyrinth. We provide a function that builds a personalized labyrinth for you. By “personalized” we mean that “no one else in the course is going to have the exact same labyrinth as you.” Your job is to figure out a path through your labyrinth that collects all three magical items, allowing you to escape.

At the top of labyrinth.cpp are two constants marked with a "TODO" message. The first one, kYourName, is a spot for your name. Edit this constant so that it contains your name. You will fill in the second constant kPathForYourName with a path. A provided test case generates the personal labyrinth for kYourName and confirms that kPathForYourName is a valid path to escape it.

Debugging linked structures

To find that path, you will use your old friend the debugger! Set a breakpoint on the test case for your personal labyrinth escape. Run the program under the debugger. When stopped at the breakpoint, look to the Variables pane to see the state of the local variables. The parameter start is a pointer to the MazeCell inside your labyrinth. Click the dropdown triangle to view the contents field of start, as well as the four pointers leading to the cell's neighbors.

Depending on your labyrinth, your starting location may allow you to move in all four cardinal directions, or you may find that you can only move in some of them. A pointer in a direction you cannot move will be set to nullptr, which displays as 0x0 in the Variables pane. A pointer in a direction you can move will be set to a non-zero value and have dropdown arrow on the value in the Variables panel. Clicking the arrow will unfold to show the neighbor cell. You can navigate further by choosing one of its dropdown arrows, or you could back up to the starting cell and explore in other directions. It’s up to you!

Draw a lot of pictures. Grab a sheet of paper and map out your labyrinth. There is no guarantee where you start – you could be in the upper-left corner, dead center, etc. The items are scattered randomly, and you’ll need to seek them out. Once you’ve mapped it out, work out the steps in your escape path and assign those steps in string form to the constant kPathForYourName; then see if you pass the escape test. If so, fantastic! You’ve escaped! If not, you have lots of options. You could step through your isPathToFreedom function to see if one of the letters you entered isn’t what you intended and accidentally tries to move in an illegal direction. Or perhaps the issue is that you mis-drew the map of your personal labyrinth and you’ve ended up somewhere without all the items. You could alternatively set the breakpoint at the test case again and walk through things a second time, seeing whether the diagram of the labyrinth you drew was incorrect.

To summarize, here’s what you need to do:

1. Edit the constant kYourName to a string containing your full name. Don’t skip this step! If you forget to do this, you’ll be solving the wrong maze. Once you have set kYourName, do not change it, as this would cause a different maze to be generated than the one you have already solved.
2. Set a breakpoint at the escape test case and run under the debugger.
3. Use the debugger to explore the labyrinth links and draw out the labyrinth on a sheet of paper and find where the items are.
4. Find a path that collects all three items and edit the constant kPathForYourName with that path. Use the provided test case to confirm your path is a valid escape.

Advice

• A labyrinth can have loops or multiple distinct paths between different cells. Keep this in mind as you’re exploring or you might find yourself going in circles!
• You don’t necessarily need to map out the whole labyrinth. You only need to explore enough of it to find the three magical items and create a path to collect them all.
• In the example labyrinth above, every link that leads northward from cell A to B has a corresponding reverse south link from B back to the A (and the same for east/west links). This may not always be the case for all labyrinth configurations. It is possible for a labyrinth to have one-way links.

Concluding thoughts

At this point, you have a good command of how to use the debugger to examine linked structures. You know how to recognize a null pointer, how to manually follow links between objects, and how to reconstruct the shape of a linked data structure. We hope you find these skills useful as you continue to write code that works on linked lists and other linked structures!

From the wacky imagination of xkcd.