# Homework 3

*Due by 11:59pm on Friday, 2/26*

## Instructions

Download hw03.zip. Inside the archive, you will find a file called hw03.py, along with a copy of the OK autograder.

**Submission:** When you are done, submit with ```
python3 ok
--submit
```

. You may submit more than once before the deadline; only the
final submission will be scored. See Lab 0 for instructions on submitting
assignments.

**Using OK:** If you have any questions about using OK, please
refer to this guide.

**Readings:** You might find the following references
useful:

## Required questions

## Sequences

The following three problems were optional in lab. If you haven't already done so, complete them (otherwise, copy your result from lab).

### Question 1: Flatten

Write a function `flatten`

that takes a (possibly deep) list and "flattens" it.
For example:

```
>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]
```

*Hint*: you can check if something is a list by using the built-in
`type`

function. For example,

```
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
```

```
def flatten(lst):
"""Returns a flattened version of lst.
>>> flatten([1, 2, 3]) # normal list
[1, 2, 3]
>>> x = [1, [2, 3], 4] # deep list
>>> flatten(x)
[1, 2, 3, 4]
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> flatten(x)
[1, 1, 1, 1, 1, 1]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q flatten`

### Question 2: Interleave

Write `interleave(s0, s1)`

, which takes two linked lists
and produces a new linked list with elements of `s0`

and `s1`

interleaved. In
other words, the resulting list should have the first element of the `s0`

, the
first element of `s1`

, the second element of `s0`

, the second element of `s1`

,
and so on.

If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.

```
def interleave(s0, s1):
"""Interleave linked lists s0 and s1 to produce a new linked
list.
>>> evens = link(2, link(4, link(6, link(8, empty))))
>>> odds = link(1, link(3, empty))
>>> print_link(interleave(odds, evens))
1 2 3 4 6 8
>>> print_link(interleave(evens, odds))
2 1 4 3 6 8
>>> print_link(interleave(odds, odds))
1 1 3 3
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q interleave`

### Question 3: Merge

Write a function `merge`

that takes 2 *sorted* lists `lst1`

and `lst2`

,
and returns a new list that contains all the elements in the two lists
in sorted order.

```
def merge(lst1, lst2):
"""Merges two sorted lists.
>>> merge([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge([], [2, 4, 6])
[2, 4, 6]
>>> merge([1, 2, 3], [])
[1, 2, 3]
>>> merge([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q merge`

## Mergesort

### Question 4: Mergesort

Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure:

- Break the input list into equally-sized halves
- Recursively sort both halves
- Merge the sorted halves.

Using your `merge`

function from the previous question, implement
`mergesort`

.

*Challenge*: Implement mergesort itself iteratively, without using
recursion.

```
def mergesort(seq):
"""Mergesort algorithm.
>>> mergesort([4, 2, 5, 2, 1])
[1, 2, 2, 4, 5]
>>> mergesort([]) # sorting an empty list
[]
>>> mergesort([1]) # sorting a one-element list
[1]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q mergesort`

## Trees

The following problems use the same `tree`

data abstraction as lecture, but
for brevity, we've renamed `make_tree`

as `tree`

.
The code you write should not apply the `[]`

operation to trees directly;
that's an abstraction barrier violation.
The `print_tree`

function is provided for convenience:

```
##############################################################
# An alternative implementation of the tree data abstraction #
##############################################################
def tree(label, children=[]):
for branch in children:
assert is_tree(branch), 'children must be trees'
return (label, children)
def label(tree):
return tree[0]
def children(tree):
return tree[1]
def is_tree(tree):
if type(tree) is not tuple or len(tree) != 2 \
or (type(tree[1]) is not list and type(tree[1]) is not tuple):
return False
for branch in children(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
return not children(tree)
def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the label.
>>> print_tree(tree(1))
1
>>> print_tree(tree(1, [tree(2)]))
1
2
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
"""
print(' ' * indent + str(label(t)))
for child in children(t):
print_tree(child, indent + 1)
```

## Mobiles

**Acknowledgements.** This mobile example is based on
a classic problem from Structure and Interpretation of Computer Programs,
Section 2.2.2.

A mobile is a type of hanging sculpture. A binary mobile consists of two sides. Each side is a rod of a certain length, from which hangs either a weight or another mobile.

We will represent a binary mobile using the data abstractions below, which use
the `tree`

data abstraction for their representation.

- A
`mobile`

has a left side (index 0) and a right side (index 1). - A
`side`

has a length and a structure, which is either a`mobile`

or`weight`

. - A
`weight`

has a size, which is a positive number.

### Question 5

Implement the `weight`

data abstraction by completing the `weight`

constructor, the `size`

selector, and the `is_weight`

predicate so that a weight is represented using a tree. The `total_weight`

example is provided to demonstrate use of the mobile, side, and weight
abstractions.

```
def mobile(left, right):
"""Construct a mobile from a left side and a right side."""
return tree(None, [left, right])
def sides(m):
"""Select the sides of a mobile."""
return children(m)
```

```
def side(length, mobile_or_weight):
"""Construct a side: a length of rod with a mobile or weight at the end."""
return tree(length, [mobile_or_weight])
def length(s):
"""Select the length of a side."""
return label(s)
def end(s):
"""Select the mobile or weight hanging at the end of a side."""
return children(s)[0]
```

```
def weight(size):
"""Construct a weight of some size."""
assert size > 0
"*** YOUR CODE HERE ***"
def size(w):
"""Select the size of a weight."""
"*** YOUR CODE HERE ***"
def is_weight(w):
"""Whether w is a weight, not a mobile."""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q total_weight`

### Question 6

Implement the `balanced`

function, which returns whether `m`

is a balanced
mobile. A mobile is said to be balanced if the torque applied by its left
side is equal to that applied by its right side (that is, if the length
of the left rod multiplied by the total weight hanging from that rod is equal
to the corresponding product for the right side) and if each of the submobiles
hanging off its sides is balanced.

```
def balanced(m):
"""Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> w = mobile(side(3, t), side(2, u))
>>> balanced(w)
False
>>> balanced(mobile(side(1, v), side(1, w)))
False
>>> balanced(mobile(side(1, w), side(1, v)))
False
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q balanced`

## Simplifying Expressions

### Question 7

In lecture, you saw that one use of trees is in representing expressions
(such as arithmetic expressions). So, for example, the expression
`2 * (3 + x)`

can be represented as the tree

That is, each operand is a child of the operator that applies to it.
In lecture, we looked at evaluating an expression that contains only numbers
and operators. For this problem, we'll work at *simplifying* an expression
that may contain variables without necessarily evaluating it. For example,
`2 * (x + 0) + y * 0`

could be simplified to `2 * x`

.

For this problem, the only operators are `*`

, `+`

, and `-`

(as strings), and
the labels of leaves
will either be numbers or strings containing variable names. Thus, our first
example would be represented with

` tree('*', [tree(2), tree('+', [tree(3), tree('x')])])`

To help you, we've defined a few useful things that may come in handy:

```
# Alternative names of parts of an expression tree.
def left_opnd(expr):
return children(expr)[0]
def right_opnd(expr):
return children(expr)[1]
def oper(expr):
return label(expr)
# Useful constants:
ZERO = tree('0')
ONE = tree('1')
def same_expr(expr0, expr1):
"""Return true iff expression trees EXPR0 and EXPR1 are identical."""
if oper(expr0) != oper(expr1):
return False
elif is_leaf(expr0):
return True
else:
return same_expr(left_opnd(expr0), left_opnd(expr1)) and \
same_expr(right_opnd(expr0), right_opnd(expr1))
def postfix_to_expr(postfix_expr):
"""Return an expression tree equivalent to POSTFIX_EXPR, a string
in postfix ("reverse Polish") notation. In postfix, one writes
E1 OP E2 (where E1 and E2 are expressions and OP is an operator) as
E1' E2' OP, where E1' and E2' are the postfix versions of E1 and E2. For
example, '2*(3+x)' is written '2 3 x + *' and '2*3+x' is `2 3 * x +'.
>>> print_tree(postfix_to_expr("2 3 x + *"))
*
2
+
3
x
"""
def expr_to_infix(expr):
"""A string containing a standard infix denotation of the expression
tree EXPR"""
```

Implement the function `simplify`

on these trees. Given an expression tree
`expr`

, this function returns a new expression tree, simplified from `expr`

by
applying the following rules:

- the expressions
`E * 0`

and`0 * E`

, where`E`

here can be any expression tree, are replaced by`0`

. - the expressions
`E * 1`

and`1 * E`

are replaced by`E`

. - the expressions
`E + 0`

,`0 + E`

, and`E - 0`

are replaced by`E`

. - the expression
`E - E`

(where the two operands are identical trees) is replaced by`0`

.

These simplifications may cause a cascade, as in `y * (x - (0 + x))`

which
simplifies to `y * (x - x)`

, then to `y * 0`

, and then to `0`

. In order for
that to work, you must be careful to simplify operands *before* simplifying the
whole expression.

```
def simplify(expr):
"""EXPR must be an expression tree involving the operators
'+', '*', and '-' in inner nodes; numbers and strings (standing for
variable names) in leaves. Returns an equivalent, simplified version
of EXPR.
>>> def simp(postfix_expr):
... return expr_to_infix(simplify(postfix_to_expr(postfix_expr)))
>>> simp("x y + 0 *")
'0'
>>> simp("0 x y + *")
'0'
>>> simp("x y + 0 +")
'(x + y)'
>>> simp("0 x y + +")
'(x + y)'
>>> simp("x y + 1 *")
'(x + y)'
>>> simp("1 x y + *")
'(x + y)'
>>> simp("x y + x y + -")
'0'
>>> simp("x y y - + x - a b * *")
'0'
>>> simp("x y 3 * -")
'(x - (y * 3))'
>>> simp("x y 0 + 3 * -")
'(x - (y * 3))'
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q simplify`

## Extra questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Question 8

The well-known *Eight Queens Problem* is to place eight chess queens
on an 8x8 chessboard in such a way that none of them attack any of the
others. Queens in chess can move (and attack) any number of squares
horizontally, vertically, or diagonally. Your problem is to complete
the `place_queens`

function to find such a configuration of N queens
for a board of any size NxN (if the configuration exists). This function
returns a list containing, for each row, the position of the queen in
that row (the conditions of the problem guarantee that there must be
one queen in each row), or `None`

if no such configuration exists.

```
def place_queens(size):
"""Return a list. p, of length SIZE in which p[r] is the column in
which to place a queen in row r (0 <= r < SIZE) such that no two
queens are attacking each other. Return None if there is no such
configuration.
>>> place_queens(2) == None
True
>>> place_queens(3) == None
True
>>> check_board(4, place_queens(4))
True
>>> check_board(8, place_queens(8))
True
>>> check_board(14, place_queens(14))
True
"""
"*** YOUR CODE HERE ***"
def check_board(n, cols):
"""Check that COLS is a valid solution to the N-queens problem
(N == len(COLS)). COLS has the format returned by place_queens."""
if cols is None:
return False
if n != len(cols):
return False
if set(cols) != set(range(n)):
return False
if n != len(set([ r + c for r, c in enumerate(cols) ])):
return False
if n != len(set([ r - c for r, c in enumerate(cols) ])):
return False
return True
def print_board(cols):
"""Print a board, COLS, returned by place_queens (as a list of column
positions of queens for each row)."""
if cols is None:
print("No solution")
else:
for c in cols:
print("- " * c + "Q " + "- " * (len(cols) - c - 1))
"""Example:
> print_board(place_queens(5))
Q - - - -
- - Q - -
- - - - Q
- Q - - -
- - - Q -
"""
```

Use OK to test your code:

`python3 ok -q place_queens`