# Homework 5: Inheritance, Mutable Trees, Linked Lists hw05.zip

Due by 11:59pm on Wednesday, July 24

## Instructions

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

Submission: When you are done, submit the assignment by uploading all code files you've edited 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:

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

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

## Inheritance

### Election

Let's implement a game called Election. In this game, two players compete to try and earn the most votes. Both players start with 0 votes and 100 popularity.

The two players alternate turns, and the first player starts. Each turn, the current player chooses an action. There are two types of actions:

• The player can debate, and either gain or lose 50 popularity. If the player has popularity `p1` and the other player has popularity `p2`, then the probability that the player gains 50 popularity is `max(0.1, p1 / (p1 + p2))` Note that the `max` here ensures that the probability is never lower than 0.1.
• The player can give a speech. If the player has popularity `p1` and the other player has popularity `p2`, then the player gains `p1 // 10` votes and popularity and the other player loses `p2 // 10` popularity.

The game ends when a player reaches 50 votes, or after a total of 10 turns have been played (each player has taken 5 turns). Whoever has more votes at the end of the game is the winner!

### Q1: Player

First, let's implement the `Player` class. Fill in the `debate` and `speech` methods, that take in another `Player` `other`, and implement the correct behavior as detailed above. Here are a few additional things to keep in mind:

• Each player carries a random number generator (the `random_func` instance attribute), which is a function that returns a random float between 0 and 1 when called.
• In the `debate` method, you should call the `random_func` function to get a random number. The player should gain 50 popularity if the random number is smaller than the probability described above, and lose 50 popularity otherwise.
• Neither players' popularity should ever become negative. If this happens, set it equal to 0 instead.
``````### Phase 1: The Player Class
class Player:
"""
>>> random = make_test_random()
>>> p1 = Player('Hill', random)
>>> p2 = Player('Don', random)
>>> p1.popularity
100
>>> p1.debate(p2)  # random() should return 0.0
>>> p1.popularity
150
>>> p2.popularity
100
0
>>> p2.speech(p1)
10
>>> p2.popularity
110
>>> p1.popularity
135
>>> p1.speech(p2)
13
>>> p1.popularity
148
10
>>> p2.popularity
99
>>> for _ in range(4):  # 0.1, 0.2, 0.3, 0.4
...     p1.debate(p2)
>>> p2.debate(p1)
>>> p2.popularity
49
>>> p2.debate(p1)
>>> p2.popularity
0
"""
def __init__(self, name, random_func):
self.name = name
self.popularity = 100
self.random_func = random_func

def debate(self, other):

def speech(self, other):

def choose(self, other):
return self.speech``````

Use Ok to test your code:

``python3 ok -q Player``

### Q2: Game

Now, implement the `Game` class. Fill in the `play` method, which should alternate between the two players, starting with `p1`, and have each player take one turn at a time. The `choose` method in the `Player` class returns the method, either `debate` or `speech`, that should be called to perform the action.

In addition, fill in the `winner` method, which should return the player with more votes, or `None` if the players are tied.

``````### Phase 2: The Game Class
class Game:
"""
>>> random = make_test_random()
>>> p1, p2 = Player('Hill',random), Player('Don', random)
>>> g = Game(p1, p2)
>>> winner = g.play()
>>> p1 is winner
True
>>> winner is g.winner()
True
>>> g.turn
10
>>> print(g.winner())
None
"""
def __init__(self, player1, player2):
self.p1 = player1
self.p2 = player2
self.turn = 0

def play(self):
while not self.game_over():
return self.winner()

def game_over(self):

def winner(self):
``````

Use Ok to test your code:

``python3 ok -q Game``

### Q3: New Players

The `choose` method in the `Player` class is boring, because it always returns the `speech` method. Let's implement two new classes that inherit from `Player`, but have more interesting `choose` methods.

Implement the `choose` method in the `AggressivePlayer` class, which returns the `debate` method if the player's popularity is less than or equal to `other`'s popularity, and `speech` otherwise. Also implement the `choose` method in the `CautiousPlayer` class, which returns the `debate` method if the player's popularity is 0, and `speech` otherwise.

``````### Phase 3: New Players
class AggressivePlayer(Player):
"""
>>> random = make_test_random()
>>> p1, p2 = AggressivePlayer('Don', random), Player('Hill', random)
>>> g = Game(p1, p2)
>>> winner = g.play()
>>> p1 is winner
True
>>> p1.popularity = p2.popularity
>>> p1.choose(p2) == p1.debate
True
>>> p1.popularity += 1
>>> p1.choose(p2) == p1.debate
False
>>> p2.choose(p1) == p2.speech
True
"""
def choose(self, other):
``````

Use Ok to test your code:

``python3 ok -q AggressivePlayer``

``````class CautiousPlayer(Player):
"""
>>> random = make_test_random()
>>> p1, p2 = CautiousPlayer('Hill', random), AggressivePlayer('Don', random)
>>> p1.popularity = 0
>>> p1.choose(p2) == p1.debate
True
>>> p1.popularity = 1
>>> p1.choose(p2) == p1.debate
False
>>> p2.choose(p1) == p2.speech
True
"""
def choose(self, other):
``````

Use Ok to test your code:

``python3 ok -q CautiousPlayer``

## Mutable Trees

Implement `add_d_leaves`, a function that takes in a `Tree` instance `t` and a number `v`.

We define the depth of a node in `t` to be the number of edges from the root to that node. The depth of root is therefore 0.

For each node in the tree, you should add `d` leaves to it, where `d` is the depth of the node. Every added leaf should have a label of `v`. If the node at this depth has existing branches, you should add these leaves to the end of that list of branches.

For example, you should be adding 1 leaf with label `v` to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Here is an example of a tree `t`(shown on the left) and the result after `add_d_leaves` is applied with `v` as 5.

Hint: Use a helper function to keep track of the depth!

Take a look at the doctests below and try drawing out the second doctest to visualize how the function is mutating `t3`.

``````def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.

>>> t_one_to_four = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> print(t_one_to_four)
1
2
3
4
>>> print(t_one_to_four)
1
2
5
3
4
5
5
5

>>> t0 = Tree(9)
>>> t0
Tree(9)
>>> t1 = Tree(1, [Tree(3)])
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> print(t3)
3
1
3
4
0
2
5
6
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
``````

Use Ok to test your code:

``python3 ok -q add_d_leaves``

As a reminder, the depth of a node is defined as the number of edges from the root to the node. Therefore, the root itself has a depth of 0 since there are no edges between the root and itself.

Given a tree `t` and a linked list of one-argument functions `funcs`, write a function that mutates the labels of `t` using the functions from `funcs` at the corresponding depths. For example:

• The label at the root node (depth 0) will be mutated using the function at depth 0 of `funcs` (`funcs.first`).
• The label at the first level of the tree will be mutated using the function at depth 1 of `funcs` (`funcs.rest.first`), and so on.

Each function in `funcs` takes in a label value and returns a valid label value.

If a node is a leaf and there are remaining functions in `funcs`, all of these remaining functions should be applied in order to the label of the leaf node. If `funcs` is empty, the tree should remain unmodified.

Please refer to the doctests for examples.

``````def level_mutation_link(t, funcs):
"""Mutates t using the functions in the linked list funcs.

>>> t = Tree(1, [Tree(2, [Tree(3)])])
>>> funcs = Link(lambda x: x + 1, Link(lambda y: y * 5, Link(lambda z: z ** 2)))
>>> t    # At level 0, apply x + 1; at level 1, apply y * 5; at level 2 (leaf), apply z ** 2
Tree(2, [Tree(10, [Tree(9)])])
>>> t2 = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> t2    # Level 0: 1+1=2; Level 1: 2*5=10 => 10**2 = 100, 3*5=15; Level 2 (leaf): 4**2=16
Tree(2, [Tree(100), Tree(15, [Tree(16)])])
>>> t3 = Tree(1, [Tree(2)])
>>> t3    # Level 0: 1+1=2; Level 1: 2*5=10; no further levels, so apply remaining z ** 2: 10**2=100
Tree(2, [Tree(100)])
"""
if _____________________:
return
t.label = _____________________
remaining = _____________________
if __________________ and __________________:
while _____________________:
_____________________
remaining = remaining.rest
for b in t.branches:
_____________________
``````

Use Ok to test your code:

``python3 ok -q level_mutation_link``

### Q6: Store Digits

Write a function `store_digits` that takes in an integer `n` and returns a linked list where each element of the list is a digit of `n`.

Important: Do not use any string manipulation functions like `str` and `reversed`.

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

>>> s = store_digits(1)
>>> s
>>> store_digits(2345)
>>> store_digits(876)
>>> store_digits(2450)
>>> # 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
"""
``````

Use Ok to test your code:

``python3 ok -q store_digits``

### Q7: Mutable Mapping

Implement `deep_map_mut(func, link)`, which applies a function `func` onto all elements in the given linked list `lnk`. If an element is itself a linked list, apply `func` to each of its elements, and so on.

Hint: The built-in `isinstance` function may be useful.

``````>>> s = Link(1, Link(2, Link(3, Link(4))))
True
>>> isinstance(s, int)
False``````

Construct Check: The last doctest of this question ensures that you do not create new linked lists. If you are failing this doctest, ensure that you are not creating link lists by calling the constructor, i.e.

``s = Link(1)``
``````def deep_map_mut(func, lnk):
"""Mutates a deep link lnk by replacing each item found with the
result of calling func on the item. Does NOT create new Links (so

Does not return the modified Link object.

<3 <4> 5 6>
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> try:
...     deep_map_mut(lambda x: x * x, link1)
... finally:
<9 <16> 25 36>
"""
``````

Use Ok to test your code:

``python3 ok -q deep_map_mut``

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.

# Extra Credit (1 pt)

During Office Hours and Project Parties, the staff will prioritize helping students with required questions. We will not be offering help with this question unless the queue is empty.

Note: To get credit for the extra credit question, you must submit to the extra credit assignment on Gradescope. This is separate from the main assignment on Gradescope.

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 61A 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`.

Definitions:

• Codon: a string of 3 characters(triplet), made from A, T, G, 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.

<<AUG GCC ACG> <ATG AUG ACG GCC>>
<<AUG TTA GCC ACG> <ATG AUG TTA TTA ACG GCC>>
<<ATG> <AUG AUG> <AUG GCC>>
>>> crispr_gene_insertion(link, "TTA") # first gene has no AUG so unchanged, 2nd gene has 2 AUGs but only first considered for insertion
<<ATG> <AUG TTA TTA AUG> <AUG TTA TTA TTA GCC>>
()
"""
``````

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 `dict` that maps DNA bases to their corresponding RNA bases for transcription. This is already added to your function. `dict = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}`

Example: if `dna = 'ATG'`:

``````dict['A'] = 'U'
dict['T'] = 'A'
dict['G'] = 'C'
transcribe(dna) = ['UAC']``````

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.

>>> DNA = "TACCTAGCCCATAAA"
>>> transcribe(DNA)
['AUG', 'GAU', 'CGG', 'GUA', 'UUU']
"""
dict = {'A': 'U', 'T': 'A', 'G': 'C', 'C': 'G'}
return __________________
``````

Use Ok to test your code:

``python3 ok -q transcribe``

# Exam Practice

Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!

Object-Oriented Programming

1. Spring 2022 MT2 Q8: CS61A Presents The Game of Hoop.
2. Fall 2020 MT2 Q3: Sparse Lists
3. Fall 2019 MT2 Q7: Version 2.0