**Assignment 03: Debugging the Labyrinth**
You are trapped in a [labyrinth](https://en.wikipedia.org/wiki/Labyrinth), and your only hope to escape is to cast the magic spell needed to free you from its walls. To do so, you will need to explore the labyrinth and find three magical items:
1. The **Spellbook** (đź“–), which contains the spell you need to cast to escape.
2. The **Potion** (🍾), which contain the arcane compounds needed for the spell.
3. The **Wand** (🪄), which concentrates your focus to make the spell work.
Once you have all three items, you can cast the spell to escape to safety.
This assignment is based on "Linked List Labyrinth" by Keith Schwarz of Stanford University.
# Learning Goals
- Gain experience with `gdb` and Visual Studio Code Debugging.
- Learn more about pointers and memory locations in C.
- Learn how to understand (and fix) a C program using a debugger.
# Grading Walk-Throughs
This assignment will be graded as "Nailed It" / "Not Yet" by a TA. To pass ("Nailed It") the assignment, you must
1. Complete the assignment and submit your work to gradescope.
+ You should start this assignment in class on the day shown on the calendar.
+ *Complete the assignment as early as possible*.
1. Schedule a time to meet with a TA. You can meet with them after the submission deadline.
+ You must book a time to meet with a TA
+ Sign-up on the Google Sheet *with at least 36 hours of notice*.
+ Contact your TA on Slack after signing up.
+ All partners must meet with the TA. If you cannot all make it at the same time, then each of you needs to schedule a time to meet with the TAs.
1. Walk the TA through your solutions prior to the deadline.
+ Walk-throughs should take no more than 20 minutes.
+ You should be well prepared to walk a TA through your answers.
+ You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected---nobody is perfect.
+ You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through---this is best left to a mentor session.
1. The TA will then either
+ mark your assignment as "Nailed It" on gradescope, or
+ mark your assignment as "Not Yet" and inform you that you have some corrections to make.
1. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA.
+ You will ideally complete any needed revisions by the end of the day the following Monday.
If you have concerns about the grading walk-through, you can meet with me after you have first met with a TA.
# Overview
This is, of course, no ordinary maze. It’s a *pointer maze*. The maze consists of a collection of `MazeCell` objects, where `MazeCell` is defined here:
~~~c
struct MazeCell
{
enum Item item;
struct MazeCell *north;
struct MazeCell *south;
struct MazeCell *east;
struct MazeCell *west;
};
~~~
Here, `Item` is this enumerated type:
~~~c
enum Item
{
NOTHING,
SPELLBOOK,
POTION,
WAND
};
~~~
For example, below is a 4 by 4 labyrinth. We’ve marked your starting position with a smiley face and positions of the three items with similarly cute emojis. The `MazeCell` you begin at would have its north, south, east, and west pointers pointing at the `MazeCell` objects located one step in each of those directions from you.
On the other hand, the `MazeCell` containing the book would have its north, east, and west pointers set to `NULL`, and only its south pointer would point somewhere (specifically, to the cell in the bottom-left corner).
Each `MazeCell` has a variable named `item` indicated what item, if any, is in that cell. Empty cells will have `item` set to the `NOTHING`. The cells containing the Spellbook, Potion, or Wand will have those fields set to `SPELLBOOK`, `POTION`, or `WAND`, respectively.
If you were to find yourself in this labyrinth, you could walk around a bit to find the items you need to cast the escape spell. There are many paths you can take; here’s three of them:
- `ESNWWNNEWSSESWWN`
- `SWWNSEENWNNEWSSEES`
- `WNNEWSSESWWNSEENES`
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 directions you’d follow. For example, the first sequence represents going east, then south (getting the Potion), then north, then west, etc. Trace though those paths and make sure you see how they pick up all three items.
# Quick Startup
## Compiling and Debugging
The starter code contains:
- `Main.c`: the main file in which you will type your team names and paths
- `Labyrinth.c`: the file in which you will implement the path checker
- `Labyrinth.h`: a "header" file in which you'll find some types and declarations
- `MazeGenerator.cpp`: an implementation of maze generation algorithms
- `MazeGenerator.h`: a "header" file in which you'll find some types and declarations
You'll only need to edit code in `Main.c` (very minimally) and in `Labyrinth.c` (you'll implement one function). You might notice that the list above contains both C files and a C++ file. Getting these to work together requires a small amount of extra work. Follow these steps:
1. Compile the C++ file into an object file.
~~~bash
g++ -c -std=c++11 MazeGenerator.cpp
~~~
2. Tell Visual Studio Code to generate a debug configuration by clicking the "Debug C/C++ file" button at the top of the window when you have `Main.c` open. **This process will fail**.
3. Tell Visual Studio Code that it should use `g++` (instead of `gcc`) and compile with a few extra files when debugging. To do so, edit the newly generated `.vscode/tasks.json` file and update it with the following changes.
~~~json
"command": "/usr/bin/g++",
"args": [
"-fdiagnostics-color=always",
"-g",
"${file}",
"MazeGenerator.o",
"Labyrinth.c",
"-o",
"${fileDirname}/${fileBasenameNoExtension}"
],
~~~
To change a variable while the program is running, you can use type following command at the debug console.
~~~text
-exec set var VARIABLE_NAME = NEW_VALUE
~~~
Note: the `-exec` part is only necessary if you are using Visual Studio Code. You can find other commands in this handy [reference card](gdb-refcard.pdf).
# Check Paths to Freedom
Your first task is to write a function that, given a cell and a path, checks whether that path is legal and picks up all three items. Specifically, in the file `Labyrinth.c`, implement the function
~~~c
int isPathToFreedom(struct MazeCell *start, const char *moves);
~~~
This function takes as input your starting location and a string made purely from the characters `N`, `S`, `E`, and `W`, then returns whether that path lets you escape from the maze.
A path lets you escape the maze if
1. the path is legal, in the sense that it never takes a step that isn’t permitted in the current `MazeCell`, and
2. the path picks up the Spellbook, Wand, and Potion.
The order in which those items are picked up is irrelevant, and it’s okay if the path continues onward after picking all the items up.
You can assume that `startLocation` is not a null pointer (you do indeed begin somewhere valid) and that the input string does not contain any characters besides `N`, `S`, `E`, and `W`.
Some notes on this problem:
- Your code should work for a `MazeCell` from any possible maze, not just the one shown on the previous page.
- Although in the previous picture the maze was structured so that if there was a link from one cell to another going north there would always be a link from the second cell back to the first going south (and the same for east/west links), you should not assume this is the case in this function. Then again, chances are you wouldn’t need to assume this.
- A path might visit the same location multiple times, including possibly visiting locations with items in them multiple times.
- You shouldn’t need to allocate any new `MazeCell` objects in the course of implementing this function. Feel free to declare variables of type `MazeCell*`. After all, your job is to check a path in an existing maze, not to make a new maze.
- Speaking of a `MazeCell*`, to access members via a pointer, you need to use the arrow (`->`) operator. See the following:
~~~c
struct MazeCell *currentCell = start;
if (currentCell->item == WAND) {
// ...
}
~~~
- Feel free to implement this function either iteratively or recursively, whichever seems best to you. You don’t need to worry about stack overflows here; we’ll never run your code on anything large enough to run out of stack space.
- Your code should not modify the maze passed into the function. In particular, you should not change which items appear where or where the links point.
- An edge case you should handle: it is okay to find the three items and then continue to walk around the maze. However, if the path both (1) finds all three items and (2) tries making an illegal step, then your function should return false.
# Escape from Your Personal Labyrinth
Your next task is to escape from a labyrinth that’s specifically constructed for your team. The starter code will use your team name to build a personalized labyrinth. By "personalized," we mean "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 that labyrinth that picks up all the three items, allowing you to escape.
At the top of `Main.c` you’ll see three constants.
- `TeamName` is a spot for you to type your unique team name. Edit this constant so that it contains your names or some team name that you choose.
- `PathOutOfNormalMaze` is the solution you find to the normal maze. You won't know this until you step through your maze with the debugger.
- `PathOutOfTwistyMaze` is a solution you find to the twisty maze. You won't know this until you step through your maze with the debugger.
This first half of main generates a personalized labyrinth based on your `TeamName` and returns a pointer to one of the cells in that maze. It then checks whether the constant `PathOutOfNormalMaze` is a sequence that will let you escape from the maze. To start, `PathOutOfNormalMaze` is a TODO message, so it’s not going to let you escape from the labyrinth. You’ll need to edit this string with the escape sequence once you find it.
To come up with a path out of the labyrinth, use the debugger! Set a breakpoint at the indicated line in main. When you do, you should see local variables in the debugging pane, along with the contents of `startLocation`, which is the `MazeCell` where you've been dropped into the labyrinth. Clicking the dropdown triangle in the debugger window will let you read the contents of the `item` field of `startLocation` (it should be `NOTHING`), as well as the four pointers leading out of the cell.
Depending on your maze, you may find yourself in a position where you can move in all four cardinal directions, or you may find that some directions are dead-ends. The pointers in directions you can’t go are all equal to `NULL`, which will show up as memory address `0x0` in the debugger. Valid pointers will have dropdown arrows near them, and clicking an arrow will show you the `MazeCell`s reachable by moving in the corresponding direction. You can "navigate" the maze further by choosing one of those dropdown arrows, or you could back up to the starting maze cell and explore in other directions. It’s really up to you!
Some hints:
- Grab a sheet of paper and map out your maze.
- Keep in mind that you can start potentially anywhere in the maze.
- Items are scattered randomly.
- Once you've mapped out your maze, construct an escape sequence and stash it in the constant `PathOutOfNormalMaze`. You should then pass the first test.
# Escape from Your Personal Twisty Labyrinth
In the previous section, you escaped from a labyrinth that nicely obeyed the laws of geometry. The locations you visited formed a nice grid, any time you went north you could then go back south, etc. We’re now going to relax these constraints, and you’ll need to find your way out of trickier mazes that look like the one shown to the above.
`MazeCells` are no longer in a nice rectangular grid where directions of motion correspond to the natural cardinal directions. There’s a `MazeCell` here where moving north and then north again will take you back where you started. In one spot, if you move west, you have to move south to return to where you used to be. In that sense, the names "north," "south," "east," and "west" here no longer have any nice geometric meaning; they’re just the names of four possible exits from one `MazeCell` into another.
The one guarantee you do have is that if you move from one `MazeCell` to another, there will always be a direct link from the second cell back to the first. It just might be along a direction of travel that has no relation to any of the directions you’ve taken so far.
The second half of main contains code to generate a "twisty" labyrinth personalized with the `TeamName` constant. As before, you’ll need to find a sequence of steps that will let you collect the three items you need to escape.
In many regards, the way to complete this section is similar to the way to complete the previous one. Set a breakpoint in the indicated spot, and then use the debugger to explore the maze. Unlike the previous section, though, in this case you can’t rely on your intuition for what the geometry of the maze will look like. For example, suppose your starting location allows you to go north. You might find yourself in a cell where you can then move either east or west. One of those directions will take you back where you started, but how would you know which one?
This is where memory addresses come in. Internally, each object in C has an associated **memory address**. Memory addresses typically are written out in the form `@0x********`, where `********` is the address of the object. You can think of memory addresses as sort of being like an "ID number" for an object---each object has a unique address, with no two objects having the same address. When you pull up the debugger view of a maze cell, you should see the `MazeCell` memory address under the Value column.
For example, suppose that you’re in a maze and your starting location has address `0x7fffc8003740` (the actual number you see will vary), and you can move to the south (which ways you can go are personalized to you based on your name, so you may have some other direction to move). If you expand out the dropdown for the south pointer, you’ll find yourself at some other `MazeCell`. One of the links out of that cell takes you back where you’ve started, and it’ll be labeled `0x7fffc8003740`. Moving in that direction might not be productive---it just takes you back where you came from---so you’d probably want to explore other directions to search the maze.
It’s going to be hard to escape from your maze unless you **draw lots of pictures** to map out your surroundings. To trace out the maze that you’ll be exploring, we recommend diagramming it on a sheet of paper as follows. For each `MazeCell`,
- draw a circle labeled with the memory address, or, at least the last five characters of that memory address. (Usually, that’s sufficient to identify which object you’re looking at).
- As you explore, add arrows between those circles labeled with which direction those arrows correspond to. What you have should look like the picture above, except that each circle will be annotated with a memory address.
It’ll take some time and patience, but with not too much effort you should be able to scout out the full maze. Then, as before, find an escape sequence from the maze!
Some notes on this problem:
- Memory addresses are not guaranteed to be consistent across runs of the program. This means that if you map out your maze, stop the running program, and then start the program back up again, you are not guaranteed that the addresses of the `MazeCell`s in the maze will be the same. The shape of the maze is guaranteed to be the same, though. If you do close your program and then need to explore the maze again, you may need to relabel your circles as you go, but you won’t be drawing a different set of circles or changing where the arrows link.
- You are guaranteed that if you follow a link from one `MazeCell` to another, there will always be a link from that second `MazeCell` back to the first, though the particular directions of those links might be completely arbitrary. That is, you’ll never get "trapped" somewhere where you can move one direction but not back where you started.
- Attention to detail is key here---different `MazeCell` objects will always have different addresses, but those addresses might be really similar to one another. Make sure that as you’re drawing out your diagram of the maze, you don’t include duplicate copies of the same `MazeCell`.
- The maze you’re exploring might contain loops or cases where there are multiple distinct paths between different locations. Keep this in mind as you’re exploring or you might find yourself going in circles!
- Remember that you don’t necessarily need to map out the whole maze. You only need to explore enough of it to find the three items and form a path that picks all of them up.
# Submitting Your Assignment
You will submit your responses on gradescope. **Only one partner should submit.** The submitter will add the other partner through the gradescope interface.
- [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work)
- [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members)
- [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)