Homework 6: Object Oriented Programming, Linked Lists

Due by 11:59pm on Thursday, March 16


Download hw06.zip. Inside the archive, you will find a file called hw06.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. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 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.

YouTube link


Q1: Mint

A mint is a place where coins are made. In this question, you'll implement a Mint class that can output a Coin with the correct year and worth.

  • Each Mint instance has a year stamp. The update method sets the year stamp of the instance to the present_year class attribute of the Mint class.
  • The create method takes a subclass of Coin (not an instance!), then creates and returns an instance of that class stamped with the mint's year (which may be different from Mint.present_year if it has not been updated.)
  • A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the present_year class attribute of the Mint class.
class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.present_year.

    >>> mint = Mint()
    >>> mint.year
    >>> dime = mint.create(Dime)
    >>> dime.year
    >>> Mint.present_year = 2102  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    >>> mint.update()   # The mint's year is updated to 2102
    >>> Mint.present_year = 2177     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    present_year = 2022

    def __init__(self):

    def create(self, coin):
        "*** YOUR CODE HERE ***"

    def update(self):
        "*** YOUR CODE HERE ***"

class Coin:
    cents = None # will be provided by subclasses, but not by Coin itself

    def __init__(self, year):
        self.year = year

    def worth(self):
        "*** YOUR CODE HERE ***"

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

Use Ok to test your code:

python3 ok -q Mint

Q2: Vending Machine

In this question you'll create a vending machine that only outputs a single product and provides change when needed.

Create a class called VendingMachine that represents a vending machine for some product. A VendingMachine object returns strings describing its interactions. Remember to match exactly the strings in the doctests -- including punctuation and spacing!

Fill in the VendingMachine class, adding attributes and methods as appropriate, such that its behavior matches the following doctests:

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Nothing left to vend. Please restock.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'Please add $10 more funds.'
    >>> v.add_funds(7)
    'Current balance: $7'
    >>> v.vend()
    'Please add $3 more funds.'
    >>> v.add_funds(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.add_funds(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'

    >>> w = VendingMachine('soda', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.add_funds(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    "*** YOUR CODE HERE ***"

You may find Python's formatted string literals, or f-strings useful. A quick example:

>>> feeling = 'love'
>>> course = '61A!'
>>> f'I {feeling} {course}'
'I love 61A!'

Use Ok to test your code:

python3 ok -q VendingMachine

If you're curious about alternate methods of string formatting, you can also check out an older method of Python string formatting. A quick example:

>>> ten, twenty, thirty = 10, 'twenty', [30]
>>> '{0} plus {1} is {2}'.format(ten, twenty, thirty)
'10 plus twenty is [30]'


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 causes the probability to never be 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!

Q3: 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 two additional things to keep in mind:

  • In the debate method, you should call the provided random function, which returns a random float between 0 and 1. 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')
    >>> p2 = Player('Don')
    >>> p1.popularity
    >>> p1.debate(p2)  # random() should return 0.0
    >>> p1.popularity
    >>> p2.popularity
    >>> p2.votes
    >>> p2.speech(p1)
    >>> p2.votes
    >>> p2.popularity
    >>> p1.popularity

    def __init__(self, name):
        self.name = name
        self.votes = 0
        self.popularity = 100

    def debate(self, other):
        "*** YOUR CODE HERE ***"

    def speech(self, other):
        "*** YOUR CODE HERE ***"

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

Use Ok to test your code:

python3 ok -q Player

Q4: 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:
    >>> p1, p2 = Player('Hill'), Player('Don')
    >>> g = Game(p1, p2)
    >>> winner = g.play()
    >>> p1 is winner

    def __init__(self, player1, player2):
        self.p1 = player1
        self.p2 = player2
        self.turn = 0

    def play(self):
        while not self.game_over():
            "*** YOUR CODE HERE ***"
        return self.winner()

    def game_over(self):
        return max(self.p1.votes, self.p2.votes) >= 50 or self.turn >= 10

    def winner(self):
        "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q Game

Q5: 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'), Player('Hill')
    >>> g = Game(p1, p2)
    >>> winner = g.play()
    >>> p1 is winner

    def choose(self, other):
        "*** YOUR CODE HERE ***"

class CautiousPlayer(Player):
    >>> random = make_test_random()
    >>> p1, p2 = CautiousPlayer('Hill'), AggressivePlayer('Don')
    >>> p1.popularity = 0
    >>> p1.choose(p2) == p1.debate
    >>> p1.popularity = 1
    >>> p1.choose(p2) == p1.debate

    def choose(self, other):
        "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q AggressivePlayer
python3 ok -q CautiousPlayer


Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Optional Questions

Q6: Next Virahanka Fibonacci Object

Implement the next method of the VirFib class. For this class, the value attribute is a Fibonacci number. The next method returns a VirFib instance whose value is the next Fibonacci number. The next method should take only constant time.

Note that in the doctests, nothing is being printed out. Rather, each call to .next() returns a VirFib instance. The way each VirFib instance is displayed is determined by the return value of its __repr__ method.

Hint: Keep track of the previous number by setting a new instance attribute inside next. You can create new instance attributes for objects at any point, even outside the __init__ method.

class VirFib():
    """A Virahanka Fibonacci number.

    >>> start = VirFib()
    >>> start
    VirFib object, value 0
    >>> start.next()
    VirFib object, value 1
    >>> start.next().next()
    VirFib object, value 1
    >>> start.next().next().next()
    VirFib object, value 2
    >>> start.next().next().next().next()
    VirFib object, value 3
    >>> start.next().next().next().next().next()
    VirFib object, value 5
    >>> start.next().next().next().next().next().next()
    VirFib object, value 8
    >>> start.next().next().next().next().next().next() # Ensure start isn't changed
    VirFib object, value 8

    def __init__(self, value=0):
        self.value = value

    def next(self):
        "*** YOUR CODE HERE ***"

    def __repr__(self):
        return "VirFib object, value " + str(self.value)

Use Ok to test your code:

python3 ok -q VirFib

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