Instructions
Requirements and Specifications
Source Code
QUESTION 1
=== Question 1 answers ===
(a) Answer (YES or NO):
If yes, explain how, and if no, explain why not:
Yes. If class instance has invariant, one must guarantee, that after execution of this new method, the invariant is satisfied.
Common approach is to make necessary check and raise exception if state is invalid.
(b) The docstring is:
"""
Tests, that last element of index after appending v is v
"""
The function body is:
lst.append(v)
assert lst[-1] == v
QUESTION 3
"""
Question (12 marks)
TO HAND IN: Add your code to this file and hand it in on MarkUs. Be sure to
run the self-test on MarkUs to avoid failing all our tests due to a silly error.
--------------------------------------------------------------------------------
In this question, you will write code to implement magical creatures so that
the doctest examples below run without error, and these specifications are
followed:
- There are 2 kinds of magical creatures for now, but we plan to add more later.
- When created, magical creatures have a name and an amount of vitality
(100 units of vitality for unicorns, but only 50 for pixies.)
- All magical creatures can return a string that is suitable for printing.
- All magical creatures can sing (return a string representing their song),
but their songs vary (as shown below) and singing affects their vitality
differently:
- Unicorns find singing joyous, so their vitality goes up by 1
- Pixies find singing laborious, so their vitality goes down by 20.
And if they try to sing when their vitality is under 20, they just
return the string 'cough!' and their vitality is unaffected.
- All magical creatures can fly, and when they do, their vitality increases
by the distance they fly (see example usage in the doctests below). You may
assume that the distance argument is > 0.
- There is no upper limit on a magical creature's vitality.
- Magical creatures are considered equivalent if they have the same amount of
vitality.
Any behaviour that is not specified by this description plus the doctests is
up to you.
We have started the code for you.
- You must not alter anything that is already written. Just add to it.
- No docstrings are required. But for full marks, you must provide type
annotations that specify the return type and parameter types for each method.
- Part of the marks will be for avoiding repeated code where appropriate.
- Do not add any new attributes.
HINT: Run this module to check your code against these doctest examples:
>>> u1 = Unicorn('Mary')
>>> print(u1)
Name: Mary, vitality: 100
>>> u1.sing()
'I am majestic, la la la.'
>>> print(u1)
Name: Mary, vitality: 101
>>> p1 = Pixie('Cornelius')
>>> print(p1)
Name: Cornelius, vitality: 50
>>> p1.sing() # Cornelius is about to wear himself out singing.
'I am Cornelius and I like mischief, haha.'
>>> print(p1)
Name: Cornelius, vitality: 30
>>> p1.sing()
'I am Cornelius and I like mischief, haha.'
>>> print(p1)
Name: Cornelius, vitality: 10
>>> p1.sing() # Cornelius doesn't have enough vitality left to sing.
'cough!'
>>> p1.fly(110) # But flying gives him more vitality.
>>> print(p1)
Name: Cornelius, vitality: 120
>>> p1.sing()
'I am Cornelius and I like mischief, haha.'
>>> print(p1)
Name: Cornelius, vitality: 100
>>> u2 = Unicorn('Lucius')
>>> print(u2)
Name: Lucius, vitality: 100
>>> u2 == p1 # This unicorn and this pixie have the same vitality.
True
--------------------------------------------------------------------------------
This file is Copyright (c) 2022 University of Toronto
All forms of distribution, whether as given or with any changes, are
expressly prohibited.
--------------------------------------------------------------------------------
"""
from __future__ import annotations
class MagicalCreature:
name: str
vitality: int
# TODO: Implement this class
def __init__(self, name: str, vitality: int):
self.name = name
self.vitality = vitality
def __str__(self) -> str:
return 'Name: {0}, vitality: {1}'.format(self.name, self.vitality)
def sing(self) -> str:
return ''
def fly(self, dist: int):
self.vitality += dist
def __eq__(self, other):
return self.vitality == other.vitality
class Unicorn(MagicalCreature):
name: str
vitality: int
# TODO: Implement this class
def __init__(self, name: str):
MagicalCreature.__init__(self, name, 100)
def sing(self) -> str:
self.vitality += 1
return 'I am majestic, la la la.'
class Pixie(MagicalCreature):
name: str
vitality: int
# TODO: Implement this class
def __init__(self, name: str):
MagicalCreature.__init__(self, name, 50)
def sing(self) -> str:
if self.vitality < 20:
return 'cough!'
self.vitality -= 20
return 'I am {0} and I like mischief, haha.'.format(self.name)
if __name__ == '__main__':
import doctest
doctest.testmod()
QUESTION 4
"""
Question (5 marks)
Implement the function below according to the docstring provided.
You may use the Stack and Queue classes provided in module 'adts' to
create temporary Stack and/or Queue objects. These are the same Stack and
Queue classes you have seen before.
Rules:
- You must NOT create any other compound objects (lists, dictionaries, etc.)
- You may create variables to store individual values (counters, items that
have been popped or dequeued, etc.)
- You may add doctest examples if desired.
Hint: You may find it helpful to use modular division by 2, that is, "% 2".
TO HAND IN: Add your code to this file and hand it in on MarkUs. Be sure to
run the self-test on MarkUs to avoid failing all our tests due to a silly error.
--------------------------------------------------------------------------------
This file is Copyright (c) 2022 University of Toronto
All forms of distribution, whether as given or with any changes, are
expressly prohibited.
--------------------------------------------------------------------------------
"""
from adts import Stack, Queue
def remove_odd(s: Stack) -> None:
"""Modify s to remove any elements that are odd.
Do NOT return a new stack. Modify the one that is given.
Precondition: Each item in s is an int.
>>> s = Stack()
>>> s.push(10)
>>> s.push(9)
>>> s.push(3)
>>> s.push(2)
>>> s.push(5)
>>> remove_odd(s)
>>> s.pop()
2
>>> s.pop()
10
>>> s.is_empty()
True
"""
index = 0
while index < len(s._items):
if s._items[index] % 2 == 1:
del s._items[index]
else:
index += 1
return None
if __name__ == '__main__':
import doctest
doctest.testmod()
QUESTION 5
"""
Question (6 marks)
We are adding another method to the LinkedList class. It's almost written
but 4 lines are missing. Complete those lines so that the method is correct
according to its docstring.
Rules:
- For each TODO below, write a single line of code as indicated,
without changing its indentation.
- You must not change any other code in any way. E.g., you must not modify,
delete or add to what is there.
TO HAND IN: Add your code to this file and hand it in on MarkUs. Be sure to
run the self-test on MarkUs to avoid failing all our tests due to a silly error.
--------------------------------------------------------------------------------
This file is Copyright (c) 2022 University of Toronto
All forms of distribution, whether as given or with any changes, are
expressly prohibited.
--------------------------------------------------------------------------------
"""
from __future__ import annotations
from typing import Any, Optional
class _Node:
"""A node in a linked list.
Note that this is considered a "private class", one which is only meant
to be used in this module by the LinkedList class, but not by client code.
=== Attributes ===
item:
The data stored in this node.
next:
The next node in the list, or None if there are no more nodes.
"""
item: Any
next: Optional[_Node]
def __init__(self, item: Any) -> None:
"""Initialize a new node storing - , with no next node.
"""
self.item = item
self.next = None # Initially pointing to nothing
class LinkedList:
"""A linked list implementation of the List ADT.
"""
# === Private Attributes ===
# _first:
# The first node in the linked list, or None if the list is empty.
_first: Optional[_Node]
def __init__(self, items: list) -> None:
"""Initialize a new linked list containing the given items.
The first node in the linked list contains the first item
in .
"""
if len(items) == 0: # No items, and an empty list!
self._first = None
else:
self._first = _Node(items[0])
curr = self._first
for item in items[1:]:
curr.next = _Node(item)
curr = curr.next
def __str__(self) -> str:
"""Return a string representation of this list in the form
'[item1 -> item2 -> ... -> item-n]'.
>>> str(LinkedList([1, 2, 3]))
'[1 -> 2 -> 3]'
>>> str(LinkedList([]))
'[]'
"""
items = []
curr = self._first
while curr is not None:
items.append(str(curr.item))
curr = curr.next
return '[' + ' -> '.join(items) + ']'
def insert_at_end(self, v: int) -> int:
"""
Add a new node at the end of this linked list, with the value v in it,
and return the total of the values in all nodes, including the new last
node.
>>> linky = LinkedList([5, 20, 15, 10])
>>> linky.insert_at_end(9)
59
>>> print(linky)
[5 -> 20 -> 15 -> 10 -> 9]
>>> linky = LinkedList([5])
>>> linky.insert_at_end(9)
14
>>> print(linky)
[5 -> 9]
>>> linky = LinkedList([])
>>> linky.insert_at_end(9)
9
>>> print(linky)
[9]
"""
if self._first is None:
self._first = _Node(v) # TODO: Replace pass with one line of code
return v # TODO: Replace pass with one more line of code
else:
curr = self._first
total = 0
while curr.next is not None:
total += curr.item
curr = curr.next
curr.next = _Node(v) # TODO: Replace pass with one line of code
return total + curr.item + v # TODO: Replace pass with one more line of code
if __name__ == '__main__':
import doctest
doctest.testmod()