Quiz 1 Makeup Resubmit

The questions below are due on Saturday October 14, 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 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.

Download: quiz1.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

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.


Problem 1: run_length_encode

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 by W9. AB, likewise, becomes A1B1.

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).

Examples:

  • run_length_encode("") should return ""
  • run_length_encode("ABC") should return "A1B1C1"
  • run_length_encode("AACCA") should return "A2C2A1"
  • run_length_encode("ROOMMATE") should return "R1O2M2A1T1E1"

Problem 2: how_many_knight_moves

In chess, the knight moves as follows:

Locations on a chessboard are represented as coordinates of the form (X,Y), where X and Y are integers between 0 and 7. X is the horizontal coordinate and Y is the vertical coordinate. Given two locations A and 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.

Examples:

  • how_many_knight_moves((0,0), (0,0)) => 0
  • how_many_knight_moves((4,4), (3,2)) => 1
  • how_many_knight_moves((0,0), (4,0)) => 2
  • how_many_knight_moves((0,0), (7,7)) => 6

Problem 3: enumerate_tic_tac_toe

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 "X" or "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 bottom row. "X-X-OXOXO" is the representation for the board shown above.

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_board,winner) where

  • ending_board is a 9-character string representation of a board state when the game ended, and

  • winner is one of "X", "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.

Examples:

# 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')]