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

# MCS 275 Spring 2022 Homework 7 Solutions¶

• Course Instructor: David Dumas
• Solutions prepared by: Johnny Joyce

## 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. (If you upload a screenshot or other file format, you won't get credit.)

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 1 March 2022.

### Collaboration¶

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

### Resources you may consult¶

The course materials you may refer to for this homework are:

### Point distribution¶

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

Points Item
4 Problem 2
4 Problem 3
10 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 1 doesn't exist¶

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

## Problem 2: List of accessible locations¶

Suppose that instead of trying to solve a maze (find a path from start to goal), you want to determine all accessible squares in the maze (i.e. all locations that can be reached by a path from start).

In a file called hwk7prob2.py, write a function accessible_locations(M) that takes a maze object M and returns a list of all locations in M that can be reached from M.start. It is fine for this function to have other parameters as long as they have default values, so that the function can be called as accessible_locations(M).

As in solvemaze.py, you should use the interface provided by the Maze class from maze.py.

You aren't required to use recursion here, but the most direct way to solve this problem is to make the minimum necessary changes to solvemaze() and retain the basic recursive strategy. The problems from worksheet 7 may also be useful.

Here is an example of the output of this function when applied to the 7x7 example maze we discussed in lecture.

In [13]:
# Need to import maze and define accessible_locations before this will work!
M = maze.MazeExample1()
accessible_locations(M)

Out[13]:
[(1, 1),
(1, 2),
(1, 3),
(2, 3),
(3, 3),
(4, 3),
(5, 3),
(5, 2),
(5, 1),
(4, 1),
(3, 1),
(3, 4),
(3, 5),
(2, 5),
(1, 5),
(4, 5),
(5, 5)]

As a reminder, here is a picture of this maze, which can be used to check the correctness of the list above.

As another example, this code creates a 5x5 maze with all its interior squares free, and with (2,2) as the start, and tests the function on it.

In [18]:
M = maze.Maze(5,5)
M.apply_border()
M.start = (2,2)

L = accessible_locations(M)
assert(len(L)==9) # make sure we found all 9 interior squares accessible!
L

Out[18]:
[(2, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3)]

# Solution¶

In [ ]:
import maze

def accessible_locations(M,path=None,visited=None):
"""
Returns list of all locations that can be reached from M.start
"""
if visited==None: # Initialize visited upon first call
visited=[M.start]
if path==None: # Initialize path upon first call
path = [M.start]
if path[-1] not in visited: # Keep track of locations
visited.append(path[-1])

# Find all possible directions to go from current location
current_location = path[-1]
steps = M.free_neighbors(*current_location) # * sign lets us give x and y coords as two separate args

for s in steps:
if len(path)>=2 and s == path[-2]:
continue
if s in visited:
continue
accessible_locations(M,path+[s],visited)
return visited


## Problem 3: Specialized quicksort for few distinct values¶

Suppose you're quicksorting a list that has only a few distinct values, like

[2, 3, 2, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 3, 1, 2, 2, 3, 3, 3]


(which has 20 entries but only 3 distinct values). In this case, a recursive algorithm that repeatedly partitions the list is likely to sometimes end up working on a sublist in which every value is the same. Once the part of the list you're working on looks like that, e.g. [1,1,1,1] or [2,2,2,2,2], it's already sorted and there's no point in partitioning it further and making recursive calls.

Write a version of quicksort that is adapted to this special case by replacing the step that calls partition with:

1. Check whether every element of (the current part of) the list is equal to the first element (of the current part) of the list.
2. If so, then this part of the list is already sorted. Return.
3. Otherwise, partition the list and proceed as usual with recursive calls.

Call the new function quicksort_few_distinct(L) and put it in a file called hwk7prob3.py.

# Solution 1 (list comprehension - shortest way):¶

Both solutions are edited versions of sorts.py on the class Github in samplecode/recursion/. Direct link: https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/recursion/sorts.py

In [ ]:
def quicksort_few_distinct(L,start=0,end=None):
"""
Quicksort the part of list L between indices
start and end in place. Optimized for use with lists
containing few distinct elements repeated many times
"""
if end == None:
end = len(L)
if end-start > 1:
# there are at least two elements,
# so some work is necessary
print("Quicksort called on",L[start:end])
first = L[start]
# List comprehension checks if value of each item is same as first value.
if all([x == first for x in L]):
return
else:
m = partition(L,start,end)
quicksort(L,start,m)
quicksort(L,m+1,end)


# Solution 2:¶

In [ ]:
def quicksort(L,start=0,end=None):
"""
Quicksort the part of list L between indices
start and end in place.
"""
if end == None:
end = len(L)
if end-start > 1:
# there are at least two elements,
# so some work is necessary
print("Quicksort called on",L[start:end])
all_vals_equal_first = True # Keep track of whether every item in L has same value as first item
for i in L:
if i != L[0]:
all_vals_equal_first = False
break
if all_vals_equal_first:
return
else:
m = partition(L,start,end)
quicksort(L,start,m)
quicksort(L,m+1,end)