# Quiz 2 Practice Problems

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.

### 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**-- it will be your job to fill in the values of these cells.`-1`

indicates that the value is missing

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

### Problem 4: Advanced Forestry

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

`"data"`

stores the data value that this node tells us is in the set.`"left"`

points to a subtree with data values*less than*`"data"`

, or contains`None`

if that subtree is empty.`"right"`

points to a subtree with data values*greater than*`"data"`

, or contains`None`

if that subtree is empty.`"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.`"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:

`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**-- it will be your job to fill in the values of these cells.`-1`

indicates that the value is missing`magic_sum`

: the magic sum of the completed magic square.`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:

- 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]]`

. - One valid solution to
`solve_magicsquare_recursive([[-1, -1], [-1, -1]], 4, [1, 2, 3, 4])`

is`[[2, 2], [2, 2]]`

.