Lab 7: Object-Oriented Programming, Linked Lists, Mutable Trees
Due by 11:59pm on Tuesday, March 9.
Starter Files
Download lab07.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Object-Oriented Programming
Minilecture Video: OOP
Object-oriented programming (OOP) is a style of programming that
allows you to think of code in terms of "objects." Here's an example of
a Car
class:
class Car:
num_wheels = 4
def __init__(self, color):
self.wheels = Car.num_wheels
self.color = color
def drive(self):
if self.wheels <= Car.num_wheels:
return self.color + ' car cannot drive!'
return self.color + ' car goes vroom!'
def pop_tire(self):
if self.wheels > 0:
self.wheels -= 1
Here's some terminology:
- class: a blueprint for how to build a certain type of object.
The
Car
class (shown above) describes the behavior and data that allCar
objects have. instance: a particular occurrence of a class. In Python, we create instances of a class like this:
>>> my_car = Car('red')
my_car
is an instance of theCar
class.data attributes: a variable that belongs to the instance (also called instance variables). Think of a data attribute as a quality of the object: cars have wheels and color, so we have given our
Car
instanceself.wheels
andself.color
attributes. We can access attributes using dot notation:>>> my_car.color 'red' >>> my_car.wheels 4
method: Methods are just like normal functions, except that they are bound to an instance. Think of a method as a "verb" of the class: cars can drive and also pop their tires, so we have given our
Car
instance the methodsdrive
andpop_tire
. We call methods using dot notation:>>> my_car = Car('red') >>> my_car.drive() 'red car goes vroom!'
constructor: As with data abstraction, constructors build an instance of the class. The constructor for car objects is
Car(color)
. When Python calls that constructor, it immediately calls the__init__
method. That's where we initialize the data attributes:def __init__(self, color): self.wheels = Car.num_wheels self.color = color
The constructor takes in one argument,
color
. As you can see, this constructor also creates theself.wheels
andself.color
attributes.self
: in Python,self
is the first parameter for many methods (in this class, we will only use methods whose first parameter isself
). When a method is called,self
is bound to an instance of the class. For example:>>> my_car = Car('red') >>> car.drive()
Notice that the
drive
method takes inself
as an argument, but it looks like we didn't pass one in! This is because the dot notation implicitly passes incar
asself
for us.
Linked Lists
Minilecture Video: Linked Lists
We've learned that a Python list is one way to store sequential values. Another type of list is a linked list. A Python list stores all of its elements in a single object, and each element can be accessed by using its index. A linked list, on the other hand, is a recursive object that only stores two things: its first value and a reference to the rest of the list, which is another linked list.
We can implement a class, Link
, that represents a linked list object. Each
instance of Link
has two instance attributes, first
and rest
.
class Link:
"""A linked list.
>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.first = 5
>>> s.rest.first = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
<5 7 <8 9>>
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
A valid linked list can be one of the following:
- An empty linked list (
Link.empty
) - A
Link
object containing the first value of the linked list and a reference to the rest of the linked list
What makes a linked list recursive is that the rest
attribute of a single
Link
instance is another linked list! In the big picture, each Link
instance stores a single value of the list. When multiple Link
s are linked
together through each instance's rest
attribute, an entire sequence is
formed.
Note: This definition means that the
rest
attribute of anyLink
instance must be eitherLink.empty
or anotherLink
instance! This is enforced inLink.__init__
, which raises anAssertionError
if the value passed in forrest
is neither of these things.
To check if a linked list is empty, compare it against the class attribute
Link.empty
. For example, the function below prints out whether or not the
link it is handed is empty:
def test_empty(link):
if link is Link.empty:
print('This linked list is empty!')
else:
print('This linked list is not empty!')
Mutable Trees
Minilecture Video: Mutable Trees
Recall that a tree is a recursive abstract data type that has a label
(the
value stored in the root of the tree) and branches
(a list of trees directly
underneath the root).
We saw one way to implement the tree ADT -- using constructor and selector
functions that treat trees as lists. Another, more formal, way to implement the
tree ADT is with a class. Here is part of the class definition for Tree
,
which can be found in lab07.py
:
class Tree:
"""
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t.label
3
>>> t.branches[0].label
2
>>> t.branches[1].is_leaf()
True
"""
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = list(branches)
def is_leaf(self):
return not self.branches
Even though this is a new implementation, everything we know about the tree ADT remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the tree ADT (e.g. we can still use recursion on the branches!). The main difference, aside from syntax, is that tree objects are mutable.
Here is a summary of the differences between the tree ADT implemented using functions and lists vs. implemented using a class:
- | Tree constructor and selector functions | Tree class |
---|---|---|
Constructing a tree | To construct a tree given a label and a list of branches , we call tree(label, branches) |
To construct a tree object given a label and a list of branches , we call Tree(label, branches) (which calls the Tree.__init__ method) |
Label and branches | To get the label or branches of a tree t , we call label(t) or branches(t) respectively |
To get the label or branches of a tree t , we access the instance attributes t.label or t.branches respectively |
Mutability | The tree ADT is immutable because we cannot assign values to call expressions | The label and branches attributes of a Tree instance can be reassigned, mutating the tree |
Checking if a tree is a leaf | To check whether a tree t is a leaf, we call the convenience function is_leaf(t) |
To check whether a tree t is a leaf, we call the bound method t.is_leaf() . This method can only be called on Tree objects. |
Required Questions
WWPD: Objects
Q1: The Car class
Note: These questions use inheritance. For an overview of inheritance, see the inheritance portion of Composing Programs
Below is the definition of a Car
class that we will be using in the following WWPD questions.
Note: This definition can also be found in car.py
.
class Car:
num_wheels = 4
gas = 30
headlights = 2
size = 'Tiny'
def __init__(self, make, model):
self.make = make
self.model = model
self.color = 'No color yet. You need to paint me.'
self.wheels = Car.num_wheels
self.gas = Car.gas
def paint(self, color):
self.color = color
return self.make + ' ' + self.model + ' is now ' + color
def drive(self):
if self.wheels < Car.num_wheels or self.gas <= 0:
return 'Cannot drive!'
self.gas -= 10
return self.make + ' ' + self.model + ' goes vroom!'
def pop_tire(self):
if self.wheels > 0:
self.wheels -= 1
def fill_gas(self):
self.gas += 20
return 'Gas level: ' + str(self.gas)
Use Ok to test your knowledge with the following What would Python Display questions.
python3 ok -q wwpd-car -u
If an error occurs, type Error. If nothing is displayed, type Nothing.
>>> deneros_car = Car('Tesla', 'Model S')
>>> deneros_car.model
______'Model S'
>>> deneros_car.gas = 10
>>> deneros_car.drive()
______'Tesla Model S goes vroom!'
>>> deneros_car.drive()
______'Cannot drive!'
>>> deneros_car.fill_gas()
______'Gas level: 20'
>>> deneros_car.gas
______20
>>> Car.gas
______30
>>> deneros_car = Car('Tesla', 'Model S')
>>> deneros_car.wheels = 2
>>> deneros_car.wheels
______2
>>> Car.num_wheels
______4
>>> deneros_car.drive()
______'Cannot drive!'
>>> Car.drive()
______Error (TypeError)
>>> Car.drive(deneros_car)
______'Cannot drive!'
For the following, we reference the MonsterTruck
class below.
Note: The MonsterTruck
class can also be found in car.py
.
class MonsterTruck(Car):
size = 'Monster'
def rev(self):
print('Vroom! This Monster Truck is huge!')
def drive(self):
self.rev()
return Car.drive(self)
>>> deneros_car = MonsterTruck('Monster', 'Batmobile')
>>> deneros_car.drive()
______Vroom! This Monster Truck is huge!
'Monster Batmobile goes vroom!'
>>> Car.drive(deneros_car)
______'Monster Batmobile goes vroom!'
>>> MonsterTruck.drive(deneros_car)
______Vroom! This Monster Truck is huge!
'Monster Batmobile goes vroom!'
>>> Car.rev(deneros_car)
______Error (AttributeError)
Magic: The Lambda-ing
In the next part of this lab, we will be implementing a card game! This game is inspired by the similarly named Magic: The Gathering.
You can start the game by typing:
python3 cardgame.py
This game doesn't work yet. If we run this right now, the code will
error, since we haven't implemented anything yet. When it's working, you
can exit the game and return to the command line with Ctrl-C
or Ctrl-D
.
This game uses several different files.
- Code for all the questions in this lab can be found in
classes.py
. - Some utility for the game can be found in
cardgame.py
, but you won't need to open or read this file. This file doesn't actually mutate any instances directly - instead, it calls methods of the different classes, maintaining a strict abstraction barrier. - If you want to modify your game later to add your own custom cards and decks,
you can look in
cards.py
to see all the standard cards and the default deck; here, you can add more cards and change what decks you and your opponent use. If you're familiar with the original game, you may notice the cards were not created with balance in mind, so feel free to modify the stats and add/remove cards as desired.
Rules of the Game This game is a little involved, though not nearly as much as its namesake. Here's how it goes:
There are two players. Each player has a hand of cards and a deck, and at the start of each round, each player draws a random card from their deck. If a player's deck is empty when they try to draw, they will automatically lose the game. Cards have a name, an attack statistic, and a defense statistic. Each round, each player chooses one card to play from their own hands. The card with the higher power wins the round. Each played card's power value is calculated as follows:
(player card's attack) - (opponent card's defense) / 2
For example, let's say Player 1 plays a card with 2000 attack/1000 defense and Player 2 plays a card with 1500 attack/3000 defense. Their cards' powers are calculated as:
P1: 2000 - 3000/2 = 2000 - 1500 = 500
P2: 1500 - 1000/2 = 1500 - 500 = 1000
So Player 2 would win this round.
The first player to win 8 rounds wins the match!
However, there are a few effects we can add (in the optional questions section) to make this game a bit more interesting. Cards are split into Tutor, TA, and Professor types, and each type has a different effect when they're played. All effects are applied before power is calculated during that round:
- A Tutor card will cause the opponent to discard and re-draw the first 3 cards in their hand.
- A TA card will swap the opponent card's attack and defense.
- A Professor card will add the opponent card's attack and defense to all cards in their deck and then remove all cards in the opponent's deck that share its attack or defense!
These are a lot of rules to remember, so refer back here if you need to review them, and let's start making the game!
Q2: Making Cards
To play a card game, we're going to need to have cards, so let's make some!
We're gonna implement the basics of the Card
class first.
First, implement the Card
class constructor in classes.py
. This constructor
takes three arguments:
- the
name
of the card, a string - the
attack
stat of the card, an integer - the
defense
stat of the card, an integer
Each Card
instance should keep track of these values using instance attributes
called name
, attack
, and defense
.
You should also implement the power
method in Card
, which takes in another card as
an input and calculates the current card's power. Check the Rules section if you want
a refresher on how power is calculated.
class Card:
cardtype = 'Staff'
def __init__(self, name, attack, defense):
"""
Create a Card object with a name, attack,
and defense.
>>> staff_member = Card('staff', 400, 300)
>>> staff_member.name
'staff'
>>> staff_member.attack
400
>>> staff_member.defense
300
>>> other_staff = Card('other', 300, 500)
>>> other_staff.attack
300
>>> other_staff.defense
500
"""
"*** YOUR CODE HERE ***"
def power(self, opponent_card):
"""
Calculate power as:
(player card's attack) - (opponent card's defense)/2
>>> staff_member = Card('staff', 400, 300)
>>> other_staff = Card('other', 300, 500)
>>> staff_member.power(other_staff)
150.0
>>> other_staff.power(staff_member)
150.0
>>> third_card = Card('third', 200, 400)
>>> staff_member.power(third_card)
200.0
>>> third_card.power(staff_member)
50.0
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q Card.__init__
python3 ok -q Card.power
Q3: Making a Player
Now that we have cards, we can make a deck, but we still need players to actually use them. We'll now fill in the implementation of thePlayer
class.
A Player
instance has three instance attributes:
name
is the player's name. When you play the game, you can enter your name, which will be converted into a string to be passed to the constructor.deck
is an instance of theDeck
class. You can draw from it using its.draw()
method.hand
is a list ofCard
instances. Each player should start with 5 cards in their hand, drawn from theirdeck
. Each card in the hand can be selected by its index in the list during the game. When a player draws a new card from the deck, it is added to the end of this list.
Complete the implementation of the constructor for Player
so that self.hand
is set to a list of 5 cards drawn from the player's deck
.
Next, implement the draw
and play
methods in the Player
class. The
draw
method draws a card from the deck and adds it to the
player's hand. The play
method removes and returns a card from the player's hand at the
given index.
Call
deck.draw()
when implementingPlayer.__init__
andPlayer.draw
. Don't worry about how this function works - leave it all to the abstraction!
class Player:
def __init__(self, deck, name):
"""Initialize a Player object.
A Player starts the game by drawing 5 cards from their deck. Each turn,
a Player draws another card from the deck and chooses one to play.
>>> test_card = Card('test', 100, 100)
>>> test_deck = Deck([test_card.copy() for _ in range(6)])
>>> test_player = Player(test_deck, 'tester')
>>> len(test_deck.cards)
1
>>> len(test_player.hand)
5
"""
self.deck = deck
self.name = name
"*** YOUR CODE HERE ***"
def draw(self):
"""Draw a card from the player's deck and add it to their hand.
>>> test_card = Card('test', 100, 100)
>>> test_deck = Deck([test_card.copy() for _ in range(6)])
>>> test_player = Player(test_deck, 'tester')
>>> test_player.draw()
>>> len(test_deck.cards)
0
>>> len(test_player.hand)
6
"""
assert not self.deck.is_empty(), 'Deck is empty!'
"*** YOUR CODE HERE ***"
def play(self, card_index):
"""Remove and return a card from the player's hand at the given index.
>>> from cards import *
>>> test_player = Player(standard_deck, 'tester')
>>> ta1, ta2 = TACard("ta_1", 300, 400), TACard("ta_2", 500, 600)
>>> tutor1, tutor2 = TutorCard("t1", 200, 500), TutorCard("t2", 600, 400)
>>> test_player.hand = [ta1, ta2, tutor1, tutor2]
>>> test_player.play(0) is ta1
True
>>> test_player.play(2) is tutor2
True
>>> len(test_player.hand)
2
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q Player.__init__
python3 ok -q Player.draw
python3 ok -q Player.play
After you complete this problem, you'll be able to play a working version of the game! Type
python3 cardgame.py
to start a game of Magic: The Lambda-ing!
This version doesn't have the effects for different cards, yet - to get those working, try out the optional questions below.
WWPD: Linked Lists
Q4: WWPD: Linked Lists
Minilecture Video: Linked Lists
Read over the Link
class in lab07.py
. Make sure you understand the
doctests.
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q link -u
Enter
Function
if you believe the answer is<function ...>
,Error
if it errors, andNothing
if nothing is displayed.If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the
Link
class into the interpreter withpython3 -i lab07.py
.
>>> from lab07 import *
>>> link = Link(1000)
>>> link.first
______1000
>>> link.rest is Link.empty
______True
>>> link = Link(1000, 2000)
______AssertionError
>>> link = Link(1000, Link())
______TypeError
>>> from lab07 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______1
>>> link.rest.first
______2
>>> link.rest.rest.rest is Link.empty
______True
>>> link.first = 9001
>>> link.first
______9001
>>> link.rest = link.rest.rest
>>> link.rest.first
______3
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______1
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______1
>>> link2.rest.first
______2
>>> from lab07 import *
>>> link = Link(5, Link(6, Link(7)))
>>> link # Look at the __repr__ method of Link
______Link(5, Link(6, Link(7)))
>>> print(link) # Look at the __str__ method of Link
______<5 6 7>
Linked Lists
Q5: Convert Link
Write a function convert_link
that takes in a linked list and returns the
sequence as a Python list. You may assume that the input list is shallow; none
of the elements is another linked list.
Try to find both an iterative and recursive solution for this problem!
def convert_link(link):
"""Takes a linked list and returns a Python list with the same elements.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> convert_link(link)
[1, 2, 3, 4]
>>> convert_link(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q convert_link
Trees
Q6: Cumulative Mul
Minilecture Video: Mutable Trees
Write a function cumulative_mul
that mutates the Tree t
so that each node's
label becomes the product of all labels in the subtree rooted at the node.
def cumulative_mul(t):
"""Mutates t so that each node's label becomes the product of all labels in
the corresponding subtree rooted at t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative_mul(t)
>>> t
Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q cumulative_mul
Optional Questions
The following code-writing questions will all be in classes.py
.
For the following sections, do not overwrite any lines already provided in the
code. Additionally, make sure to uncomment any calls to print
once you have implemented
each method. These are used to display information to the user, and changing them
may cause you to fail tests that you would otherwise pass.
Q7: Tutors: Flummox
To really make this card game interesting, our cards should have effects!
We'll do this with the effect
function for cards, which takes
in the opponent card, the current player, and the opponent player.
Implement the effect
method for Tutors, which causes the opponent to discard
the first 3 cards in their hand and then draw 3 new cards. Assume there at least 3 cards
in the opponent's hand and at least 3 cards in the opponent's deck.
Remember to uncomment the call to print
once you're done!
class TutorCard(Card):
cardtype = 'Tutor'
def effect(self, opponent_card, player, opponent):
"""
Discard the first 3 cards in the opponent's hand and have
them draw the same number of cards from their deck.
>>> from cards import *
>>> player1, player2 = Player(player_deck, 'p1'), Player(opponent_deck, 'p2')
>>> opponent_card = Card('other', 500, 500)
>>> tutor_test = TutorCard('Tutor', 500, 500)
>>> initial_deck_length = len(player2.deck.cards)
>>> tutor_test.effect(opponent_card, player1, player2)
p2 discarded and re-drew 3 cards!
>>> len(player2.hand)
5
>>> len(player2.deck.cards) == initial_deck_length - 3
True
"""
"*** YOUR CODE HERE ***"
#Uncomment the line below when you've finished implementing this method!
#print('{} discarded and re-drew 3 cards!'.format(opponent.name))
Use Ok to test your code:
python3 ok -q TutorCard.effect
Q8: TAs: Shift
Let's add an effect for TAs now! Implement the effect
method for TAs, which
swaps the attack and defense of the opponent's card.
class TACard(Card):
cardtype = 'TA'
def effect(self, opponent_card, player, opponent):
"""
Swap the attack and defense of an opponent's card.
>>> from cards import *
>>> player1, player2 = Player(player_deck, 'p1'), Player(opponent_deck, 'p2')
>>> opponent_card = Card('other', 300, 600)
>>> ta_test = TACard('TA', 500, 500)
>>> ta_test.effect(opponent_card, player1, player2)
>>> opponent_card.attack
600
>>> opponent_card.defense
300
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q TACard.effect
Q9: The Professor Arrives
A new challenger has appeared! Implement the effect
method for the Professor,
who adds the opponent card's attack and defense to all cards in the player's
deck and then removes all cards in the opponent's deck that have the same
attack or defense as the opponent's card.
Note: You might run into trouble when you mutate a list as you're iterating through it. Try iterating through a copy instead! You can use slicing to copy a list:
>>> lst = [1, 2, 3, 4] >>> copy = lst[:] >>> copy [1, 2, 3, 4] >>> copy is lst False
class ProfessorCard(Card):
cardtype = 'Professor'
def effect(self, opponent_card, player, opponent):
"""
Adds the attack and defense of the opponent's card to
all cards in the player's deck, then removes all cards
in the opponent's deck that share an attack or defense
stat with the opponent's card.
>>> test_card = Card('card', 300, 300)
>>> professor_test = ProfessorCard('Professor', 500, 500)
>>> opponent_card = test_card.copy()
>>> test_deck = Deck([test_card.copy() for _ in range(8)])
>>> player1, player2 = Player(test_deck.copy(), 'p1'), Player(test_deck.copy(), 'p2')
>>> professor_test.effect(opponent_card, player1, player2)
3 cards were discarded from p2's deck!
>>> [(card.attack, card.defense) for card in player1.deck.cards]
[(600, 600), (600, 600), (600, 600)]
>>> len(player2.deck.cards)
0
"""
orig_opponent_deck_length = len(opponent.deck.cards)
"*** YOUR CODE HERE ***"
discarded = orig_opponent_deck_length - len(opponent.deck.cards)
if discarded:
#Uncomment the line below when you've finished implementing this method!
#print('{} cards were discarded from {}\'s deck!'.format(discarded, opponent.name))
return
Use Ok to test your code:
python3 ok -q ProfessorCard.effect
After you complete this problem, we'll have a fully functional game of Magic: The Lambda-ing! This doesn't have to be the end, though - we encourage you to get creative with more card types, effects, and even adding more custom cards to your deck!
Q10: Cycles
The Link
class can represent lists with cycles. That is, a list may
contain itself as a sublist.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3
Implement has_cycle
,that returns whether its argument, a Link
instance, contains a cycle.
Hint: Iterate through the linked list and try keeping track of which
Link
objects you've already seen.
def has_cycle(link):
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q has_cycle
As an extra challenge, implement has_cycle_constant
with only constant space. (If you followed
the hint above, you will use linear space.) The solution is short (less than 20
lines of code), but requires a clever idea. Try to discover the solution
yourself before asking around:
def has_cycle_constant(link):
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle_constant(t)
False
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q has_cycle_constant
Q11: Every Other
Implement every_other
, which takes a linked list s
. It mutates s
such
that all of the odd-indexed elements (using 0-based indexing) are removed from
the list. For example:
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True
If s
contains fewer than two elements, s
remains unchanged.
Do not return anything!
every_other
should mutate the original list.
def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q every_other
Q12: Reverse Other
Write a function reverse_other
that mutates the tree such that labels on
every other (odd-depth) level are reversed. For example,
Tree(1,[Tree(2, [Tree(4)]), Tree(3)])
becomes Tree(1,[Tree(3, [Tree(4)]), Tree(2)])
.
Notice that the nodes themselves are not reversed; only the labels are.
def reverse_other(t):
"""Mutates the tree such that nodes on every other (odd-depth) level
have the labels of their branches all reversed.
>>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(4), Tree(3), Tree(2)])
>>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q reverse_other