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.

Table of Contents

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
    """
    "*** YOUR CODE HERE ***"

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.

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

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:

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

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.

Towers of Hanoi

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)

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