Due by 11:59pm on Wednesday, November 5

Instructions

Download hw08.zip. Inside the archive, you will find a file called hw08.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 2.9.1

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 6 points.

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

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

Use Ok to test your code:

python3 ok -q store_digits
Copy
✂️

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

Use Ok to test your code:

python3 ok -q deep_map_mut
Copy
✂️

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

Use Ok to test your code:

python3 ok -q crispr_gene_insertion
Copy
✂️

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 __________________

Use Ok to test your code:

python3 ok -q transcribe
Copy
✂️

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.