A document from MCS 275 Spring 2023, instructor Emily Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Homework 6

  • Course Instructor: Emily Dumas

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work.

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 21, 2023.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Content

This assignment is about recursion with backtracking. It's a little shorter than usual as I know you're working on Project 2, and this assignment and that project cover some similar ground.

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 3 problems, numbered 2, 3, and 4. The grading breakdown is:

Points Item
3 Autograder
6 Problem 2
9 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 2: Does the maze have a short solution?

Like much of worksheet 6, this problem builds on the work we did in solvemaze.py.

What the length of a solution means

Recall our convention is that the solution to a maze is a list of Point2 objects. The length of a solution to the maze is defined as the number of objects in that list. So if the start is at Point2(1,1) and the goal is at the adjacent location Point2(1,2), then the list [Point2(1,1), Point2(1,2)] would be a solution of length 2.

Your task

Write a function can_be_solved_maxlen(M,k) that takes a Maze object M, an integer k and returns a boolean value:

  • True if maze M has a solution of length k or less.
  • False is returned otherwise (i.e. if M has no solution at all, or if all solutions to M have length greater than k).

It would be reasonable to use depth_first_maze_solution from solvemaze.py as a starting point for your work, modifying it to do what is needed in this problem.

Put this function in a file called mcs275hwk6.py and upload it. You don't need to upload any other files (e.g. no need to include plane.py or maze.py).

Something to be careful about

A maze might have multiple solutions. Suppose you find a solution of length 30. There might be another solution of length 22, and so you can't necessarily determine the return value for can_be_solved_maxlen(M,25) on the basis of the length of the first solution that's found.

Revision history

  • 2023-02-16 Initial publication