In this assignment you will attempt to find out your way out of a linked list labyrinth,
armed only with your wits and a debugger. Good Luck!
IMPORTANT: For this assignment you will be working by yourself.
Before you start coding, make sure you read through this whole document. If any of the
instructions aren’t clear, feel free to ask about it on CampusWire (use the PSA4 category).
Pre‐requisites
• Textbook1 Chapter 5
• Lab Sessions 08 (Debugging with VS Code)
Learning Objectives
Upon successful completion of this PSA you will be able to do the following.
• Use a debugger to examine the contents of memory
• Write Python code that uses the assert statement to check preconditions.
• Write Python code that raises an exception.
Initial Setup
Both you and your partner will need to get the starter code for your group using Git.
1. In VS Code, open the command palette and select the “Git Clone” option.
2. When prompted for the repository URL, enter the following, with X replaced by your
group number (e.g. 7 or 12).
ssh://git@code.sandiego.edu/comp120‐sp23‐s03‐psa4‐groupX
3. When prompted for where to save the repository, select the “comp120” folder you
created earlier this semester. If you happen to get an error, make sure you click the
“Git Log” button when prompted and look for the reported error message. Look at
CampusWire to see if anyone else got the same error message: if not, create a new
post, copying and pasting the output of the Git log.
4. Choose the “Open Repository” option in the window that pops up in the lower‐right
corner of the screen. In this repository you will find several Python files (*.py) and
several text files in a directory named data_files.
Note that when working on the PSA, you should be careful to only work on one computer at
a time (either you or your partner’s). If you want to switch between computers, make sure
you “Sync” your code.
IMPORTANT: As you complete and sync each problem, you can check the SAFE webapp for
the results of some limited testing. Note that the messages you receive from the tests run
are purposely vague: you should be relying on your own tests (as specified throughout
this assignment) to get the diagnostic feedback that you need to solve your problems.
Think of SAFE as a minimum backup to make sure that the very basics are working.
Computational Problem: Linked List Labyrinth
You have been trapped in a labyrinth, and your only hope to escape is to cast the magic
spell that will free you from its walls. To do so, you will need to explore the labyrinth to find
three magical items:
• The Spellbook (????), which contains the spell you need to cast to escape.
• The Potion (⚗), containing the arcane compounds that power the spell.
• 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 is, of course, no ordinary maze. It’s a reference maze. The maze consists of a collection
of objects of type MazeCell, where MazeCell is defined here:
class MazeCell:
whatsHere: Item # Item present, if any.
north: Optional[‘MazeCell’] # The cell north of us (if one exists)
south: Optional[‘MazeCell’]
east: Optional[‘MazeCell’]
west: Optional[‘MazeCell’]
Here, Item is this enumerated type:
class Item(Enum):
NOTHING
POTION
SPELLBOOK
WAND
For example, the following figure show a 4 × 4 labyrinth.
4×4 Labyrinth
We’ve marked your starting position with a smiley face and the positions of 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 nullptr, and only its south pointer would point
somewhere (specifically, to the cell in the bottom‐left corner).
Each MazeCell has a variable named whatsHere that indicates what item, if any, is at that
position. Empty cells will have whatsHere set to the Item.NOTHING. The cells containing
the Spellbook, Potion, or Wand will have those fields set to Item.SPELLBOOK, Item.POTION,
or Item.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:
1. ESNWWNNEWSSESWWN
2. SWWNSEENWNNEWSSEES
3. WNNEWSSESWWNSEENES
Each path is represented as a sequence of letters (N for north, W for west, etc.) that, when
fol‐lowed 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.
Milestone 1: Check Paths to Freedom
Your first task is to write a function that, given a cell in a maze and a path, checks whether
that path is legal and picks up all three items. Specifically, in the file main.py, implement the
function:
is_path_to_freedom(start_location: MazeCell, path: str) ‐> bool
This function takes as input your starting location in the maze 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.
The start_location should not be not None: make sure you an add an assert to the top of
the function to check for this precondition.
The path string may have characters that are not valid (i.e. not N, S, E, or W). If it does, you
should raise a ValueError exception, including a message that indicates what the invalid
character was.
To summarize, here’s what you need to do.
1. Implement the is_path_to_freedom function in main.py.
2. Test your code thoroughly using the tests found in test_main.py.
To run the test, you should just be able to press the “Play” button in VS Code, or you
can do the following in the Terminal: python3 ‐m pytest test_main.py
If you’d like to add your own tests to this file you’re welcome to do so, though it’s
not required here.
Notes
Some notes on this problem:
1. Your code should work for a MazeCell from any possible maze, not just the one
shown above.
2. 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.
3. A path might visit the same location multiple times, including possibly visiting
locations with items in them multiple times.
4. You shouldn’t need to create any new MazeCell objects in the course of solving this
problem. After all, your job is to check a path in an existing maze, not to make a new
maze.
5. Feel free to implement this function either iteratively or recursively, whichever
seems best to you. You don’t need to worry about recursion depth issues here; we’ll
never run your code on anything large enough to cause a problem.
6. 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.
7. 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.
Milestone 2: Escape From your Personal Labyrinth
Your next task is to escape from a labyrinth that’s specifically constructed for you. The
starter code we’ve provided will use your name(s) to build you 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.
In the file main.py and you’ll see three ALL_CAPS variables. (By convention, ALL_CAPS
variables are meant to represent variables that should never be reassigned.) The first one,
YOUR_NAME, is a spot for your name. Right now, it’s marked with a TODO message. Edit this
string so that it contains your full name.
This first half of main generates a personalized labyrinth based on the YOUR_NAME
constant and returns a pointer to one of the cells in that maze. It then checks whether the
constant PATH_OUT_OF_MAZE a sequence that will let you escape from the maze. Right now,
PATH_OUT_OF_MAZE 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 the main function. Run the program in VS Code, making sure you select
“Debug Python File” instead of the default run mode (“Run Python File”). When you do, you
should see the variables window pop up, along with the contents of start_location, which
is the MazeCell where we’ve dropped you into the labyrinth. Clicking the “>” symbol next
to the variable name in the debugger window will let you read the contents of the
whatsHere field of start_location (it’ll be Item.NOTHING), as well as the four reference
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 you can only move in some of them. The
pointers in directions you can’t go are all equal to None. The pointers that indicate
directions you can go will all have dropdown arrows near them. Clicking one of these
arrows will show you the MazeCells reachable by moving in the indicated directions. 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!
Draw a lot of pictures. Grab a sheet of paper and map out the maze you’re in. There’s no
guarantee where you begin in the maze: 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 out the maze, construct an escape sequence and stash it in the constant
PATH_OUT_OF_MAZE, then see if you pass the first test. If so, fantastic! You’ve escaped! If not,
you have lots of options.
You could step through your is_path_to_freedom 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 misdrew your map and you’ve ended up somewhere without
all the items. It’s also easy to get your directions backwards when you have it mapped out
on paper so be careful about that! You could alternatively set the breakpoint at the test case
again and walk through things a second time, seeing whether the picture of the maze you
drew was incorrect.
To summarize, here’s what you need to do:
1. Edit the constant YOUR_NAME at the top of main.py with a string containing your
name. Don’t skip this step! If you forget to do this, you’ll be solving the “default
labyrinth”, which is the wrong one! (You unfortunately won’t get credit for solving
this incorrect labyrinth).
2. Set a breakpoint at the first indicated line in main.py and run the program in debug
mode to trigger the debugger.
3. Map out the maze on a sheet of paper and find where all the items are. Once you’re
done, stop the running program.
4. Find a path that picks up all three items and edit the constant PATH_OUT_OF_MAZE at
the top of main.py with that path. Run the test a second time with the debugger
turned off to confirm you’ve escaped.
Milestone 3: Escape from Your Personal Twisty Labyrinth
Now, let’s make things a bit more interesting. 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.
In this section, we’re 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 right.
The figure below shows one of these strange new types of labyrinths.
Twisty Labyrinth
This maze is stranger than the previous one you explored. For example, you’ll notice that
these 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 a second, 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 that generates a twisty labyrinth personalized with
the YOUR_NAME 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 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 Python has a memory
address associated with it. Memory addresses typically are written out in the form
0xsomething, where something 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 listed with the object (e.g. it
will say “MazeCell object at 0xbadbeef”).
For example, suppose that you’re in a maze and your starting location has address
0x10c3fa10 (the actual number you see will vary based on your computer), 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 0x10c3fa10. 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! To recap, here’s what you need to do:
1. Set a breakpoint at the indicated line in main and run the program in debug mode to
trigger the debugger.
2. Map out the twisty maze on a sheet of paper and find where all the items are and
how the cells link to each other. Once you’re done, stop the running program.
3. Find an escape sequence, and edit the constant PATH_OUT_OF_TWISTY_MAZE at the
top of main.py with that constant. Run the tests again–this time without the
breakpoint–and see if you’ve managed to escape!
Notes on this Milestone
Some notes on this milestone:
1. The memory addresses of objects 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 MazeCells 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.
2. You are guaranteed that if you follow a link from one MazeCell to another, there will
al‐ways 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.
3. 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.
4. 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!
5. 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.
Final Words
At this point, you have a solid command of how to use the debugger to analyze linked
structures. You know how to recognize memory addresses, how to manually follow links
between objects, and how to reconstruct the full shape of the linked structure even when
there’s bizarre and unpredictable cross‐links between them. We hope you find these skills
useful as you continue to write code that works on linked lists and other linked structures!
Grading
You will receive the following points for completing each of the three milestones.
• Milestone 1: Correctly implemented is_path_to_freedom <#pts 5>
• Milestone 2: Correct value for PATH_OUT_OF_MAZE with YOUR_NAME set to your name.
<#pts 5>
• Milestone 3: Correct value for PATH_OUT_OF_TWISTY_MAZE with YOUR_NAME set to
your name. <#pts 8>