Quiz 1 Makeup Resubmit
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 1 Makeup Resubmit -- Fall 2017
If your Quiz 1 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, 10/9, 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.
You can use the files you downloaded for the in-class Quiz 1 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.
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
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.
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
function will provide a concise summary of built-in operations on data
help(set)) or information about the arguments for the
built-in functions (e.g.,
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
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
Each test case is worth one point for a total of 20 points. Your score will be computed from the number of tests you pass. If you pass all the tests for a problem, you'll receive full credit. If you pass 2 of the 5 tests, you'll receive 40% of the credit for the problem. 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.
Run length encoding is a simple technique to compress sparse strings
of data featuring runs (sequences of the same character). In this
problem, each run of a character is shortened to a single character
followed by the length of the run. For example,
WWWWWWWWW is encoded
AB, likewise, becomes
Given a string
S, return a string that is the run length encoding of
S. Assume only alphabetic, capital characters occur in the
string (A-Z only).
In chess, the knight moves as follows:
Locations on a chessboard are represented as coordinates of the form
Y are integers between
the horizontal coordinate and
Y is the vertical coordinate. Given
B on the chessboard, write a program
how_many_knight_moves( A, B ) that returns the minimum number
of knight moves necessary to move from A to B. Of course, each intermediate
move should be to a square on the board. Note that it is always possible
to move a knight between any two squares.
Tic-tac-toe is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 board. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.
We'll represent the board as a 9-character string where each character is
"O" if the square as been filled, or
"-" is the square
is empty. String characters 0-2 give the marks on the top row of the
board left-to-right, characters 3-5 the middle row, and characters 6-8 the
"X-X-OXOXO" is the representation for the board shown
Your task is write the
enumerate_tic_tac_toe(board) procedure where
board is the string representation of a game after some moves have
been made. The procedure should enumerate all possible ending boards,
starting with the in-progress game and assuming that X will make the
next move. Consider all possible legal moves as each player takes
their turn. A game ends when one player wins or all the squares have
been filled. Once a game has ended no further moves are allowed.
The procedure should return a list of tuples
ending_boardis a 9-character string representation of a board state when the game ended, and
winneris one of
"O"if one of the players has won, or
"-"if the game ended because all the squares were filled but neither player won.
There should be one entry in the list for each possible sequence of legal moves. Note that a particular ending board may appear multiple times in the list since the same ending board can be generated with different sequences of moves. The list can be in any order.
# O has already won enumerate_tic_tac_toe("OX-XO-X-O")` => [("OX-XO-X-O", "O")] # X has already won enumerate_tic_tac_toe("O-O-O-XXX") => [("O-O-O-XXX", "X")] # tie enumerate_tic_tac_toe("XOXXOOOXX") => [("XOXXOOOXX"), '-'] # 4 possible outcomes enumerate_tic_tac_toe("XOXOXO---") => [('XOXOXO--X', 'X'), ('XOXOXOOXX', 'X'), ('XOXOXOX--', 'X'), ('XOXOXOXXO', 'X')]