Quiz 2 Practice Problems

You are not logged in.

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.

Practice Problems for 6.009 Quiz 2 (Fall 2017)

Since these are practice problems, there is nothing to turn in! We have included unit tests for each problem: the unit test for Problem 1 is called TestProblem1, and so on.

The following file contains quiz.py and test.py: q2_problems.zip

Problem 1: solve_latin_square

A Latin square is an n x n grid of numbers in which each row and each column contains the numbers 1, 2, ..., n exactly once. Below is an example of a 3 x 3 Latin square.

You are given a partially filled square with empty cells. Your task is to produce a Latin square by filling the empty cells, or determine that the task is impossible. We recommend that you perform a search over all possible values to place in the empty cells. This problem should remind you of Tent Packing lab.

Suppose you were given the following partially filled 3 x 3 square.

One way to fill in the empty squares with values of 1, 2, or 3 to produce a Latin square is shown above in the first figure.

For this question you will implement the solve_latin_square method to the specification below.

INPUTS:

• grid: a list-of-lists representation of a partially filled square. grid[r][c] gives the value of the cell in row r and column c (grid[0][0] gives the value in the top left corner). A value of -1 indicates that the value is missing -- it will be your job to fill in the values of these cells.

OUTPUT:

If a solution exists, your program should return a list-of-lists finished_grid, corresponding to grid with the empty cells filled in properly. Multiple solutions may exist -- you only need to return one.

If no solution exists, your program should return False.

EXAMPLES:

• Using the example above, one valid solution to solve_latin_square([[1, -1, -1], [-1, 3, -1], [-1, -1, -1]]) is [[1, 2, 3], [2, 3, 1], [3, 1, 2]].
• One valid solution to solve_latin_square([[-1, -1], [-1, -1]]) is [[1, 2], [2, 1]].

Problem 2: is_proper

A black-red tree can store information across successive levels of nodes, starting with the root. Each node is colored either black or red (hence the name) and points to up to 2 children: a left child and/or a right child. The child(ren) of any node can be of either color.

We say that a black-red tree is proper if it satisfies the following property: Any path from the root to a leaf contains the same number of black nodes. Recall that a leaf is a node with no children.

We implement a black-red tree as a nested dictionary. Each node in the black-red tree is a dictionary containing:

• "color": the color of the node as a string, either "black" or "red"
• "left": the left child, as another dictionary, if it exists. If the node does not have a left child, then the value is -1.
• "right": the right child, as another dictionary, if it exists. If the node does not have a right child, then the value is -1.

Consider the following example of a proper black-red tree in which any path from the root to a leaf contains exactly 2 black nodes.

root1, the root of this proper black-red tree, in our implementation, is

{
"color": "black",
"left": {
"color":  "black",
"left":   -1,
"right":  -1
},
"right":{
"color":  "red",
"left":   {
"color":    "black",
"left":     -1,
"right":    -1
},
"right":  {
"color":    "black",
"left":     -1,
"right":    -1
}
}
}


In contrast, the following black-red tree is NOT proper. The path from the root to the left leaf contain 1 black node, while the path from the root to the right leaf contains 0 black nodes.

root2, the root of this second black-red tree, in our implementation, is:

{
"color":  "red",
"left":   {
"color":  "black",
"left":   -1,
"right":  -1
},
"right":  {
"color":  "red",
"left":   -1,
"right":  -1
}
}


For this question you will implement the is_proper method to the specification below.

INPUTS:

• root: the root of a black-red tree, as a dictionary.

OUTPUT:

A Boolean (True/False) indicating whether the black-red tree is proper.

EXAMPLES:

• is_proper(root1) with root1 as defined above should return True.
• is_proper(root2) with root2 as defined above should return False.

HINT: Many approaches can work here. One approach (might not be the simplest to implement) is to recursively find all paths from the root to a leaf. Then, you can check the number of black nodes in each path.

Problem 3: Prairie Dog Housing Lottery

Please implement the function lottery(prairie_dogs, capacities), which assigns prairie dogs to available burrows. Not all prairie dogs are willing to live in all burrows; they have idiosyncratic individual preferences. Furthermore, each borrow can only fit so many prairie dogs. The first input value is a list with one element per prairie dog, where each element is itself a list of numbers (in no particular order), each number standing for a burrow that this prairie dog will accept. The second input value is a list giving burrow capacities. Indices in this list correspond to numbers from the prairie-dog-preference lists. If an assignment exists from prairie dogs to burrows, satisfying everyone's preferences, then return that assignment, as a list of numbers, following the same order as the original list. If no satisfactory assignment exists, return None.

Warning: there are solutions to this problem at a variety of sophistication levels. The simplest solutions will be too slow for the largest test cases! You'll need to apply some of the ideas from class to finish all the tests in time.

Examples:

lottery([[2], [1], [0]], [1, 1, 1]) should return [2, 1, 0].

lottery([[0, 1], [1, 0], [0, 1]], [1, 1]) should return None.

lottery([[0, 1], [2, 3], [4, 5], [0], [2], [4]], [1, 1, 1, 1, 1, 1]) should return [1, 3, 5, 0, 2, 4].

(Note that our test cases accept multiple correct answers, for those test cases whose answers aren't uniquely determined.)

In class, we have seen two styles of linked structures. With each "modification" to a structure, we can return a new version without modifying the original, or we can modify the original in-place. In this question, we will stick to the second kind, using modification.

We will be working with a peculiar combination of binary search trees and linked lists. Every node in a structure belongs to both a binary search tree and a linked list.

The binary-search-tree part is just as we saw in lecture. Recall that we may use these trees for representing sets of values. Some node is designated as the root, and each node has two children, left and right, either of which may be None. A node and all others reachable from it via left-child and right-child links is called a subtree. All data values in a node's left subtree must be lower than the node's own data value, and all data values in the right subtree must be higher.

Our wrinkle is to reuse the same nodes to form a linked list, taking us through all the nodes in sorted order. What added benefit does this wrinkle bring? It lets us answer range queries very efficiently: given a tree and data values u and v, we can quickly return a sorted list of all data values w in the tree such that u <= w <= v.

Every node of the tree is a dictionary. Here are the keys that every dictionary includes. (We augment this explanation with a picture afterward.)

1. "data" stores the data value that this node tells us is in the set.
2. "left" points to a subtree with data values less than "data", or contains None if that subtree is empty.
3. "right" points to a subtree with data values greater than "data", or contains None if that subtree is empty.
4. "prev" points to the tree node whose data value comes immediately before this one in sorted order, or contains None if this is the first element of the sorted list.
5. "next" points to the tree node whose data value comes immediately after this one in sorted order, or contains None if this is the last element of the sorted list.

Here is an example of one of these trees.

Nodes are circles with their data values inside. When number n appears inside node A, we have A["data"] == n. The root, with data value 3, appears highest. A node connects to its left child with a solid arrow going down and to the left, and solid rightward arrows connect to right children. So, node A with a solid left arrow to B and a solid right arrow to C has A["left"] == B and A["right"] == C. A dashed arrow from node A to node B indicates that A["next"] == B. Furthermore, we also record the information in the other direction: B["prev"] == A. Our tests will enforce exactly this convention for encoding nodes with dictionaries, so please follow it.

Your task is to write function insert(tree, data) implementing insertion into tree of a new node with data value data. Just as we learned in lecture, find the unique node nd of tree that currently has no left or right child, such that it is legal to insert the new node to the left or right of nd, respectively; and then go ahead and perform that insertion. It may also be necessary to fix up the "next" and "prev" pointers not just in the new node but also in some others from the original tree, to keep this linked list in sorted order. Note that this function doesn't return anything; we run it just for the modifications it makes to tree.

The test cases for this problem follow an unusually hard-to-read textual format, so we now include pictures of all the input trees. In the starter code, we also provide a function print_tree that generates a nicer rendering of a tree.

When t is the tree shown for Cases 7-8 and u is the tree given as an example output for Case 8 at the bottom, we have insert(t, 7) == u.

Problem 5: solve_magicsquare_recursive

A magic square is an n x n grid of numbers in which each row, each column, and both diagonals add to the same "magic sum". For example, shown below is a 3 x 3 grid with a magic sum of 15.

Suppose we were only given the partially filled 3 x 3 square without 2, 9, or 4 filled in:

If we were told that the magic sum is 15, we would be able to fill in the proper values to place in the empty cells, through a series of "deductions". A "deduction" involves examining a row/column/diagonal and inferring a proper cell value by utilizing magic_sum. For example, we deduce that 2 belongs in the top-left cell by calculating 15 - 6 - 7 = 2.

In addition to the grid, you will now be given choices, a list of numbers that you can use to fill the empty cells. The same number can be used to fill multiple empty cells. We recommend that you perform a search over the possible values to put in the empty cells. This should remind you of the recursive solutions you implemented in your labs.

For example, consider the following partially filled square.

Given that magic_sum = 15 and choices = [1, 2, 3, 4, 5, 6, 7, 8, 9], then one possible solution is the following, where we have filled in the empty cells with values in choices.

Implement the solve_magicsquare_recursive function to the specification below. You are guaranteed that a valid solution exists.

INPUTS:

1. grid: a list-of-lists representation of a partially filled square. grid[r][c] gives the value of the cell in row r and column c. A value of -1 indicates that the value is missing -- it will be your job to fill in the values of these cells.
2. magic_sum: the magic sum of the completed magic square.
3. choices: a list of numbers that can be used to fill the missing values. Each number in choices can be used to fill multiple empty cells.

OUTPUT:

A list-of-lists finished_grid, corresponding to grid with the empty cells filled in properly. An empty cell can only be filled in with a number in choices. Multiple solutions may exist -- you only need to return one.

EXAMPLES:

1. Using the example above, one valid solution to solve_magicsquare_recursive([[-1, 7, -1], [-1, -1, 1], [-1, 3, -1]], 15, [1, 2, 3, 4, 5, 6, 7, 8, 9]) is [[2, 7, 6], [9, 5, 1], [4, 3, 8]].
2. One valid solution to solve_magicsquare_recursive([[-1, -1], [-1, -1]], 4, [1, 2, 3, 4]) is [[2, 2], [2, 2]].