# Lab 06: Midterm 1 Redo

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.

## What Would Python Output?

### Question 1

Note: You do not have to submit anything for this part.

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

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

## Here We Go Again

### Question 2

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):
"""
>>> wheres_waldo(lst)
2
'Nowhere'
"""
if "CONDITION":
return "RESULT"
elif "CONDITION":
return "RESULT"
if "CONDITION":
return "RESULT"
return "RESULT"``````
``````def wheres_waldo(linked_list):
return 'Nowhere'
return 0
if found_him == 'Nowhere':
return found_him
return 1 + found_him``````

## Piled Higher and Deeper

### Question 3

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

### Question 4

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

## Recursion on Trees

### Question 5

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

## Newton's Method

### Question 6

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