代写Python编程设计、代做data程序、Python程序语言调试

日期：2021-03-30 10:48

Quiz 1 (Conflict)

The questions below are due on Thursday March 25, 2021; 11:55:00 AM.

Submissions to the quiz are no longer allowed. If there was an extenuating circumstance that prevented you from

submitting on time, please post a private note to the instructors on the forum within 15 minutes of the end of your

quiz, containing your code and an explanation of the issue. Otherwise, please use the resubmission page to

complete the resubmission..

6.009 CONFLICT Quiz 1 -- Spring 2021

Please download the .zip file below, which contains all the files, test cases, etc., you need to complete the quiz using your own

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

Download Your Last Submission

Click to View Your Last Submission

Click to Show All Submissions

Select File No file selected

Submit

You have submitted this assignment 7 times.

Instructions

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

You are allowed to access online materials, including search engines, forums, and the Python documentation, but we do not

expect these resources to be particularly helpful, so it is likely in your interest not to spend too much time searching them.

Additionally, your code submission should not include any code that you did not write yourself, and you should cite any sources

you referenced during the quiz. You may include code you previously wrote yourself, without attribution.

3/27/2021 Quiz 1 (Conflict) | Quiz 1 | 6.009 Spring 2021

https://py.mit.edu/spring21/quizzes/quiz1/conflict 2/5

You may not discuss the quiz with other students -- even after you complete the quiz and/or complete any regrade

submission -- until regrades have been completed for all students and final quiz scores assigned (at the end of next

week), because many students will still be working on regrades or other/conflict offerings of the quiz.

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)). This information is also available online as

part of the Python documentation.

Proctors will be available on the help queue 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 suite of tests in test.py.

Note that you can run tests for a specific problem like so

python3 test.py problem1

or

pytest test.py -k problem1

This quiz is worth 20 points; these points will ultimately translate to an equivalent grade for the quiz per the published 6.009

grading policy. Your quiz points score will be based primarily on performance of your last code submitted during the quiz,

tested against some number of test cases for each problem. However, points will be lost in other circumstances:

You must not import any Python modules to use as part of your solutions -- quizzes with import statements (or their

equivalents!) will be given grades of 0.

Having your code check for a specific input (called "hardcoding") and then return a specific result is okay only for the base

cases in iteration or recursion. Problem solutions that look for specific test case arguments other than base cases are

disallowed and will receive no credit.

Including comments and helper functions is encouraged, as it may help you organize your code. That said, if your code

passes all the test cases for a particular problem, then we will not deduct points from that problem for lack of comments

or for otherwise unoptimal style. For problems on which you do not pass all test cases, though, comments and otherwise

good style can help us award appropriate partial credit.

Your quiz score will be based primarily on test cases passing by your last-submitted file during the quiz, plus partial credit as

determined by a human grader. Partial credit is determined by the closeness of your code to a valid solution. Therefore,

consider leaving incomplete solutions, pseudocode, or even just detailed comments in English, even if one of your functions

passes no tests.

For your own debugging, you are welcome to add test cases of your own to test.py (but note that any tests you add will not

be run on the server). You may also write as many helper functions as you want in quiz.py.

Problem 1. Array à la Mode (5 Points)

For purposes of this problem, let the mode of a list of elements be the element that occurs most frequently within that list.

Complete this problem by filling in the definition of grid_mode in quiz.py. This function should take as input a 2-d array (list

of lists) inp containing arbitrary elements; and it should return a new 2-d array out of the same size, where the value of out at

3/27/2021 Quiz 1 (Conflict) | Quiz 1 | 6.009 Spring 2021

https://py.mit.edu/spring21/quizzes/quiz1/conflict 3/5

any location is the mode of the elements at that location and all neighboring locations in inp (in all 8 directions). Note that this

means for cells in the middle of the array, we will be computing the mode of collections of 9 elements at a time; but since cells

on the edge of the array have fewer neighbors, those will require computing the mode of a smaller collection of elements.

For example, when given the following array as input:

inp = [

['o', 'O', 7, 'o'],

[ 7, 7, 'o', 'o'],

['C', 7, 'o', 'f'],

['a', 'C', 'O', 'O'],

]

the output should be the following:

[[ 7, 7, 'o', 'o'],

[ 7, 7, 'o', 'o'],

[ 7, 7, 'o', 'o'],

['C', 'C', 'O', 'O']]

In all of the provided test cases, we guarantee that every cell's neighbors have a unique mode; so you do not have to worry

about breaking ties when computing the mode.

Problem 2. Catching the Bus (7 points)

Your friend needs your help to catch a moving bus in an infinite 2-d grid. We know the bus's schedule, and we want to use the

graph search algorithms we've built up in 6.009 to plan a path such that your friend and the bus end up in the same grid

location at the same time.

Assume that the search starts at time 0 with your friend in some location (r,c). On each step, time increases by 1, and your

friend can move to any of the eight neighboring locations (up, down, left, right, or any diagonal), or they can stay in the same

location.

We also know the bus's schedule, as a function that maps times to locations. This schedule is specified by a Python function,

which takes a time as input and returns the bus's location at that time as a tuple (r,c).

In quiz.py, we have provided an implementation of the catch_bus function, which takes two inputs:

your friend's starting location as an (r, c) tuple, and

the bus schedule, as a Python function mapping times to (r, c) tuples representing locations.

catch_bus, which makes use of the search code in search.py, should ultimately return a path of (r,c) values that your friend

could use to reach the bus. While there are multiple correct solutions for many of the test cases, it is important that your code

returns a path of minimal length (we want to help your friend catch the bus as soon as possible!).

Importantly, you should implement entire behavior without changing the catch_bus function. Instead of modifying catch

bus, you should implement the setup_bus_catcher function so that it returns an appropriate successor function, starting

state, and goal test function to be used in the search process.

3/27/2021 Quiz 1 (Conflict) | Quiz 1 | 6.009 Spring 2021

https://py.mit.edu/spring21/quizzes/quiz1/conflict 4/5

Ultimately, the form of the paths returned from the search function is up to you (and is based on your choice of state as

specified by the start state, as well as the successor and goal test functions), so you may also need to implement the

interpret_result function, to convert a path of that form into the right type that catch_bus is expected to return.

For example, consider calling this function with your friend starting at location (0,0) and the bus's schedule given by lambda

t: (1, t-3). The earliest your friend can catch the bus is at time 2. One such way to reach that location is shown below:

Time Friend Bus

0 (0, 0) (1, -3)

1 (1, 0) (1, -2)

2 (1, -1) (1, -1)

So one possible solution would be given by:

>>> catch_bus((0,0), lambda t: (1, t-3))

[(0,0), (1, 0), (1, -1)]

Other valid solutions include:

[(0, 0), (0, -1), (1, -1)]

[(0, 0), (0, 0), (1, -1)]

[(0, 0), (1, -1), (1, -1)]

Problem 3. Boggle Words (8 Points)

In the board game Boggle, players are presented with a 2-d grid of letters, and their goal is to look for words that can be

constructed from the letters in sequentially adjacent locations, where "adjacent" locations are those that neighbor a given

location horizontally, vertically, and diagonally. Any individual word may not re-use the letter in a given space.

In this problem, your goal is to write a small program to play Boggle by implementing the words_at_location function. Given

a 2-d array of letters (represented as a list of lists) and a starting location in terms of (row, column), your function should

return a set of all valid Boggle words that start at that location. To check whether a sequence of letters consitute a valid word,

we have provided a set called ALL_WORDS, which contains all sequences of characters that we should consider to be valid words.

Unlike the standard Boggle game, we will not assume that the boards we are given are four-by-four squares.

As an example, consider the following 2-d array:

board = [

['t', 'w', 'y', 'r'],

['e', 'n', 'p', 'h'],

['g', 's', 'c', 'r'],

['o', 'n', 's', 'e'],

]

which represents the following board:

3/27/2021 Quiz 1 (Conflict) | Quiz 1 | 6.009 Spring 2021

https://py.mit.edu/spring21/quizzes/quiz1/conflict 5/5

If we start from location (2, 1), representing row 2 and column 1 (the upper-left-most s letter), we see the following output:

>>> words_at_location(board, (2,1))

{'sego', 'sent', 'set', 'sew', 'sewn', 'son', 'song', 'sons', 'spry', 'spy'}

These words can be formed via the following paths: