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: