Discussion 06 Guide
2.3: Question 1 • Question 2 • Question 3
2.4: Question 1
Section 2.3 Question 1
Write a function that rotates the elements of a list to the right by k. Elements
should not ”fall off”; they should wrap around the beginning of the list.
rotate should return a new list. To make a list of n 0’s, you can do this:
[0] * n
def rotate(lst, k):
""" Return a new list, with the same elements
of lst, rotated to the right k.
>>> x = [1, 2, 3, 4, 5]
>>> rotate(x, 3)
[3, 4, 5, 1, 2]
"""
First, we should define what one rotation is. We are rotating to the right, so
the last element of a list becomes the first element of our new, rotated list,
and the first len(lst)-1 elements gets pushed over 1 space to the right.
Rotating the lst [1, 2, 3, 4, 5] once gives you [5, 1, 2, 3, 4].
Solving with a loop
Since we need to make k rotations, and we know how to make one rotation, we
can use a while loop like this:
rotation_num = 0
while rotation_num < k:
# TODO: rotate the list once
rotation_num += 1
return lst
Now, let’s write the code that actually rotates the list once. Here’s what we know:
- The last element of the list becomes the first
- The first
len(lst) - 1elements of the list shift their index by+1. - We need to make a new list
This leads me to this solution:
new_lst = 0 * len(lst)
new_lst[0] = lst[lst(len(lst) - 1)]
for i in range(1, len(new_lst)):
new_lst[i] = lst[i - 1]
lst = new_lst # For the next rotation
Putting it together:
def rotate(lst, k):
rotation_num = 0
while rotation_num < k:
new_lst = 0 * len(lst)
new_lst[0] = lst[lst(len(lst) - 1)]
for i in range(1, len(new_lst)):
new_lst[i] = lst[i - 1]
lst = new_lst
rotation_num += 1
return lst
You can also do this with list slicing:
lst = lst[:len(lst) - 1] + lst[:len(lst) - 1]
Solving with Clever List Slicing
def rotate(lst, k):
return lst[len(lst) - k:] + lst[:len(lst) - k)] # The 0 is implied
What if the k > len(lst)? We use % (modulus).
def rotate(lst, k):
return lst[(len(lst) - k) % len(lst):] + lst[:(len(lst) - k)) % len(lst)]
Section 2.3 Question 2
Define a function foo that takes in a list lst and returns a new list that keeps only the even-indexed elements of lst and multiplies each of those elements by the corresponding index.
def foo(lst):
"""
>>> x = [1, 2, 3, 4, 5, 6]
>>> >>> foo(x)
[0, 6, 20]
"""
return [_________________________________________________]
This can be done with a for loop or a list comprehension. Let’s do it with a
for loop first:
new_lst = []
for i in range(len(lst)):
if i % 2 == 0:
new_lst.append(lst[i] + i)
return new_lst
As a list comprehension:
return [lst[i] + i for i in range(len(lst)) if i % 2 == 0]
Section 2.3 Question 3
Implement the functions max product, which takes in a list and returns the maximum product that can be formed using nonconsecutive elements of the list. The input list will contain only numbers greater than or equal to 1.
def max_product(lst):
"""Return the maximum product that can be formed using lst
without using any consecutive numbers
>>> [10,3,1,9,2] # 10 * 9
90
"""
This one is quite tough. The crucial part of this problem is that the product
can be made up of more that two numbers. In the doctest above, it just so
happens that 10 * 9 > 10 * 1 * 2.
Finding the Base Case
So, the base case for this one isn’ super obvious, but let’s consider this cases:
- A list of length 1.
- The max_product is just the element in that list (
lst[0]).
- The max_product is just the element in that list (
Reduction
If a list is more than length 1, then we can reduce it down to length 1 by slicing.
Extra Work
We are finding the product of non-consecutive numbers in a list, which means
if you are given a list [1, 2, 3, 4, 5], your options are currently 1 * 3,
1 * 4, or 1 * 5. We want the case that yields maximum product, so one
recursive call we make will be:
lst[0] * max(max_product(lst[2:]))
This gives us a new base case (if lst[2:] returns []):
- A list of length 0.
- We just want to return 1, since
1 * x = x.
- We just want to return 1, since
The second recursive call we make will be if we do not use the first number in the list:
max_product(lst[1:])
And of course, we want the best out of those two recursive calls:
max(lst[0] * max(max_product(lst[2:])), max_product(lst[1:]))
Putting it Together
if lst == []:
return 1
elif len(lst) == 1:
return lst[0]
return max(lst[0] * max(max_product(lst[2:])), max_product(lst[1:]))
Section 2.4 Question 1
An expression tree is a tree that contains a function for each non-leaf root,
which can be either '+' or '*'. All leaves are numbers. Implement eval
tree, which evaluates an expression tree to its value. You may want to use the
functions sum and prod, which take a list of numbers and compute the sum
and product respectively.
def eval_tree(tree):
"""Evaluates an expression tree with functions as root
>>> eval_tree(tree(1))
1
>>> expr = tree('*', [tree(2), tree(3)])
>>> eval_tree(expr)
6
>>> eval_tree(tree('+', [expr, tree(4)]))
10
"""
So first, let’s look at what an simple expression tree looks like:
*
/ \
2 3
The expression tree above represents 2 * 3. Now let’s look at a more complex
one:
*
/ \
+ +
/ \ / \
2 3 1 2
This one represents (2 + 3) * (1 + 2)**. Now you should see how this is a tree,
and as a result, recursive.
Finding our Base Case
Question: What tree do we have to do absolutely no work on?
Answer: A leaf (number)! The tree 2 evaluates to the number 2.
if is_leaf(tree):
return entry(tree)
Reduction
Like many tree problems, the reduction is simply exploring the children of
tree, which are subtrees.
for c in children(tree):
return eval_tree(c)
Extra Work
We have two possible cases if our tree is not a leaf: entry(tree) is either
'*' or '+'. What we do for either case is obvious (we either sum or
prod its children. The tricky part, however, is that we need to know what
the children actually evaluate to (in the case of the complex expression tree
above). That is where our “reduction” comes into play.
evaluated_children = [eval_tree(c) for c in children(tree)]
if entry(tree) == '*':
return prod(evaluated_children)
elif entry(tree) == '+':
return sum(evaluated_children)
Putting it Together
def eval_tree(c):
if is_leaf(tree):
return entry(tree)
evaluated_children = [eval_tree(c) for c in children(tree)]
if entry(tree) == '*':
return prod(evaluated_children)
if entry(tree) == '+':
return sum(evaluated_children)