# 61A Homework 3

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.

### Question 1

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

### Question 2

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.

< 3 'foo' 6 6 >
>>> starts_with(x, empty)
True
True
False
>>> starts_with(x, x)
True
False
"""

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
< 'A' 'G' 'T' 'T' 'G' 'C' >
>>> has_sublist(x, empty)
True
False
False
True
True
False
"""

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'.
< 'C' 'A' 'T' 'G' 'C' 'A' 'T' >
>>> has_jhh_gene(dna)
False
< 'G' 'T' 'A' 'C' 'A' 'T' 'C' 'A' 'T' 'G' >
>>> has_jhh_gene(dna)
True
"""
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).

### Question 3

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.

< 50 25 10 5 1 >
>>> count_change(7, denominations)
2
>>> count_change(100, denominations)
292
< 16 8 4 2 1 >
>>> count_change(7, denominations)
6
>>> count_change(10, denominations)
14
>>> count_change(20, denominations)
60
"""

### Question 4

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

def move_disk(start, end):
print("Move 1 disk from rod", start, "to rod", end)``````

### Question 5: Challenge Problem (optional)

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