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