Homework 8 Solutions

hw08.zip

Solution Files

You can find the solutions in hw08.py.

Midsemester Feedback Survey

Please fill out the mid-semester feedback form. If 75% of the class completes this form by Monday July 28th at 11:59 PM, everyone will receive 1 point of extra credit! If this goal is not met, nobody will receive the extra point.

Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Linked Lists

Q1: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list containing the digits of n in the same order (from left to right).

Important: Do not use any string manipulation functions, such as str or reversed.

def store_digits(n: int):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> store_digits(2450)
    Link(2, Link(4, Link(5, Link(0))))
    >>> store_digits(20105)
    Link(2, Link(0, Link(1, Link(0, Link(5)))))
    >>> # a check for restricted functions
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    """
    result = Link.empty
    while n > 0:
        result = Link(n % 10, result)
        n //= 10
    return result

Use Ok to test your code:

python3 ok -q store_digits

Q2: Mutable Mapping

Implement deep_map_mut(func, s), which applies the function func to each element in the linked list s. If an element is itself a linked list, recursively apply func to its elements as well.

Your implementation should mutate the original linked list. Do not create any new linked lists. The function returns None.

Hint: You can use the built-in isinstance function to determine if an element is a linked list.
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False

Construct Check: The final test case for this problem checks that your function does not create any new linked lists. If you are failing this doctest, make sure that you are not creating link lists by calling the constructor, i.e.
s = Link(1)

def deep_map_mut(func, s: Link) -> None:
    """Mutates a deep link s by replacing each item found with the
    result of calling func on the item. Does NOT create new Links (so
    no use of Link's constructor).

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> square = lambda x: x * x
    >>> print(link1)
    (3 (4) 5 6)
    >>> link2 = Link(1, Link(Link(Link(2, Link(3))), Link(4)))
    >>> double = lambda x: x * 2
    >>> print(link2)
    (1 ((2 3)) 4)
    >>> # Disallow the use of making new Links before calling deep_map_mut
    >>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
    >>> try:
    ...     deep_map_mut(square, link1)
    ...     deep_map_mut(double, link2)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    (9 (16) 25 36)
    >>> print(link2)
    (2 ((4 6)) 8)
    """
    if s is Link.empty:
        return None
    elif isinstance(s.first, Link):
        deep_map_mut(func, s.first)
    else:
        s.first = func(s.first)
    deep_map_mut(func, s.rest)

Use Ok to test your code:

python3 ok -q deep_map_mut

Q3: Dr. Doudna's CRISPR Links

To simulate experiments with her recently discovered CRISPR Cas-9 technique, Nobel Laureate and UC Berkeley Professor Dr. Jennifer Doudna wishes to create a computational template for CRISPR insertions into certain genes. For this, she has approached the Data C88C students and staff for help in constructing a mechanism to enable these simulations. She has offered to provide a bank of test genes as well as the DNA sequence she wishes to insert into those genes.

Part A Write a function crispr_gene_insertion that takes in a string insert, a single codon sequence of 3 characters, and a nested linked list lnk_of_genes, containing a linked list of genes. Each gene is itself a linked list containing a sequence of codons which are strings of 3 characters that represent DNA units.

Add the insert codon exactly i + 1 times after the start codon ("AUG") in each gene, where i refers to the index of the gene in the linked list lnk_of_genes (NOT the index of the start codon within a particular gene).

Definitions:

Codon: a string of 3 characters (triplet), made from A, T, G, or C, that represent DNA units (e.g. "ACG", "GTT")
Gene: a sequence of codons
Start codon: "AUG"

def crispr_gene_insertion(lnk_of_genes, insert):
    """Takes a linked list of genes and mutates the genes
    with the INSERT codon added the correct number of times.

    >>> link = Link(Link("AUG", Link("GCC", Link("ACG"))), Link(Link("ATG", Link("AUG", Link("ACG", Link("GCC"))))))
    >>> print(link)
    ((AUG GCC ACG) (ATG AUG ACG GCC))
    >>> crispr_gene_insertion(link, "TTA")
    >>> print(link)
    ((AUG TTA GCC ACG) (ATG AUG TTA TTA ACG GCC))
    >>> link = Link(Link("ATG"), Link(Link("AUG", Link("AUG")), Link(Link("AUG", Link("GCC")))))
    >>> print(link)
    ((ATG) (AUG AUG) (AUG GCC))
    >>> # first gene has no AUG so unchanged, 2nd gene has 2 AUGs but only first considered for insertion
    >>> crispr_gene_insertion(link, "TTA")
    >>> print(link)
    ((ATG) (AUG TTA TTA AUG) (AUG TTA TTA TTA GCC))
    >>> link = Link.empty # empty linked list of genes stays empty
    >>> crispr_gene_insertion(link, "TTA")
    >>> print(link)
    ()
    """
    def gene_inserter(gene, index, flag):
        if gene is Link.empty or index == 0:
            return gene
        if flag:
            return Link(insert, gene_inserter(gene, index - 1, flag))
        if gene.first == "AUG":
            return Link(gene.first, gene_inserter(gene.rest, index, True))
        else:
            return Link(gene.first, gene_inserter(gene.rest,index, flag))
    index = 0
    while lnk_of_genes is not Link.empty:
        lnk_of_genes.first = gene_inserter(lnk_of_genes.first, index + 1, False)
        lnk_of_genes = lnk_of_genes.rest
        index += 1

    # ALTERNATE SOLUTION
    def crispr_gene_insertion(lnk_of_genes, insert):
        def helper(lnk, index):
            if lnk is Link.empty:
                return
            curr = lnk.first
            while curr is not Link.empty and curr.first != "AUG":
                curr = curr.rest
            if curr is not Link.empty:
                for i in range(index + 1):
                    curr.rest = Link(insert, curr.rest)
            helper(lnk.rest, index + 1)
        helper(lnk_of_genes, 0)

Use Ok to test your code:

python3 ok -q crispr_gene_insertion

Part B Now that Dr. Doudna has got her CRISPR-edited genes, she wants to convert the DNA sequences into RNA triplets. Transcribing involves converting DNA to RNA. Write a function transcribe that takes in a string dna, and returns a new Python list representing the RNA codons (triplets) sequence obtained by transcribing the DNA sequence. Assume that the length of dna is always a multiple of 3.

Additionally, you have a dictionary mapping that maps DNA bases to their corresponding RNA bases for transcription. This is already added to your function. mapping = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}

See the doctests for examples.

Note: It may be helpful to use the range(start, stop, step) function — E.g. list(range(1, 10, 2)) creates the list [1, 3, 5, 7, 9]

def transcribe(dna):
    """Takes a string of DNA and returns a Python list with the RNA codons.

    >>> transcribe("ATG")
    ['UAC']
    >>> transcribe("TACCTAGCCCATAAA")
    ['AUG', 'GAU', 'CGG', 'GUA', 'UUU']
    >>> transcribe("CCCGGTATTCAT")
    ['GGG', 'CCA', 'UAA', 'GUA']
    """
    assert len(dna) % 3 == 0, 'Assume `dna` is always a multiple of 3'
    mapping = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}
    return [mapping[dna[i]] + mapping[dna[i + 1]] + mapping[dna[i + 2]] for i in range(0, len(dna), 3)]

Use Ok to test your code:

python3 ok -q transcribe

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.