{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Homework 7 Solutions\n",
"\n",
"* Course Instructor: David Dumas\n",
"* Solutions prepared by: Johnny Joyce"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Instructions:\n",
"\n",
"* Complete the problems below, which ask you to write Python scripts.\n",
"* 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.)\n",
"\n",
"### Deadline\n",
"\n",
"This homework assignment must be submitted in Gradescope by **Noon central time on Tuesday 1 March 2022**.\n",
"\n",
"### Collaboration\n",
"\n",
"**Collaboration is prohibited**, and you may only access resources (books, online, etc.) listed below.\n",
"\n",
"### Resources you may consult\n",
"\n",
"The course materials you may refer to for this homework are:\n",
"\n",
"* [Worksheet 7 Solutions](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/worksheets/worksheet7soln.html)\n",
"* [Lecture 15 - Recursion with backtracking](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture15.html)\n",
"* [Lecture 16 - Mergesort](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture16.html)\n",
"* [Lecture 17 - Quicksort](http://dumas.io/teaching/2022/spring/mcs275/slides/lecture17.html)\n",
"* Any of the course [sample programs](https://github.com/daviddumas/mcs275spring2022/tree/main/samplecode); of particular note:\n",
" * [maze.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/recursion/maze.py)\n",
" * [solvemaze.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/recursion/solvemaze.py)\n",
" * [sorts.py](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/recursion/sorts.py)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"* MCS 260 course materials from Fall 2021:\n",
" * [Slides, homework, worksheets, and projects](https://www.dumas.io/teaching/2021/fall/mcs260/)\n",
" * [Sample programs](https://github.com/daviddumas/mcs260fall2021/tree/main/samplecode)\n",
"\n",
"### Point distribution\n",
"\n",
"This homework assignment has two problems, numbered 2 and 3. The grading breakdown is:\n",
"\n",
"| Points | Item |\n",
"| --- | --- |\n",
"| 2 | Autograder |\n",
"| 4 | Problem 2 |\n",
"| 4 | Problem 3 |\n",
"| **10** | Total |\n",
"\n",
"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.\n",
"\n",
"### What to do if you're stuck\n",
"\n",
"Ask your instructor or TA a question by email, in office hours, or on discord."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 1 doesn't exist\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 2: List of accessible locations\n",
"\n",
"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).\n",
"\n",
"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)`.\n",
"\n",
"As in `solvemaze.py`, you should use the interface provided by the `Maze` class from [`maze.py`](https://github.com/daviddumas/mcs275spring2022/blob/main/samplecode/recursion/maze.py).\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is an example of the output of this function when applied to the 7x7 example maze we discussed in lecture."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1, 1),\n",
" (1, 2),\n",
" (1, 3),\n",
" (2, 3),\n",
" (3, 3),\n",
" (4, 3),\n",
" (5, 3),\n",
" (5, 2),\n",
" (5, 1),\n",
" (4, 1),\n",
" (3, 1),\n",
" (3, 4),\n",
" (3, 5),\n",
" (2, 5),\n",
" (1, 5),\n",
" (4, 5),\n",
" (5, 5)]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Need to import maze and define accessible_locations before this will work!\n",
"M = maze.MazeExample1()\n",
"accessible_locations(M)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As a reminder, here is a picture of this maze, which can be used to check the correctness of the list above.\n",
"![7x7 maze](images/small-with-coords-scaled.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(2, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3)]"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"M = maze.Maze(5,5)\n",
"M.apply_border()\n",
"M.start = (2,2)\n",
"\n",
"L = accessible_locations(M)\n",
"assert(len(L)==9) # make sure we found all 9 interior squares accessible!\n",
"L"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import maze\n",
"\n",
"def accessible_locations(M,path=None,visited=None):\n",
" \"\"\"\n",
" Returns list of all locations that can be reached from M.start\n",
" \"\"\"\n",
" if visited==None: # Initialize `visited` upon first call\n",
" visited=[M.start]\n",
" if path==None: # Initialize `path` upon first call\n",
" path = [M.start]\n",
" if path[-1] not in visited: # Keep track of locations\n",
" visited.append(path[-1])\n",
" \n",
" # Find all possible directions to go from current location\n",
" current_location = path[-1]\n",
" steps = M.free_neighbors(*current_location) # `*` sign lets us give x and y coords as two separate args\n",
" \n",
" for s in steps:\n",
" if len(path)>=2 and s == path[-2]:\n",
" continue\n",
" if s in visited:\n",
" continue\n",
" accessible_locations(M,path+[s],visited)\n",
" return visited"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 3: Specialized quicksort for few distinct values\n",
"\n",
"Suppose you're quicksorting a list that has only a few distinct values, like\n",
"```python\n",
"[2, 3, 2, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 3, 1, 2, 2, 3, 3, 3]\n",
"```\n",
"(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.\n",
"\n",
"Write a version of quicksort that is adapted to this special case by replacing the step that calls `partition` with:\n",
"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.\n",
"1. If so, then this part of the list is already sorted. Return.\n",
"1. Otherwise, partition the list and proceed as usual with recursive calls.\n",
"\n",
"Call the new function `quicksort_few_distinct(L)` and put it in a file called `hwk7prob3.py`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution 1 (list comprehension - shortest way):\n",
"\n",
"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"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def quicksort_few_distinct(L,start=0,end=None):\n",
" \"\"\"\n",
" Quicksort the part of list L between indices\n",
" start and end in place. Optimized for use with lists\n",
" containing few distinct elements repeated many times\n",
" \"\"\"\n",
" if end == None:\n",
" end = len(L)\n",
" if end-start > 1:\n",
" # there are at least two elements,\n",
" # so some work is necessary\n",
" print(\"Quicksort called on\",L[start:end])\n",
" first = L[start]\n",
" # List comprehension checks if value of each item is same as first value.\n",
" if all([x == first for x in L]):\n",
" return\n",
" else:\n",
" m = partition(L,start,end)\n",
" quicksort(L,start,m)\n",
" quicksort(L,m+1,end)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution 2:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def quicksort(L,start=0,end=None):\n",
" \"\"\"\n",
" Quicksort the part of list L between indices\n",
" start and end in place.\n",
" \"\"\"\n",
" if end == None:\n",
" end = len(L)\n",
" if end-start > 1:\n",
" # there are at least two elements,\n",
" # so some work is necessary\n",
" print(\"Quicksort called on\",L[start:end])\n",
" all_vals_equal_first = True # Keep track of whether every item in L has same value as first item\n",
" for i in L:\n",
" if i != L[0]:\n",
" all_vals_equal_first = False\n",
" break\n",
" if all_vals_equal_first:\n",
" return\n",
" else:\n",
" m = partition(L,start,end)\n",
" quicksort(L,start,m)\n",
" quicksort(L,m+1,end)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}