- What Would Python Output?
- Here We Go Again
- Piled Higher and Deeper
- Recursion on Trees
- Newton's Method

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 n^{th} 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 n^{th} 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 n^{th} 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: x^{2} = 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)`