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 amobile
orweight
. - 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
and0 * E
, whereE
here can be any expression tree, are replaced by0
. - the expressions
E * 1
and1 * E
are replaced byE
. - the expressions
E + 0
,0 + E
, andE - 0
are replaced byE
. - the expression
E - E
(where the two operands are identical trees) is replaced by0
.
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