Quiz 2 Makeup Resubmit

The questions below are due on Thursday November 09, 2017; 10:00:00 PM.


You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.

6.009 Quiz 2 Makeup Resubmit -- Fall 2017

If your Quiz 2 Makeup doesn’t pass all the tests or you want to revise your earlier answers, we invite you to continue to work on the quiz over the weekend and resubmit using the submit form on this page. The deadline for resubmissions is Monday, November 6, at 10pm; resubmissions after the deadline will not be regraded.

In order to request a regrade for a question, you will have to submit corrected code that passes all the tests for the question and explain in Python comments your bug or the lack of functionality in your original solution. Also please indicate whether you believe this to be a large or a small change and explain your reasoning. That will help us award partial credit more efficiently and correctly. Over the following days, the staff will review your new code and award partial credit for any additional tests that you pass.

Example Large changes:

  • Changing data representation (that require code changes in multiple places)
  • Changes to control structure: e.g., add recursive case; add handling of return from recursion
  • Original code had "right idea"; new code completes the implementation of that original "idea". This is a large change.
  • Accumulation of multiple small changes for the problem

Example Small changes:

  • Fix to iteration range/termination line (e.g., to fix ending one element too soon)
  • An edit to a base case return value
  • An edit to a base case check
  • Changing nested list expressions to add/remove a level of list (e.g., return [[root]] instead of [root])

In general, if you are seeking credit for a "Small" change then you should seek to revise your code for submission making changes to the fewest lines of code that you can. If you wish to refactor your code for clarity (which we applaud!) you should do that on your own later, after resubmitting a minimally-changed version requesting "Small" change credit. (Of course, if you are making a "Large" change, you are welcome to refactor as that will not affect "Large" change credit.)

You can use the files you downloaded for the in-class Quiz 2 Makeup or redownload the .zip file below, which contains all the files, test cases, etc., you need to complete the quiz using your own machine. When unzipped it will create its own directory with the quiz’s files. The instructions follow below. You’ll be editing quiz.py to add the code requested by the instructions.

Download: quiz2_makeup.zip

Submission

When you have tested your code sufficiently on your own machine, submit your modified quiz.py below by clicking on "Choose File", then clicking the Submit button to send the file to the 6.009 server. To receive credit you must upload your code before the timer expires.

The server will run the tests and report back the results below but be aware that the server may be backlogged at the end of the quiz session. Once the server has indicated that your submission is queued to be checked, you're all set -- your submission has been accepted as on time and you don't need to wait for the results to be reported.

 No file selected

Instructions

This quiz assumes you have Python 3.5 (or a later version) installed on your machine.

This quiz is closed-book and closed-Internet -- you are only allowed to access the quiz page on the 6.009 website and the material provided in the .zip file. You are not allowed to access other information on your laptop or on the web. When you unzip the .zip file, you'll find library.pdf, which includes the chapters 1-4 of the Python Library Reference -- they cover the built-in functions (Chap. 2) and built-in data types (Chap. 4). Note that Python's built-in help function will provide a concise summary of built-in operations on data types (e.g., help(set)) or information about the arguments for the built-in functions (e.g., help(sorted)).

Proctors will be available to answer administrative questions and clarify specifications of coding problems, but they should not be relied on for coding help.

As in the labs, test.py can be used to test your code in quiz.py. Each of the three problems has a unit test: TestProblem1, TestProblem2, etc. Remember that you can run tests for a specific problem like so

python3 test.py TestProblem1

This quiz is worth 20 points, based on 20 test cases. Your score will be computed from the number of tests you pass. If you pass all the tests, you'll receive full credit. If you pass 16 of the 20 tests, you'll receive 80% of the credit for the quiz (i.e., 16 points). Note that to pass some of the tests in the time allotted, your solution may have to be reasonably efficient.

Please do not import any Python modules to use as part of your solutions -- quizzes with import statements (or their equivalent!) will be given grades of 0.

You do not have to include doctests or detailed comments in your code.

Having your code check for a specific input (called "hard coding") and then return a specific result is okay only for the base cases in recursion. Solutions that look for specific test case arguments other than base cases are disallowed and will receive no credit.


Problem 1. flood_fill(image, location_clicked, new_color)

We seek to implement a 'flood fill' or 'color paint' algorithm such as is found in many graphical paint programs. Given a two-dimensional image consisting of color pixels, a particular pixel clicked on, and a new color value, we would like to produce a new image that replaces the color of that pixel with the new color, and also replaces with the new color all pixels that are "contiguous" to that pixel and have the same color as the original clicked on pixel. The original image should remain unchanged.

Two pixels are "contiguous" if there is a chain of (any mix of) horizontal and/or vertical abutting (directly next to each other) pixels within the image between those two pixels, all having the same color. Two pixels of the same color diagonal to each other are not contiguous through that diagonal positioning.

Our representation of an image is a dictionary of the form

{'height': <int>, 
 'width': <int>, 
 'pixels': <array of length width*height of integers representing
           the pixel colors, with the first i = width elements being 
           the first row of the image, and so forth>}

A location in the image is given by the tuple (row, column), counting columns and row indices from 0.

Two example flood fills are shown in Fig. 1.

flood fill examples


Problem 2. get_anagrams(word)

An anagram, as defined by Webster, is a word or phrase made by transposing the letters of another word or phrase. For example, the word "secure" is an anagram of "rescue".

Implement a generator get_anagrams that takes a single word (string) as an input, and produces all unique (no duplicate) valid anagrams of the word and of all subgroups of the letters in the word. A valid anagram is a word appearing in the set allwords provided to you below.

Note: some tests may require a fast enough implementation in order to complete in the time allowed.

Example:

  • set(get_anagrams('tomato')) ==> {'toot', 'oat', 'tom', 'am', 'too', 'mat', 'moat', 'tomato', 'tam', 'atom', 'moot', 'to', 'at', 'tat', 'toto', 'motto', 'tot'}

Problem 3. fast linked lists - LinkedList and LinkedNode classes

One of the advantages of linked lists is that it is inexpensive to "prepend" a new node onto the front of a linked list node. However, it can be expensive to "append" at the end of a linked list, because we need to locate the last node (or "tail") of what might be a very long chain of linked list nodes. One approach is to implemented a LinkedList class that keeps track of both the head and the tail of the chain of LinkedNode objects as pictured in Fig. 2, so it is very fast to either append or prepend a node onto the LinkedList. Also, since we may often want to get the length of a LinkedList (number of LinkedNodes in the LinkedList), we would like to implement the __len__ method so that this query can be answered in constant time (not in computation time that grows proportionally with the length of the LinkedList).

LinkedList and LinkedNodes example

Some examples using a (working) implementation are shown below.

>>> x = LinkedList()        # empty LinkedList
>>> x
LinkedList()                # __repr__ already provided
>>> len(x)
0
>>> y = LinkedList([1, 2])  # LinkedList initialized with two LinkedNodes
>>> y
LinkedList([1, 2])          # __repr__ shows contents when LinkedNode.nodes is implemented
>>> len(y)
2

We can also append values to a LinkedList, and can directly access the head and tail:

>>> x = LinkedList()
>>> x.append(1)
>>> x
LinkedList([1])
>>> x.head
LinkedNode(1)               # __repr__ output for LinkedNode
>>> x.tail
LinkedNode(1)
>>> len(x)
1

We can also prepend values, putting them at the front of a LinkedList:

>>> x = LinkedList()
>>> x.append(1)
>>> x.prepend(0)
>>> x
LinkedList([0, 1])
>>> x.head
LinkedNode(0, ...)
>>> x.tail
LinkedNode(1)
>>> len(x)
2

We can remove a given node from a LinkedList

>>> x = LinkedList([1,2,3])
>>> x
LinkedList([1, 2, 3])
>>> n2 = x.head.next
>>> n2
LinkedNode(2, ...)
>>> x.remove(n2)
>>> x
LinkedList([1, 3])
>>> x.remove(x.head)
>>> x
LinkedList([3])
>>> x.remove(x.tail)
>>> x
LinkedList()

as well as get the ith node from a LinkedList:

>>> x = LinkedList()
>>> x.append(99)
>>> x.prepend(0)
>>> x.get_node(1)
LinkedNode(99)

Finally, we can map a function over the values in a LinkedList, producing a new LinkedList with the result of the function applied to the corresponding value in the original LinkedList. The map_in_place method does the same thing, except it mutates the values in place in the original LinkedList.

>>> x = LinkedList([1, 2, 3, 4])
>>> y = x.map(lambda v: v*v)
>>> y
LinkedList([1, 4, 9, 16])
>>> x
LinkedList([1, 2, 3, 4])

>>> x = LinkedList([1, 2, 3, 4])
>>> x.map_in_place(lambda v: v*v)
>>> x
LinkedList([1, 4, 9, 16])

Several methods of LinkedList and LinkedNode have already been written and are provided in quiz.py; it will be very helpful to you to understand and potentially use some of those methods as you complete this problem. Your task is to complete the implementation of the LinkedList class, including to implement the following methods consistent with the docstring/doctest specifications for each of these methods in quiz.py.

  • LinkedList.append(self, val)
  • LinkedList.prepend(self, val)
  • LinkedList.remove(self, node)
  • LinkedList.get_node(self, i)
  • LinkedList.map_in_place(self, f)
  • LinkedList.map(self, f)

Debugging note: Your score for this problem will be based on passing tests in test.py. However, you can also run "python3 quiz.py" to run quiz.py as a script to run the doctests in the LinkedList and LinkedNode classes to aid in your debugging.