This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 13, 2024.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
This assignment corresponds to Worksheet 5, which is about recursion (including the idea of recursion with backtracking).
The materials you may refer to for this homework are:
This homework assignment has 2 problems. The grading breakdown is:
| Points | Item |
|---|---|
| 4 | Autograder syntax checks |
| 5 | Problem 2 |
| 5 | Problem 3 |
| 14 | Total |
Ask your instructor or TA a question by email, in office hours, or on discord.
Testing your work (which is highly recommended) will require you to import the maze module, so make sure you have these two files in your working directory:
Then, copy and paste the following function (from lecture 11) into a new file called hwk5.py. You'll modify it as part of your work.
def depth_first_maze_solution(M, path=None):
"""
Take a Maze object `M` and optional partial
progress `path` (list of Point2 objects) and
complete to a solution recursively.
**This function can solve mazes with loops.**
"""
if path == None:
# no path given, begin at M.start
path = [M.start]
if path[-1] == M.goal:
# path is a solution, return!
return path
# enumerate possible next steps
possible_next = M.free_neighbors(path[-1])
# then remove any places we've already been
possible_next = [x for x in possible_next if x not in path]
# consider next steps
for next_step in possible_next:
new_path = path + [next_step]
res = depth_first_maze_solution(M, new_path)
if res: # if res is a nonempty list, i.e. not None
# res is in fact a solution; return it
return res
# no possible next step worked out
return None
Put your work for this problem in a file called hwk5.py.
The function solvemaze(...) we wrote in Lecture 11 finds a path from the start of a maze to its goal. These two points are stored as attributes of a Maze instance.
One could just as well ask for a route between any two points in a maze, and your task for this problem is to modify solvemaze(...) in order to make a new function that does exactly that.
Specifically, write and submit a new function (still recursive) based on solvemaze that has the following definition line and which does as the docstring says.
def maze_path(M,p,q,path=None):
"""
Use recursion with backtracking to find a path in `Maze`
object `M` from point `p` to point `q` (both are `Point2`
objects). If `path` is given, it should be a list of points
beginning with `p`, and the search will only look for paths
that extend this list.
Points `p` and `q` must be free squares in the maze. If
either is wall, this function raises ValueError since the
question does not make sense.
Returns the path that is found, or if no such path exists,
returns `None`.
Does not modify `M` at all.
"""
I recommend you do this by starting with the code in the body of solvemaze and making a few changes.
Put your work for this problem in the same file as the last problem, hwk5.py.
Suppose we have a maze that is like the random mazes generated by PrimRandomMaze in the sense that there is exactly one path between any two points $p$ and $q$ that are not walls. If you subtract one from the length of that path, the result is called the path distance between $p$ and $q$ which is denoted by $dist(p,q)$. Subtracting one ensures that $dist(p,p)=0$ and that $dist(p,q)=1$ if $p$ and $q$ are neighbors.
If $x$ is one of the points on the path from $p$ to $q$, then $dist(p,x) + dist(x,q) = dist(p,q)$. This reflects the fact that you can stop at $x$ on your way from $p$ to $q$ without making any detour. For a general point $x$, the quantity $$ dist(p,x) + dist(x,q) - dist(p,q) $$ tells you the detour distance of $x$ during a trip from $p$ to $q$, meaning the minimum additional distance you would need to add to your trip from $p$ to $q$ in order to stop at $x$.
Write a function
def maze_detour_dist(M,p,q,x):
that takes a maze M and Point2 objects p,q,x that are free locations (not walls) of M, and which computes and returns the detour distance of x during a trip from p to q.
You can (and should) use the function maze_path from problem 2 to do this. Even if you don't get the function to work in problem 2, we'll evaluate your answer to this problem on the basis of whether it works when a correct maze_path function is provided.