*Due by 11:59pm on Saturday, 7/5*

**Readings:** You might find the following references
useful:

**Submission:** See the online submission
instructions. We have provided a hw3.py starter file for the questions
below.

Write a function `has_seven`

that takes a positive integer `n`

and
returns whether `n`

contains the digit 7. *Do not use any assignment
statements - use recursion instead*:

```
def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.
>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
"""
"*** YOUR CODE HERE ***"
```

World-famous mad scientist John Harvey Hilfinger has discovered the gene which causes people to be crazy enough to lecture for CS 61A. Andrew and Rohin (last names hidden due to privacy concerns) are thus far the only two people confirmed to possess the J.H.H. gene.

We believe many more people may be afflicted, but it is very hard to
search for the presence of this J.H.H. gene in a given string of
DNA. You decide to use a `linked_list`

to solve this problem.

Given a DNA sequence (a linked list whose elements are 'A', 'G', 'C' or 'T'), your task is to find the J.H.H. gene, which is the sequence 'CATCAT'. You decide to split this up into separate parts:

First, write a function `starts_with`

that takes two inputs, `lst`

and
`sublst`

, and returns `True`

if `sublst`

is a prefix of `lst`

(that
is, if `lst`

starts with `sublist`

), and `False`

otherwise. Note that
`sublst`

may be larger than `lst`

- in this case you should return
`False`

.

```
def starts_with(lst, sublst):
"""Returns True if sublst is a prefix of lst, False otherwise.
Note that it is possible for sublst to be larger than lst.
>>> x = link(3, link('foo', link(6, link(6, empty))))
>>> print_linked_list(x)
< 3 'foo' 6 6 >
>>> starts_with(x, empty)
True
>>> starts_with(x, link(3, empty))
True
>>> starts_with(x, link(6, empty))
False
>>> starts_with(x, x)
True
>>> starts_with(link(2, empty), link(2, link(3, empty)))
False
"""
"*** YOUR CODE HERE ***"
```

Now, write a function `has_sublist`

that takes two inputs, `lst`

and
`sublst`

, and returns `True`

if `sublst`

is present anywhere in `lst`

,
and `False`

otherwise.

```
def has_sublist(lst, sublst):
"""Returns True if sublst is present anywhere in lst, False otherwise.
>>> has_sublist(empty, empty)
True
>>> x = link('A', link('G', link('T', link('T', link('G', link('C', empty))))))
>>> print_linked_list(x)
< 'A' 'G' 'T' 'T' 'G' 'C' >
>>> has_sublist(x, empty)
True
>>> has_sublist(x, link(2, link(3, empty)))
False
>>> has_sublist(x, link('A', link('T', empty)))
False
>>> has_sublist(x, link('G', link('T', link('T', empty))))
True
>>> has_sublist(link(1, link(2, link(3, empty))), link(2, empty))
True
>>> has_sublist(x, link('A', x))
False
"""
"*** YOUR CODE HERE ***"
```

Finally, we can solve the original problem as follows:

```
def has_jhh_gene(dna_seq):
"""Returns True if dna_seq contains the J.H.H. gene 'CATCAT'.
>>> dna = link('C', link('A', link('T', empty)))
>>> dna = link('C', link('A', link('T', link('G', dna))))
>>> print_linked_list(dna)
< 'C' 'A' 'T' 'G' 'C' 'A' 'T' >
>>> has_jhh_gene(dna)
False
>>> dna = link('T', link('C', link('A', link('T', link('G', empty)))))
>>> dna = link('G', link('T', link('A', link('C', link('A', dna)))))
>>> print_linked_list(dna)
< 'G' 'T' 'A' 'C' 'A' 'T' 'C' 'A' 'T' 'G' >
>>> has_jhh_gene(dna)
True
"""
jhh = link('C', link('A', link('T', link('C', link('A', link('T', empty))))))
return has_sublist(dna_seq, jhh)
```

Note: This is actually a problem of importance. CS 176 goes into more detail on this topic, with smarter algorithms that are faster, and can deal with errors in the DNA (because DNA sequencing is not 100% correct).

A set of coins makes change for `n`

if the sum of the values of the
coins is `n`

. For example, if you have 1-cent, 2-cent and 4-cent
coins, the following sets make change for `7`

:

- 7 1-cent coins
- 5 1-cent, 1 2-cent coins
- 3 1-cent, 2 2-cent coins
- 3 1-cent, 1 4-cent coins
- 1 1-cent, 3 2-cent coins
- 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for `7`

. Write a function
`count_change`

that takes a positive integer `n`

and a linked list of
the coin denominations and returns the number of ways to make change
for `n`

using these coins:

```
def count_change(amount, denominations):
"""Returns the number of ways to make change for amount.
>>> denominations = link(50, link(25, link(10, link(5, link(1, empty)))))
>>> print_linked_list(denominations)
< 50 25 10 5 1 >
>>> count_change(7, denominations)
2
>>> count_change(100, denominations)
292
>>> denominations = link(16, link(8, link(4, link(2, link(1, empty)))))
>>> print_linked_list(denominations)
< 16 8 4 2 1 >
>>> count_change(7, denominations)
6
>>> count_change(10, denominations)
14
>>> count_change(20, denominations)
60
"""
"*** YOUR CODE HERE ***"
```

A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.

Complete the definition of `towers_of_hanoi`

which prints out the steps
to solve this puzzle for any number of `n`

disks starting from the
`start`

rod and moving them to the `end`

rod:

```
def towers_of_hanoi(n, start, end):
"""Print the moves required to solve the towers of hanoi game if we start
with n disks on the start pole and want to move them all to the end pole.
The game is to assumed to have 3 poles (which is traditional).
>>> towers_of_hanoi(1, 1, 3)
Move 1 disk from rod 1 to rod 3
>>> towers_of_hanoi(2, 1, 3)
Move 1 disk from rod 1 to rod 2
Move 1 disk from rod 1 to rod 3
Move 1 disk from rod 2 to rod 3
>>> towers_of_hanoi(3, 1, 3)
Move 1 disk from rod 1 to rod 3
Move 1 disk from rod 1 to rod 2
Move 1 disk from rod 3 to rod 2
Move 1 disk from rod 1 to rod 3
Move 1 disk from rod 2 to rod 1
Move 1 disk from rod 2 to rod 3
Move 1 disk from rod 1 to rod 3
"""
"*** YOUR CODE HERE ***"
def move_disk(start, end):
print("Move 1 disk from rod", start, "to rod", end)
```

The recursive factorial function can be written as a single expression by using a conditional expression.

```
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120
```

However, this implementation relies on the fact (no pun intended) that
`fact`

has a name, to which we refer in the body of `fact`

. To write a
recursive function, we have always given it a name using a `def`

or
assignment statement so that we can refer to the function within its
own body. In this question, your job is to define fact recursively
without giving it a name!

Write an expression that computes `n`

factorial using only call
expressions, conditional expressions, and lambda expressions (no
assignment or def statements). *Note in particular that you are not
allowed to use make_anonymous_factorial in your return expression.*
The

`sub`

and `mul`

functons from the `operator`

module are the only
built-in function required to solve this problem:```
from operator import sub, mul
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
"""
return YOUR_EXPRESSION_HERE
```