By the end of this lab, you should have submitted the
lab06
assignment using the command submit lab06
.
This lab is due by 11:59pm on 07/15/2014.
Here is a lab06.py starter file for this lab.
For lab today, we'll be redoing the coding problems on Midterm 1. This
time, you'll be working together and have an interpreter to check your
answers. In the starter file, replace all capitalized strings (such as
"CONDITION"
or "RESULT"
) with the code you need to fill in.
Include all lines that the interpreter would display. If it would display a function, then write Function. If it would cause an error, write Error. Assume that you have started Python 3 and executed the following:
def welcome():
if a == 0:
return 'hello, welcome to your exam'
return 'prepare for tricks'
def last_night(n):
for i in range(n):
return 'exams'
pi = [3, 1, 4, 1, 5, 9, 2, 6, 5, 4]
cut = lambda thing: thing[2:]
slice_of = lambda thing: thing[2:8:2]
def mystery(x):
if x and (x + 1):
return 'mystery'
return mystery
Assume these commands are entered exactly as written into the interpreter. We have provided this code in the starter file, so you can interactively load it using
python3 -i lab06.py
to test your work.
>>> welcome()
______NameError
>>> last_night(308)
______'exams'
>>> (lambda x, y: x + y(x))(4, lambda y: 5)
______9
>>> [3 for x in range(30) if x > 26]
______[3, 3, 3]
>>> cut(slice_of(pi))
______[2]
>>> cut(mystery(-1)(20))
______'stery'
>>> cut(mystery(20)(-1))
______TypeError
>>> print(mystery(print(20)))
______20
<function mystery>
Define a function wheres_waldo
, which takes in a linked_list
which
may or may not contain the string "Waldo"
as an element, and returns
the index of "Waldo"
if it exists, or "Nowhere"
if it does not. Do
not assume we have get_item
defined! Note that linked_list
is
not a deep linked_list
.
def wheres_waldo(linked_list):
"""
>>> lst = link("Moe", link("Larry", link("Waldo", link("Curly", empty))))
>>> wheres_waldo(lst)
2
>>> wheres_waldo(link(1, link(2, empty)))
'Nowhere'
"""
if "CONDITION":
return "RESULT"
elif "CONDITION":
return "RESULT"
found_him = wheres_waldo(rest(linked_list))
if "CONDITION":
return "RESULT"
return "RESULT"
def wheres_waldo(linked_list):
if linked_list == empty:
return 'Nowhere'
elif first(linked_list) == 'Waldo':
return 0
found_him = wheres_waldo(rest(linked_list))
if found_him == 'Nowhere':
return found_him
return 1 + found_him
Write the function inhexing
, which takes in a Python list of numbers lst
, a function hex
, and an integer n
, and returns a new list where every nth element is replaced by the result of calling hex
on that element.
def inhexing(lst, hex, n):
"""
>>> inhexing([1, 2, 3, 4, 5], lambda x: 'Poof!', 2)
[1, 'Poof!', 3, 'Poof!', 5]
>>> inhexing([2, 3, 4, 5, 6, 7, 8], lambda x: x + 10, 3)
[2, 3, 14, 5, 6, 17, 8]
"""
result = "INITIAL"
for i in range(len(lst)):
if "CONDITION":
"ACTION"
else:
"ACTION"
return "RESULT"
def inhexing(lst, hex, n):
result = []
for i in range(len(lst)):
if (i + 1) % n == 0:
result += [ hex(lst[i]) ]
else:
result += [ lst[i] ]
return result
Now write deep_inhexing
, for deep Python lists. It takes
in a deep Python list, a function, and a number. It returns a new
list where every nth element is replaced by the function applied
to that element. If it encounters a list as an element, it recurses
on the sublist, resetting the counter, even if the sublist was an nth element. Recall you can use the expression type(x) ==
type([])
to test if x
is a Python list. Make sure you read
and understand all the doctests!
def deep_inhexing(lst, hex, n):
"""
>>> deep_inhexing([1, 2, 3, 4, 5, 6], lambda x: x + 10, 3)
[1, 2, 13, 4, 5, 16]
>>> deep_inhexing([1, [[2]], [3, 4, [5]]], lambda x: 'Poof!', 1)
['Poof!', [['Poof!']], ['Poof!', 'Poof!', ['Poof!']]]
>>> deep_inhexing([1, [2], 3], lambda x: 'Poof!', 2)
[1, [2], 3]
>>> deep_inhexing([1, [2, 3], 4, [5, 6]], lambda x: 'Poof!', 2)
[1, [2, 'Poof!'], 4, [5, 'Poof!']]
>>> deep_inhexing([[2, 3], 4, [5, 6], [7]], lambda x: 'Poof!', 2)
[[2, 'Poof!'], 'Poof!', [5, 'Poof!'], [7]]
>>> deep_inhexing([2, [4, [6, [8, 10]]]], lambda x: 'Poof!', 2)
[2, [4, [6, [8, 'Poof!']]]]
"""
def helper(lst, counter):
if "CONDITION":
return "RESULT"
first, rest = lst[0], lst[1:]
if "CONDITION":
return "RESULT"
elif counter % n == 0:
return "RESULT"
else:
return "RESULT"
return helper("ARGUMENT", "ARGUMENT")
def helper(lst, counter):
if lst == []:
return []
first, rest = lst[0], lst[1:]
if type(first) == type([]):
return [helper(first, 1)] + helper(rest, counter + 1)
elif counter % n == 0:
return [hex(first)] + helper(rest, counter + 1)
else:
return [first] + helper(rest, counter + 1)
return helper(lst, 1)
Define a function dejavu
, which takes in a tree of numbers
t
and a number n
. It returns True
if there is a path
from the root to a leaf such that the sum of the numbers along that
path is n
and False
otherwise. Reminder: The constructor
and selectors are tree
, datum
and children
.
def dejavu(t, n):
"""
>>> my_tree = tree(2, [tree(3, [tree(5), tree(7)]), tree(4)])
>>> dejavu(my_tree, 12) # 2 -> 3 -> 7
True
>>> dejavu(my_tree, 5) # Sums of partial paths like 2 -> 3 don't count
False
"""
if children(t) == []:
return "RESULT"
for VARIABLENAME in "SEQUENCE":
if "CONDITION":
return "RESULT"
return False
def dejavu(t, n):
if children(t) == []:
return n == datum(t)
for child in children(t):
if dejavu(child, n - datum(t)):
return True
return False
Show how you would use Newton's method to find the golden ratio by defining the function phi_approx()
. The golden ratio is defined as the positive solution to the equation: x2 = x + 1
def phi_approx():
"""
>>> guess = phi_approx()
>>> close_to_phi(guess)
True
"""
return "FUNCTION"("ARGUMENTS")
Here are the functions available to you, as defined in lecture:
find_zero(f, dx, x=1)
deriv(f)
easy_find_zero(f, x=1)
Check your starter file for reminders on their inputs and outputs.
find_zero(lambda x: x*x - x - 1, lambda x: 2*x - 1)
or
find_zero(lambda x: x*x - x - 1, deriv(lambda x: x*x - x - 1))
or
easy_find_zero(lambda x: x*x - x - 1)