# Solutions to Problems

## Chapter 2 Solutions

### Question 1

#### Is the ** (power) operator left or right associative?

The power operator (**) is right associative. We would not evaluate 222 as 42, instead it is evaluated as 24.

### Question 2

#### Is the % operator left or right associative?

The modulo (%) operator is left associative

### Question 3

#### Where in the precedence hierarchy do ** and % appear?

The power (**) operator appears at the top of the precedence hierarchy. The modulo (%) operator appears at the same level as multiplication and division operators.

### Question 4

#### How are the following expressions evaluated?

# 1 + 4 - 5 * 7 // 3
1 + 4 - 5 * (7 // 3)
1 + 4 - (5 * (7 // 3))
1 + (4 - (5 * (7 // 3)))
(1 + (4 - (5 * (7 // 3))))

# 2 ** 3 * 4 + 8 // 3
(2 ** 3) * 4 + 8 // 3
((2 ** 3) * 4) + 8 // 3
((2 ** 3) * 4) + (8 // 3)
(((2 ** 3) * 4) + (8 // 3))

# 4 % 3 ** 5 - 2 ** 2
4 % (3 ** 5) - 2 ** 2
4 % (3 ** 5) - (2 ** 2)
(4 % (3 ** 5)) - (2 ** 2)
((4 % (3 ** 5)) - (2 ** 2))

### Question 5

#### From the following list of integer expressions, which expression(s) have invalid syntax?

((4 * 6 - (4 // 2))
- INVALID!

9 * - 11 + 6
- VALID

6 - +4
- VALID

## Chapter 3 Solutions

### Question 1

Assume a population of rabbits doubles every 3 months. Further assume the current population is 11 rabbits i.e. number_of_rabbits = 11

Write a Python program to calculate the rabbit population after 2 years and print the result to the terminal.

#### Solution

number_of_rabbits = 11
years = 2

months_passed = 12 * years
times_pop_doubles = months_passed // 3

pop_after_time = number_of_rabbits * (2 ** times_pop_doubles)
print(pop_after_time)

### Question 2

Extend the above program to allow the user to input the number of rabbits and the time period after which you want to know the rabbit population e.g. 4 years

#### Solution

number_of_rabbits = 11
years = int(input("Enter number of years: "))

months_passed = 12 * years
times_pop_doubles = months_passed // 3

pop_after_time = number_of_rabbits * (2 ** times_pop_doubles)
print(pop_after_time)

### Question 3

Assume the user is going to input 2 numbers, x and y for example. Write a Python program that will swap the numbers stored in these variables e.g.

# Assume the user has input these
x = 3
y = 11
# Your code to swap here
# After, the variables should be:
# x = 11
# y = 3

#### Solution

x = input("X value: ")
y = input("Y value: ")

tmp = x
x = y
y = tmp

print("X after swap: " + x)
print("Y after swap: " + y)

### Question 4

The goal of this task is to derive a single assignment statement for the following sequences such that, if the variable x has the first value in a sequence, then x will have the next value in the sequence after the assignment statement is executed. And if the assignment statement were executed repeatedly, then x would cycle through all of the values in the sequence.

# EXAMPLE

# Sequence:
# 0 1 2 3 4 5 6 7 ...

#SOLUTION
x = x + 1
##### Sequence 1:
0 2 4 6 8 10 12 ...
##### Sequence 2:
0 -1 -2 -3 -4 -5 -6 ...
##### Sequence 3:
6 -6 6 -6 6 -6 ...
##### Sequence 4 (Difficult)
0 -6 -3 0 -6 -3 0 -6 -3 0 ...

### Solution

##### Sequence 1
x = 0
x = x + 2
##### Sequence 2
x = 0
x = x - 1
##### Sequence 3
x = 6
x = x * -1
##### Sequence 4
x = 0
x = x % 9 - 6

## Chapter 4 Solutions

### Question 1

Write a program that takes three inputs, a, b and c and prints out whether or not those numbers form a right angled triangle. The formula you'll need is:
$$c = \sqrt{(a^2 + b ^2)}$$

#### Solution

We're going to use Pythagoras theorem here (the formula given in the question), that is, in any right angled triangle, the area of the square whose side is the hypotenuse is equal to the sum of the other two sides. Since we don't know which side may be the hypotenuse we must check all three sides as any could be the hypothenuse.

a = int(input("Enter side 1: "))
b = int(input("Enter side 2: "))
c = int(input("Enter side 3: "))

# Result is a boolean
a_as_hypotenuse = a == ((b ** 2) + (c **2)) ** 0.5
b_as_hypotenuse = b == ((a ** 2) + (c **2)) ** 0.5
c_as_hypotenuse = c == ((a ** 2) + (b **2)) ** 0.5

# Check if a is the hypotenuse
if a_as_hypotenuse or b_as_hypotenuse or c_as_hypotenuse:
print("These sides form a right angle triangle!")
else:
print("These sides do not form a right angle triangle")

### Question 2

Fizz buzz is a game in which the following rules apply:

• any number which is divisible by 3 is replaced with fizz
• any number which is divisible by 5 is replaced with buzz
• any number which is divisible by both 3 and 5 is replaced with fizz-buzz
• any other number is just the number itself

Examples:

1 = 1
2 = 2
3 = fizz
4 = 4
5 = buzz
6 = 6
.
.
15 = fizz-buzz
###### * Remember what I said about how if...elif..else statements are evaluated sequentially (first to last) until the first condition passes

In your solution you should expect the user to enter a single number and either print the number, fizz, buzz or fizz-buzz

#### Solution

We need to be careful here, we must check if the number is divisible by both 3 and 5 before we check if it's divisible by only 3 or only 5.

number = int(input("Enter a number: "))
if number % 3 == 0 and number % 5 == 0:
print("fizz-buzz")
elif number % 3 == 0:
print("fizz")
elif number % 5 == 0:
print("buzz")
else:
print(number)

### Question 3

Write a program which takes in six numbers, x1, y1, r1 and x2, y2, r2 (which are the x and y coordinates of the center of a circle and that circles radius) and print out whether or not the two circles overlap.

You're going to need the formula for the distance between two points to solve this which is:
$$d(P, Q) = \sqrt{(x2 - x1)^{2} + (y2 - y1)^{2}}$$

The rest requires some problem solving! Perhaps drawing out the scenario on paper might help?

#### Solution

Our approach is to check if the distance between the centers of both circles is greater than the sum of their radii. If it is, then they are not overlapping, otherwise they are.

x1 = int(input("Circle-1 x: "))
y1 = int(input("Circle-1 y: "))

x2 = int(input("Circle-2 x: "))
y2 = int(input("Circle-2 y: "))

# Raising a number to the power of 0.5
# is the same as square root
distance = ((x2 - x1)**2 + (y2 - y1)**2)**0.5

print("The circles do not overlap!")
else:
print("The circles overlap!")

## Chapter 5 Solutions

### Question 1

Write a program that prints the first n numbers of the Fibonacci sequence. The Fibonacci sequence is defined as:
Fn = Fn − 1 + Fn − 2

F0 = 0, F1 = 1

That is, the next number in the sequence is the sum of the previous two numbers and the first two numbers in the sequence are 0 and 1. A part of the sequence is shown below:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

#### Solution

num_terms = int(input("How many terms?: "))

n2 = 0
n1 = 1

if num_terms <= 0:
print("Please enter a number greater than 0")
elif num_terms == 1:
print(n2)
else:
count = 0
while count < num_terms:
print(n2)
next_term = n1 + n2
n2 = n1
n1 = next_term
count += 1

### Question 2

Write a program that prints a sequence such as the one shown below. The number of stars in the widest part should be equal to the number a user inputs:

# INPUT
7

# OUTPUT
*
**
***
****
*****
******
*******
******
*****
****
***
**
*

#### Solution

width = int(input("How wide?: "))

curr_width = 1
while curr_width < width:
print("*" * curr_width)
curr_width += 1

while curr_width > 0:
print("*" * curr_width)
curr_width -= 1

### Question 3

Write a Python program that reads in a single integer from the user. Then read in an unknown number of integers, each time printing whether or not the number was higher or lower than the previous. You can assume that every number is different and you can stop when the number entered is 0. Here is an example input and output:

# INPUT
5
2
9
7
0

# OUTPUT
lower
higher
lower
Exiting...

#### Solution

number = int(input("Enter a number: "))

n = int(input("Enter another number: "))
while n != 0:
if n < number:
print("lower")
else:
print("higher")
n = int(input("Enter another number: "))

print("Exiting...")

## Chapter 6 Solutions

### Question 1

Write a program that takes as input, a single integer from the user which will specify how many decimal places the number e should be formatted to.

Take e to be 2.7182818284590452353602874713527

# EXAMPLE INPUT
4
# EXAMPLE OUTPUT
2.7183

#### Solution

n = int(input("How many decimal places?: "))

e = 2.7182818284590452353602874713527
print("{:.{}f}".format(e, n))

### Question 2

Write a program that will take as input, a string and two integers. The two integers will represent indices. If the string can be sliced using the two indices then print the sliced string. If either or both of the integers are outside the strings index range then print that the string cannot be sliced at those integers.

Assume that the integers can also be negative.

# EXAMPLE INPUT
"This is my string"
2
9

# EXAMPLE OUTPUT
'is is m'

# EXAMPLE INPUT
"This is a string"
10
22

# EXAMPLE OUTPUT
'Cannot slice string using those indices'

#### Solution

string = input()
lower = int(input("Enter the lower index: "))
upper = int(input("Enter the upper index: "))

if lower > len(string) or upper > len(string):
print("Cannot slice string using those indices")
else:
print(string[lower:upper])

### Question 3

When you sign up for accounts on website or apps, you may be told your password strength when entering it for the first time. In this exercise, you are to write a program that takes in as input, a string that will represent a password.

Assume a password can contain the following:

• digits
• lowercase letters
• uppercase letters
• special characters e.g. $, #, @, ^ A passwords strength should be graded on how many of the above categories are contained in the password. The password should be given a score of 1 to 4. If the password is greater than or equal to strength 3 (contains characters from 3 of the above categories) then you should print the strength and that the password is valid. Otherwise print the strength and that the password is not valid. Python comes with built-in documentation. To access this, at the command prompt type pydoc str. This will return the documentation for the str type. Here you will find all methods strings have to offer. # EXAMPLE INPUTS 978 hjj jKl nmM2 r@num978LL LLLL # EXAMPLE OUTPUTS 1 1 2 3 4 1 #### Solution password = input() contains_digit = False contains_lower = False contains_upper = False contains_special = False special_chars = "$#@^"

i = 0
if curr.isdigit() and not contains_digit:
contains_digit = True

elif curr.isalpha() and curr.islower() and not contains_lower:
contains_lower = True

elif curr.isalpha() and curr.isupper() and not contains_upper:
contains_upper = True

elif curr in special_chars and not contains_special:

contains_special = True
i += 1

print("Password strength: " + str(password_strength))

### Question 4

Write a program that takes 3 floating point numbers as input from the user: a starting radius, radius increment and an ending radius. Based on these three numbers, your program should output a table with a spheres corresponding surface area and volume.

The surface area and volume of a sphere are given by the following formulae:
A = 4πr2

$$V = \frac{4}{3}\pi r^{3}$$

Hint: Formatting is key here

# EXAMPLE INPUT
1
1
10

# EXAMPLE OUTPUT
----------      ----------    ------------
1.0           12.57            4.19
2.0           50.27           33.51
3.0          113.10          113.10
4.0          201.06          268.08
5.0          314.16          523.60
6.0          452.39          904.78
7.0          615.75         1436.76
8.0          804.25         2144.66
9.0         1017.88         3053.63
10.0         1256.64         4188.79

#### Solution

We will set a max width for the table of 42

radius = int(input("Enter radius: "))
inc = int(input("Enter increment: "))
end = int(input("Enter ending radius: "))

max_width = 42
print("{:>10s}{:>16s}{:>16s}".format("----------", "----------", "----------"))

i = 0
while i < end:
area = 4 * 3.14 * radius ** 2
volume = (4/3) * 3.14 * radius ** 3
i += 1

## Chapter 7 Solutions

### Question 1

Write a program that takes a string from the user and prints the first number encountered along with it's position.

You can assume the number is a single digit

# EXAMPLE INPUT
"This is chapter 7 of the book"

# EXAMPLE OUTPUT
"7 16"

# EXAMPLE INPUT
"There are no digits here"

#EXAMPLE OUTPUT
"No digits in string"

#### Solution

string = input("Enter a string: ")

i = 0
while i < len(string) and not string[i].isdigit():
i += 1

if i < len(string):
print(string[i], i)
else:
print("No digits in string")

### Question 2

Building upon the previous exercise, write a program that takes a string as input from the user and prints the first number encountered along with the starting position of the number.

Working through this question on paper would be a good idea!

# EXAMPLE INPUT
"This chapter has 1208 words in it!"

# EXAMPLE OUTPUT
"1208 17"

# EXAMPLE INPUT
"There is no numbers here"

# EXAMPLE OUTPUT
"No numbers in string"

#### Solution

string = input("Enter a string: ")

i = 0
while i < len(string) and not string[i].isdigit():
i += 1

if i < len(string):
j = i
while j < len(string) and not string[j].isalpha():
j += 1
print(string[i:j-1], i)

### Question 3

Write a program that takes a string as input from the user. The string will consist of digits and your program should print out the first repdigit. A repdigit is a number where all digits in the number are the same. Examples of repdigits are 22, 77, 2222, 99999, 444444.

# EXAMPLE INPUT
"34 74 86 34576 47093 3 349852 777 9082"

# EXAMPLE OUTPUT
"777"

# EXAMPLE INPUT
"98 3462 245 87658"

# EXAMPLE OUTPUT
"No repdigit in string"

#### Solution

string = input("Enter a string: ")

repdigit_found = False

i = 0
while i < len(string) and not repdigit_found:
j = i + 1
while j < len(string) and not string[i] == string[j]:
i += 1
j += 1

if j < len(string):

while j < len(string) and string[i] == string[j]:
j += 1

if string[i] == string[j-1]:
repdigit_found = True
print(string[i:j])

i = j + 1

### Question 4

If you open a browser and go to any web page that has text on it and press Ctrl+f, a search box will pop up. You can type any word in this search box and all occurrences of that word on the page are highlighted. This doesn't use linear search, it uses something called regular expressions (don't worry about what they are). As well as the occurrences of the word being highlighted, you are also told how many times the word occurs.

You are to write a program which mimics this behaviour. Your program should take a string as input from the user and then a second string as input which is the word the user wants to search for. Your program should print out how many times the word occurs in the string.

Assume that it still counts if the word you're searching for is embedded in another word, for example if the user was searching for the word "search":

search and searching <- you can count this as 2 occurrences

# EXAMPLE INPUT
"In this type of search, a sequential search is made over all items one by one"
"search"

# EXAMPLE OUTPUT
2

# EXAMPLE INPUT
"There wont be an occurrence here"
"python"

# EXAMPLE OUTPUT
0

#### Solution

string = input("Enter some text: ")
find = input("What word are you searching for?: ")

occurences = 0

i = 0
while i < len(string):
j = i
while j < len(string) and not string[j] == find:
j += 1

if j < len(string) and string[j:j+len(find)] == find:
occurences += 1

i = j + 1

print("The word '" + find + "' occurs " + str(occurences) + " times")

## Chapter 8 Solutions

### Question 1

Write a program that takes a string as input from the user, followed by a number and output each word which has a length greater than or equal to the number.

The string will be a series of words such as "apple orange pear grape melon lemon"

# EXAMPLE INPUT
"elephant cat dog mouse bear wolf lion horse"
5

# EXAMPLE OUTPUT
elephant
mouse
horse

You may use the following code at the beginning of your program

my_words = input().split()
num = int(input())

# REMEMBER: my_words is a list

#### Solution

my_words = input("Enter words: ").split()
num = int(input("Enter a length: "))

i = 0
while i < len(my_words):
if len(my_words[i]) >= num:
print(my_words[i])
i += 1

### Question 2

Write a program that takes a string as input from the user, followed by another string (the suffix) and output each word that ends in the suffix.

The first string will be a series of words such as "apples oranges pears grapes lemons melons"

You are to use the split() function to split the string

# EXAMPLE INPUT
"apples oranges pears grapes lemons melons"
"es"

# EXAMPLE OUTPUT
apples
oranges
grapes

Hint: Your solution should be generalized for any suffix. Don't assume the length of the suffix will be 2

#### Solution

words = input().split()
suffix = input()

i = 0
while i < len(words):
if words[i][-len(suffix):] == suffix:
print(words[i])
i += 1

### Question 3

Write a program that builds a list of integers from user input. You should stop when the user enters 0.

Your program should print out the list.

# EXAMPLE INPUT
3
5
6
7
0

# EXAMPLE OUTPUT
[3, 5, 6, 7]

#### Solution

numbers = []

digit = int(input())

# Remember: all integers are truthy except 0
while digit:
numbers.append(digit)
digit = int(input())

print(numbers)

### Question 4

Building on your solution to question 3, taking a list built up from user input, ask the user for two more pieces of input. Integers this time.

The integers will represent indices. You are to swap the elements at the specified indices with eachother.

# EXAMPLE INPUT
6
3
9
0

*********************************
* LIST SHOULD NOW BE: [6, 3, 9] *
*********************************

1
2

# EXAMPLE OUTPUT
[6, 9, 3]

#### Solution

numbers = []

digit = int(input())
while digit:
numbers.append(digit)
digit = int(input())

index1 = int(input("Index 1: "))
index2 = int(input("Index 2: "))

tmp = numbers[index1]
numbers[index1] = numbers[index2]
numbers[index2] = tmp

print(numbers)

### Question 5

Write a program that builds a list of integers from user input. You program should then find the smallest of those integers and put it at the first index (0) in the list. Input ends when the user inputs 0.

# EXAMPLE INPUT
10
87
11
5
65
342
12
0

# LIST SHOULD NOW BE: [10, 87, 11, 5, 65, 342, 12]

# EXAMPLE OUTPUT
[5, 87, 11, 10, 65, 342, 12]

#### Solution

numbers = []

digit = int(input())
while digit:
numbers.append(digit)
digit = int(input())

# Keep track of position of smallest number
smallest_index = 0

i = 1
while i < len(numbers):
if numbers[i] < numbers[smallest_index]:
smallest_index = i
i += 1

tmp = numbers[smallest_index]
numbers[smallest_index] = numbers
numbers = tmp

print(numbers)

### Question 6

* THIS IS A HARD PROBLEM *

Write a program that takes two sorted lists as input from the user and merge them together. The resulting list should also be sorted. Both of the input lists will be in increasing numerical order, the resulting list should be also.

# EXAMPLE INPUT
2
6
34
90
0      # END OF FIRST INPUT
5
34
34
77
98
0     # END OF SECOND INPUT

# EXAMPLE OUTPUT
[2, 5, 6, 34, 34, 34, 77, 90, 98]

Don't assume both lists will be the same length!

#### Solution

# Take input for first list
list1 = []

digit = int(input())
while digit:
list1.append(digit)
digit = int(input())

# Take input for second list
list2 = []

digit = int(input())
while digit:
list2.append(digit)
digit = int(input())

# Merge both lists
merged_list = []

i = 0
j = 0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
merged_list.append(list1[i])
i += 1
else:
merged_list.append(list2[j])
j += 1

# Handle the case were one list if longer than the other
# - Just append everything else in the longer list
if i < len(list1):
while i < len(list1):
merged_list.append(list1[i])
i += 1
else:
while j < len(list2):
merged_list.append(list2[j])
j += 1

print(merged_list)

## Chapter 9 Solutions

### Question 1

What is the time complexity of:

1. Insertion sort
2. Selection sort

#### Solution

The time complexity of Insertion sort is O(n^2)

The time complexity of Selection sort is O(n^2)

### Question 2

What is the space complexity of:

1. Selection sort
2. Insertion sort

#### Solution

The space complexity of Selection sort is O(1)

The space complexity of Insertion sort is O(1)

### Question 3

Give two examples of when we might use selection sort or insertion sort in the real world?

#### Solution

Although the time complexities of Selection sort and Insertion sort are O(n^2), they are the algorithm of choice either when the data is nearly sorted or when the problem size is small.

### Question 4

If we ended up in a situation in which the input was sorted but we didn't know and we try to sort the input, why might we prefer insertion sort over selection sort?

You may have to go and search for the answer to this.

#### Solution

Usually, insertion sort will perform less comparisons than selection sort, depending on the degree of "sortedness" of the list. While selection sort must scan the remaining parts of the list when placing an element, insertion sort only scans as many elements as necessary. That means that when the array is already sorted or almost sorted, insertion sort performs in O(n) time.

One advantage of selection sort over insertion sort, is that the number of writes (swaps) is in O(n), while in insertion sort it is in O(n^2). This may be important if you are sorting on Flash memory, for example, because writes reduce the lifespan of Flash memory.

## Chapter 10 Solutions

### Question 1

Write a program that multiplies an arbitrary number of command-line arguments together. The arguments will be numbers (convert them first).

Your program should be run as follows:

$py calc.py 5 99 32 .... To test that your solution is correct, you should get the following output $ py calc.py 8 8 9 3 2
3456

#### Solution

import sys

total = 1

i = 1
while i < len(sys.argv):
total *= int(sys.argv[i])
i += 1

print(total)

### Question 2

Write a program that reads in lines from standard input (no redirection) and outputs them to standard output (no redirection).

#### Solution

import sys

while line:
print(line)
line = sys.stdin.readline()

### Question 3

Write a program that reads a text file and outputs (using print() is fine) how many words are contained within that file. The name of the text file should be passed as a command-line argument to your script.

Your program shouldn't consider blank lines as words and you need not worry about punctuation. For example you can consider "trust," to be a single word.

Your program should be run as follows:

$py num_words.py input.txt To test that your solution is correct, use the Second Inaugural Address of Abraham Lincoln as your input text and your program should output: 701 #### Solution import sys filename = sys.argv with open(filename, "r") as f: text = f.read() words = text.split() print(len(words)) ### Question 4 Write a program that reads in the contents of a file. Each line will contain a word or phrase. Your program should output (using print() is fine) whether or not each line is a palindrome or not, "True" or "False". The name of the text file should be passed as a command-line argument to your script. A palindrome is a word or phrase that is the same backwards as it is forwards. For example, "racecar" is a palindrome while "AddE" is not. Your program should not be case sensitive: "Racecar" should still be considered a palindrome. Spaces should NOT effect your program either. Consider removing white space characters. Your program should be run as follows: $ py palindrome.py input.txt

To test that your solution is correct, use the following as your input text:

racecar
HmllpH
Was it a car or a cat I saw
Hannah
T can arise in context where language is played wit
Able was I ere I saw Elba
Doc note I dissent A fast never prevents a fatness I diet on cod

Using the above input, your output should be:

True
False
False
True
True
False
True
True

#### Solution

import sys

filename = sys.argv

with open(filename, "r") as f:
while word:
processed = word.replace(" ", "").lower()
if processed == processed[::-1]:
print(True)
else:
print(False)
word = f.readline().strip()

### Question 5

__** THIS QUESTION IS HARD **__

Similar to question 3, write a program that reads a text file. This time your program should output how many unique words are contained within the file.

This time you do need to care about punctuation and your solution should not be case sensitive. For example "trust" and "trust," and "Trust" should be considered the same word, therefore only one occurrence of that word should be recorded as unique and if you were to come across "trust" again, then don't record it.

Your program should be run as follows:

$py unique_words.py input.txt To test if your solution is correct, use the Second Inaugural Address of Abraham Lincoln as your input text and your program should output: 343 Hint 1: Take a look at the string module. In particular, string.punctuation. If you import this, you may be able to use it to your advantage. Import it as follows from string import punctuation. Figure out how string.punctuation works. Hint 2: The solution to this exercise may make use of some string methods that we looked at back in the strings chapter. Hint 3: Making use of a second list might be a good idea! #### Solution import sys # punctuation is a string of all punctuation characters # punctuation == !"#$%&'()*+, -./:;<=>?@[\]^_{|}~
from string import punctuation as punc

filename = sys.argv

with open(filename, "r") as f:
# Read in text and strip any newline characters.

i = 0
while i < len(punc):
# Replace all punctuation (e.g 'trust' and 'Trust,' are now 'trust' and 'Trust')
text = text.replace(punc[i], "")
i += 1

# Convert everything to lowercase (e.g 'trust' and 'Trust' are now both 'trust')
text = text.lower()

words = text.split()

print(len(words))

## Chapter 11 Solutions

### Question 1

Write a program that reads a file. The file will contain a number of items stocked in a shop and the number of each item available. Your program should parse the file and build a dictionary from this it, then output the stock available in alphabetical order and in a specific format. You can use the following as your input text file:

Oranges 12
Apples 10
Pears 22
Milk 7
Water Bottles 33
Chocolate Bars 11
Energy Drinks 8

Your program output should look like this:

        Apples : 10
Chocolate Bars : 11
Energy Drinks : 8
Milk : 7
Oranges : 12
Pears : 22
Water Bottles : 33

Hint: Find out the length of the longest key.

#### Solution

import sys
from string import punctuation as punc

inventory = {}

filename = sys.argv

with open(filename, "r") as f:
# Read in data line by line
tokens = line.strip().split()

# Each line is now a list called tokens e.g ['Energy', 'Drinks', '8']

# Last element in the list is the value, every thing else is the key
stock = tokens[-1]
product_name = " ".join(tokens[:-1])

inventory[product_name] = stock

# Find longest key for formatting
longest_key = 0
for product in inventory.keys():
if len(product) > longest_key:
longest_key = len(product)

# Format the output with sorted keys
for (product, stock) in sorted(inventory.items()):
print("{:>{}s} : {}".format(product, longest_key, stock))

### Question 2

Write a program that reads a text file. The file is a list of contact details for people. With each contact you're given the name, phone number and email address. Your dictionary should be a mapping from contact names to email and phone number for that contact. Your program should then ask for user input. The input should be a single name. If the name can be found in the contact list then output the name and contact details for that person, otherwise output No contact with that name.

The contact list file is:

Liam 345-45643454 liam@mymail.com
Noah 324-43576413 noah.doe@gmail.com
Tony 987-56543239 tony@hr.mycompany.com
Bert 654-99275234 bert.hertz@support.hertz.co.uk

If the user then enters the following names in this order:

Tony
Noah
John
Annie
Bert

Your program should give the following output:

Name: Tony
Email: tony@hr.mycompany.com
Phone: 987-56543239

Name: Noah
Email: noah.doe@gmail.com
Phone: 324-43576413

No contact with that name

No contact with that name

Name: Bert
Email: bert.hertz@support.hertz.co.uk
Phone: 654-99275234

These details should be printed one by one as the user enters the names, not in bulk as I have above.

#### Solution

import sys
from string import punctuation as punc

contacts = {}

filename = sys.argv

with open(filename, "r") as f:
# Read in data line by line
tokens = line.strip().split()

name = tokens
number = tokens
email = tokens

contacts[name] = {"number": number, "email": email}

lookup_name = input()
while lookup_name:
if lookup_name in contacts:
print("Name: " + lookup_name)
print("Email: " + contacts[lookup_name]["email"])
print("Phone: " + contacts[lookup_name]["number"])
else:
print("No contact with that name exists")
lookup_name = input()

### Question 3

In the previous chapter we tried to count how many words were contained within a piece of text. In this question you are to do the same except you should output how many times each word occurred in the text.

Again, punctuation matters. This time we want to strip any punctuation surrounding a word. Your program should not be case sensitive either, Hello and hello should count as the same word. However, something like John and John's should not be counted as the same word. In other words, you are striping leading and trailing punctuation characters.

Your program should be run as follows:

$py dict_count.py input.txt To test that your solution is correct, use the Second Inaugural Address of Abraham Lincoln as your input text and your program should output (this is a sample from the out): . . . the : 58 oath : 1 of : 22 presidential : 1 office : 1 there : 2 is : 6 less : 2 occasion : 2 for : 9 an : 3 extended : 1 address : 2 than : 4 . . . You need not format the output. The length of your dictionary should be 701. #### Solution import sys from string import punctuation as punc filename = sys.argv word_count = {} with open(filename, "r") as f: text = f.read().strip() text = text.lower() words = text.split() for word in words: if word in punc: word = word.replace(word, "") elif word[-1] in punc: word = word.replace(word[-1], "") if word not in word_count: word_count[word] = 1 else: word_count[word] += 1 for word, count in word_count.items(): print(word + " : " + str(count)) ### Question 4 Write a program that takes two dictionaries and outputs their intersection. The intersection of two dictionaries should be a third dictionary that contains key-value pairs that are present in both of the other two dictionaries. You can hard code these two dictionaries in. They don't need to be read from anywhere. Run your script as follows: $ py intersection.py 

To test if your solution is correct, you can run your program with the two following dictionaries:

d1 = {"k1": True, "k2": True, "k3": True, "k4": True}
d2 = {"k6": True, "k2": True, "k5": True, "k1": True, "k8": True, "k4": True}

Your program should output the following dictionary:

intersection = {"k2": True, "k1": True, "k4": True}

#### Solution

d1 = {"k1": True, "k2": True, "k3": True, "k4": True}
d2 = {"k6": True, "k2": True, "k5": True, "k1": True, "k8": True, "k4": True}

intersection = {}

for key in d1.keys():
if key in d2:
intersection[key] = True

print(intersection)

## Chapter 12 Solutions

### Question 1

Write a module named sorting.py that contains functions that implement both selection and insertion sort i.e your module (sorting.py) should contain a selection_sort(a) function and an insertion_sort(a) function. Your function should return the values, not print them.

Your module should be imported and run as follows in another script called test.py:

import sorting

a = [5, 6, 3, 8, 7, 2]
print(sorting.selection_sort(a))
a = [5, 6, 3, 8, 7, 2]
print(sorting.insertion_sort(a))
$py test.py [2, 3, 5, 6, 7, 8] [2, 3, 5, 6, 7, 8] #### Solution ##### sorting.py def insertion_sort(lst): i = 1 while i < len(lst): v = lst[i] p = i while p > 0 and v < lst[p-1]: lst[p] = lst[p-1] p -= 1 lst[p] = v i += 1 return lst def selection_sort(lst): i = 0 while i < len(lst): p = i j = i + 1 while j < len(lst): if lst[j] < lst[p]: p = j j += 1 tmp = lst[p] lst[p] = lst[i] lst[i] = tmp i += 1 return lst def main(): test_list = [5, 2, 4, 7, 3, 6, 22, 12] print(insertion_sort(test_list)) test_list = [5, 2, 4, 7, 3, 6, 22, 12] print(selection_sort(test_list)) if __name__=="__main__": main() ##### test.py import sorting a = [5, 6, 3, 8, 7, 2] print(sorting.selection_sort(a)) a = [5, 6, 3, 8, 7, 2] print(sorting.insertion_sort(a)) ### Question 2 Write a module called arithmetic.py. This module should include the following functions: • add() • multiply() • divide() • subtract() The add(), multiply() and subtract() functions should be able to handle an arbitrary number of arguments. divide() should only take 2 arguments. Your function should return the calculated values, not print them. Your module should be imported and run as follows in another script called test.py from arithmetic import * print(add(4, 6, 7, 2, 3)) print(add(3, 2)) print(subtract(5, 6, 8, 9)) print(subtract(3, 2)) print(divide(6, 3)) print(multiply(2, 3)) print(multiply(2, 3, 3) $ py test.py
22
5
-18
1
2
6
18

#### Solution

##### arithmetic.py
def add(*argv):
total = 0
for arg in argv:
total += arg

def multiply(*argv):
total = 1
for arg in argv:
total *= arg

def divide(arg1, arg2):
return arg1 // arg2

def subtract(*argv):
total = argv
i = 1
while i < len(argv):
total = total - argv[i]
i += 1

def main():
print(subtract(5, 6, 8, 9))
print(divide(6, 3))
print(multiply(2, 3, 3))

if __name__=="__main__":
main()

### Question 3

Write a function called length() that mimics the len() function. Your function should work for strings, dictionaries and lists. length() should only take 1 argument and return the length of the data-structure passed to it.

Your function should be tested with the following:

a = [5, 3, 4, 1, 2, 3]
print(length(a))

a = []
print(length(a))

d = {}
print(length(d))

d = {"one": True, "two": True}
print(length(d))

s = "This is a string"
print(length(s))

s = ""
print(length(s))
$py test.py 6 0 0 2 16 0 #### Solution def length(iterable): length = 0 for x in iterable: length += 1 return length ### Question 4 Write a function called fib() that calculates and returns the n-th Fibonacci number. Your function should take 1 argument, the Fibonacci number you want to calculate. Your function should be tested with the following: print(fib(3)) print(fib(0)) print(fib(1)) print(fib(10)) print(fib(13)) $ py test.py
3
1
1
89
377

Remember:
Fn = Fn − 1 + Fn − 2

F0 = 1, F1 = 1

#### Solution

def fib(n):
n2 = 1
n1 = 1

if n <= 0:
return 1
elif n == 1:
return 1
else:
count = 0
while count < n:
next_term = n1 + n2
n2 = n1
n1 = next_term
count += 1
return n2

### Question 5

Write a function called read_file() which takes a single argument, a filename (as a string), and returns the contents of the file in list form with each element in the list being a single line from the file.

Your function should be called as follows:

lines = read_file("input.txt")

#### Solution

def read_file(filename):
with open(filename, "r") as f:
return f.readlines()

### Question 6

Write a function procedure called rep_all() that takes 3 arguments, a list of integers and 2 numbers. Your procedure should replace all occurrences of the first number with the second.

Calling your function as follows and printing the list afterwards should produce the following:

a = [4, 2, 3, 3, 7, 8]
rep_all(a, 3, 10)
print(a)
$py test.py [4, 2, 10, 10, 7, 8] #### Solution def rep_all(lst, first, second): for i in range(len(lst)): if lst[i] == first: lst[i] = second return lst ## Chapter 13 Solutions ### Question 1 Answer the following questions: • Why must we add 1 to low when updating it's value? • What is the runtime complexity of Binary Search • What is the space complexity of Binary Search? #### Solution • We must add 1 when updating the low value because if low == mid, we will end up in an infinite loop and that is bad news! • The runtime complexity of Binary Search is O(log(n)) • The space complexity of Binary Search is O(1) ### Question 2 Using what you've learned in this chapter, write a function called insert()that uses an efficient algorithm (hint, hint...) and takes a list and an element as input and returns the index at which that element should be inserted into the list. For example, calling the insert function as such should return the following: insert([1, 3, 4, 5], 2) # RETURNS 1 # i.e. 2 should be inserted at index 1 #### Solution This is a bit of trick question, the solution to this problem is the binary search algorithm! Not only does binary search tell you where an element is in the list, if it isn't there, it tells you what index to insert the element into in order to keep the list sorted! ### Question 3 Again, using what you've learned, write a function called contains() that takes two arguments, a list and an element and returns whether or not that element is contained within that list. For example: contains([1, 3, 5, 7], 3) # RETURNS True ------------------------------ contains([1, 3, 5, 7], 2) #RETURNS False #### Solution def binary_search(arr, elem): low = 0 high = len(arr) while low < high: mid = (low + high) // 2 if arr[mid] < elem: low = mid + 1 else: high = mid return low def contains(arr, elem): index = binary_search(arr, elem) if arr[index] == elem: return True return False ## Chapter 14 Solutions ### Question 2 When should we use the following? • raise • finally • try and except • What is a precondition? • What is a postcondition? #### Solution • Sometimes in our programs we want to raise an exception if a specific condition occurs. This condition might not be one that will crash our program, but we as programmers don't want it occurring. • You can use finally to make sure files or resources are closed or released regardless of whether an exception occurs, even if you don't catch the exception. We use it to clean up our code! • We use try-except to catch errors that may arise in our code which allows us to handle them appropriately rather than our program just crashing. • A precondition is a condition or predicate that must always be true just prior to the execution of some section of code. • A postcondition of an operation is a condition that should be satisfied after the operation has been performed. ## Chapter 15 Solutions ### Question 1 During a study, a number of software engineers were asked what their top 3 favourite programming languages were. Write a program that determines the number of unique languages given as answers during the study. Below is the input file and each line is an answer given by a software engineer: java python c++ python scala c java haskell javascript javascript python c c c++ c# c# haskell java Your program should be run as follows and give the following output: $ py unique.py input.txt
8

#### Solution

I'm using a set method called update() here. This method accepts another iterable (a list in the case below) and adds the elements of the iterable to the set. Remember, sets cannot contain the same element twice!

import sys

with open(sys.argv, "r") as f:
unique_languages = set()
langs = line.strip().split()
unique_languages.update(langs)

print(len(unique_languages))

### Question 2

Write a list comprehension that creates a list containing all the odd numbers between 0 and 10,000.

#### Solution

odd_nums = [num for num in range(0, 10000) if num % 2]

### Question 3

Using the dictionary you downloaded earlier, write a program that builds a list containing all the words that are longer than or equal to 18 characters. You should use a list comprehension to do this!

Your program should be run as follows:

#### Solution

Here I use the all() function. This function returns true when all it's arguments elements are Truthy.

import sys

vowels = set('aeiou')

all_vowels = [word.strip() for word in sys.stdin if all([char in word for char in vowels])]

print(all_vowels)

### Question 5

Using the dictionary you downloaded earlier, write a program that builds a list containing all the words that contain exactly 4 a's and end in 'ian'. For example, the word "alabastrian" should be in the list. You should make good use of a list comprehension to do this!

Your program should be run as follows:

$py two_conditions.py < dictionary.txt #### Solution import sys words = [word.strip() for word in sys.stdin if word.count("a") == 4 and word.strip()[-3:] == "ian"] print(words) ### Question 5 Using the dictionary you downloaded earlier, write a program that builds a list containing all the words in the dictionary whose reverse also occurs. For example, the words "lager" and "regal" should be in the list. You should make good use of comprehensions to do this! Your program should be run as follows: $ py reverse.py < dictionary.txt

Tip: You may want to think about your solution for this. Your program may take a very long time to run if you don't implement a more efficient solution!

#### Solution

I firstly read all words into a set using a set comprehension, why? Set comprehensions work the same way as list comprehensions but we swap the square brackets for curly braces. Let's think about why this is a good idea. The dictionary contains 370,103 words. This means we have a list of 370,103 words. If we did not build a set and built a list instead, then we would have to search the list, word by word for each word in the list. That is an O(n^2) operation or:
3701032
In other words, we would have to go through the list, 136,979,191,449 times. That's almost 137 billion times! Our program would take far too long to run.

When we check if a word is in a set however, we find out straight away since set membership checks are O(1) operations, therefore the runtime of building our reverse_words list is O(n) which is much faster!

import sys

words = {word.strip() for word in sys.stdin}

reverse_words = [word for word in words if word[::-1] in words]

print(reverse_words)

## Chapter 16 Solutions

### Question 1

What is:

• Recursion?
• Memoization?

#### Solution

• A recursive solution is one where the solution to a problem is expressed as an operation on a simplified version of the same problem.
• Memoization is an optimization technique used to speed up our programs by caching the results of expensive function calls.

### Question 2

Write a recursive function that adds up all the numbers from 1 to 100.

#### Solution

def add(n):
if n == 0:
return 0

def main():

if __name__=="__main__":
main()

### Question 3

Write a recursive function that takes an integer as an argument and returns whether or not that integer is a power of 2. Your function should return True or False

#### Solution

def power_of_two(n):
if n == 1 or n == 0:
return True
elif n < 2:
return False
return power_of_two(n/2)

def main():
print(power_of_two(512))

if __name__=="__main__":
main()

### Question 4

Write a recursive function that takes a string as an argument and returns whether or not that string is a palindrome. Your function should return True or False.

#### Solution

def is_palindrome(string):
if len(string) <= 1:
return True
if string == string[-1]:
return is_palindrome(string[1:-1])
return False

def main():
print(is_palindrome("rotor"))

if __name__=="__main__":
main()

### Question 5

Write a recursive function that takes a list of integers as an argument and returns the maximum of that list.

#### Solution

def maximum(lst):
if len(lst) == 1:
return lst
else:
m = maximum(lst[1:])
if m > lst:
return m
else:
return lst

def main():
print(maximum([4, 7, 2, 34, 4, 34, 23, 65, 23, 12]))

if __name__=="__main__":
main()

## Chapter 17 Solutions

### Question 1

Write a class that models a Lamp. The lamp class will have have two methods. The first will initialise the lamp and is called plug_in(). This will set the is_on attribute which is a boolean to False. The second method is called toggle(). If the lamp is off, it will turn it on (set is_on to True) and if the lamp is on, it will turn it off (set is_on to True).

Your class may be imported and used as follows:

>>> from my_lamp import Lamp
>>> la = Lamp()
>>> la.plug_in()
>>> print(la.is_on)
False
>>> la.toggle()
>>> print(la.is_on)
True
>>> la.toggle()
>>> print(la.is_on)
False

#### Solution

class Lamp():
def plug_in(self):
self.is_on = False
def toggle(self):
self.is_on = not self.is_on

def main():
la = Lamp()
la.plug_in()
print(la.is_on)
la.toggle()
print(la.is_on)
la.toggle()
print(la.is_on)

if __name__=="__main__":
main()

### Question 2

Write a class that models a Cirlce. The circle class will have four methods. The first will initialise the circle. The initialise() method should take three parameters, x_coord, y_coord, and radius. This will set the circles x and y coordinates and it radius. The next method is called calc_area(). It should calculate the area of the circle (Look up the formula). The third method is called calc_perimeter() and should calculate the circumference of the circle (Look up the formula). The fourth method is overlaps(). It should take as an argument, another circle and print out whether or not the two circles overlap.

Your class may be imported and used as follows:

>>> from my_circle import Circle
>>> c1 = Cirlce()
>>> c1.initialise(2, 2, 4)
>>> c2 = Circle()
>>> c2.initialise(3, 2, 2)
>>> c1.calc_perimeter()
25.13
>>> c2.calc_perimeter()
12.57
>>> c1.calc_area()
50.27
>>> c1.overlaps(c2)
True

Hint: Your definition of the overlaps methods should be overlaps(self, other_circle)

#### Solution

class Circle():
self.x_coord = x_coord
self.y_coord = y_coord

def calc_area(self):

def calc_perimeter(self):

def overlaps(self, other):
dist = ((self.x_coord - other.x_coord)**2 + (self.y_coord - other.y_coord)**2)**0.5
print(False)
else:
print(True)

### Question 3

Write a class that models a students grades for particular modules. The class will have four methods. The first should initialise the student. The student should have a name and age. The grades should be modelled as a dictionary in which the key is the name of the module and the value is the grade. This should initially be empty. The second method is called add_module() and should add a module to the student object. The third is called update_module_grade() and should update the grade for a particular module. The final method is called show_grades() and should print out the students modules and the grade associated with each module.

Your class may be imported and used as follows:

>>> from my_student import Student
>>> s1 = Student()
>>> s1.initialise("Noah", 19)
Python: 87
Networks: 77

Hint: Make sure you’re initialising the grades dictionary correctly!

#### Solution

class Student():
def initialise(self, name, age):
self.name = name
self.age = age

s = self.name + "s grades are:\n"
s = s + module + ": " + str(grade) + "\n"
print(s)

## Chapter 18 Solutions

### Question 1

Create a BankAccount class. The bank account class should have the following attributes: balance and account_owner. The bank account class should also have deposit and withdraw methods. You should also be able to print the bank account, to display the account owners name and balance. When implemented correctly, you should be able to use the Bank account class as follows:

account = BankAccount("John Smith")
print(account)
>>> Owner: John Smith
>>> Balance: $0 account.deposit(200) print(account) >>> Owner: John Smith >>> Balance:$200
account.withdraw(50)
print(account)
>>> Owner: John Smith
>>> Balance: $150 account.withdraw(200) # Not enough in the account to withdraw 200 print(account) >>> Owner: John Smith >>> Balance:$150

#### Solutions

class BankAccount():
def __init__(self, owner):
self.owner = owner
self.balance = 0

def deposit(self, amount):
self.balance += amount

def withdraw(self, amount):
if self.balance >= amount:
self.balance -= amount

def __str__(self):
return "Owner: {}\nBalance: \${:d}".format(self.owner, self.balance)

### Question 2

Create a Line class. The line class should have four attributes: an x1 and a y1 coordinate for one point on the line and an x2 and a y2 coordinate for the second point on the line. You should be able to do a few things with an instance of a line. You should be able to call the len method on a line to show its length, add two lines together, subtract two lines, multiply a line by an integer, print the line and compare two lines to see if they are equal. In this case equality means both lines are the same length. When implemented correctly, you should be able to use the Line class as follows:

lineOne = Line(2, 2, 4, 4)
lineTwo = Line(1, 1, 3, 3)

len(lineOne)
>>> 2
lineThree = lineOne + lineTwo
len(lineThree)
>>> 4
lineFour = lineOne - lineTwo
len(lineFour)
>>> 1
lineFive = lineTwo * 3
len(liveFive)
>>> 6
print(lineOne)
>>> Line Details:
>>> Point 1: (2, 2)
>>> Point 2: (4, 4)
print(lineOne == lineTwo)
>>> True
print(lineOne == lineFive)
>>> False

#### Solution

class Line():
def __init__(self, x1, y1, x2, y2):
self.x1 = x1
self.x2 = x2
self.y1 = y1
self.y2 = y2

def __len__(self):
# We must use integer division to convert length to an integer
# because __len__ must return an integer
return int(((self.x2 - self.x1)**2 + (self.y2 - self.y1)**2)**0.5)

new_x1 = self.x1 + other.x1
new_x2 = self.x2 + other.x2
new_y1 = self.y1 + other.y1
new_y2 = self.y2 + other.y2
return Line(new_x1, new_y1, new_x2, new_y2)

def __sub__(self, other):
new_x1 = self.x1 - other.x1
new_x2 = self.x2 - other.x2
new_y1 = self.y1 - other.y1
new_y2 = self.y2 - other.y2
return Line(new_x1, new_y1, new_x2, new_y2)

def __mul__(self, amount):
new_x1 = self.x1 * amount
new_x2 = self.x2 * amount
new_y1 = self.y1 * amount
new_y2 = self.y2 * amount
return Line(new_x1, new_y1, new_x2, new_y2)

def __str__(self):
return "Line Details:\nPoint 1: ({:d}, {:d})\nPoint 2: ({:d}, {:d})".format(self.x1, self.y1, self.x2, self.y2)

def __eq__(self, other):
return len(self) == len(other)

## Chapter 19 Solutions

### Question 1

Write a Python program that contains a class called Person. An instance of a Person should have name and age attributes. You should be able to print an instance of the class which, for example, should output John is 28 years old.

Your class should have a method called fromBirthYear() which as parameters should take an age and a birth year. For example, fromBirthYear('John', 1990) should return an instance of Person whose age is 29 (at the time of writing this book, 2019).

Running your program should produce the following:

>>> from my_person import Person
>>> john = Person("John", 28)
>>> print(john)
"John is 28 years old"
"Adam is 29 years old"

Think carefully about what type of method to use.

#### Solution

import datetime

class Person():
def __init__(self, name, age):
self.name = name
self.age = age

def __str__(self):
return "{:s} is {:d} years old".format(self.name, self.age)

@classmethod
def fromBirthYear(cls, name, year_born):
date = datetime.datetime.now()
current_year = date.year
age = current_year - year_born
return cls(name, age)

def main():
john = Person("John", 28)
print(john)

if __name__=="__main__":
main()

### Question 2

Write a Student class that has initializes a student with 3 attributes: name, grades and student_number. Grades should be a dictionary of modules to grades. The student number of the first student instance should be 19343553. The student number of the second student instance should be 19343554 and so on. You should have three methods, add_module() which takes one parameter, a module name, and initialises the grade to 0. The second method should be, update_module() which takes two parameters, the module name and the grade for the module. The final method should allow the user to print a student.

Think carefully about how you will implement the increasing student number.

Running your program should give the following output:

>>> from my_student import Student
>>> john = Student("John")
>>> john.update_module("Python", 88)
>>> print(john)
Name: John
Student Number: 19343553
Python 88
Student Number: 19343554
Java: 60

#### Solution

class Student():
STUDENT_NUMBER = 19343553

def __init__(self, name):
self.name = name
self.student_number = Student.STUDENT_NUMBER
Student.set_next_student_number()

@classmethod
def set_next_student_number(cls):
cls.STUDENT_NUMBER += 1

def __str__(self):
string = "Name: {:s}\nStudent Number: {:d}\nGrades:\n".format(self.name, self.student_number)
return string

def main():
john = Student("John")
john.update_module("Python", 88)
print(john)

if __name__=="__main__":
main()

### Question 3

Modify the Student class to include a method that will validate grades. A grade should be between 0 and 100.

Think carefully about the type of method this should be.

#### Solution

class Student():

# METHODS FROM PREVIOUS EXERCISE HERE

@classmethod
return True
return False

# METHODS FROM PREVIOUS EXERCISE HERE

## Chapter 20 Solutions

### Question 1

Create two classes: Person and Employee. The person class should have name and age attributes. The employee class should have one additional employeeId attribute. The employ should also have clock_in and clock_out methods. When implemented correctly, you should be able to use the two classes as follows:

>>> person = Person("John", 33)
>>> employee = Employee("Tom", 42)
>>> employee.clock_in()
Tom has clocked in.
>>> employee.clock_out()
Tom has clocked out.

Note: You are to use inheritance to implement the employee class.

#### Solution

class Person():
def __init__(self, name, age):
self.name = name
self.age = age

def __str__(self):
return "{:s} is {:d} years old".format(self.name, self.age)

class Employee(Person):
EMPLOYEE_ID = 100

def __init__(self, name, age):
super().__init__(name, age)
self.employeeId = Employee.EMPLOYEE_ID
Employee.set_next_employee_id()

def clock_in(self):
print(self.name + " has clocked in.")

def clock_out(self):
print(self.name + " has clocked out.")

@classmethod
def set_next_employee_id(cls):
cls.EMPLOYEE_ID += 1

def main():
person = Person("John", 33)
employee = Employee("Tom", 42)
employee.clock_in()

print(employee)

employee.clock_out()

if __name__=="__main__":
main()

### Question 2

Create a Shape class. The shape class should have two attributes: num_sides and side_length. It should also have one method called show_type()

Create two other classes: Triangle and Pentagon. Each of these classes should inherit from the Shape class.

Both the Triangle and Pentagon classes should have area() methods.

When implemented correctly, you should be able to use your classes as follows:

>>> shape = Shape(7, 2)
>>> shape.show_type()
I am a Shape
>>> triangle = Triangle(3) # This refers to side length
>>> triangle.show_type()
I am a triangle
>>> triangle.area()
3.9
>>> pent = Pentagon(4) # This refers to side length
>>> pent.show_type()
I am a pentagon
>>> pent.area()
27.53

Note: The triangle is an equilateral triangle and the pentagon is a regular pentagon. You can find the formulae for both of their areas online.

#### Solution

class Shape():
def __init__(self, num_sides, side_length):
self.num_sides = num_sides
self.side_length = side_length

def show_type(self):
print("I am a Shape")

class Triangle(Shape):
def __init__(self, side_length):
super().__init__(3, side_length)

def show_type(self):
print("I am a Triangle")

def area(self):
# Area of an equilateral triangle
return ((3**0.5)/(4)) * self.side_length ** 2

class Pentagon(Shape):
def __init__(self, side_length):
super().__init__(5, side_length)

def show_type(self):
print("I am a Pentagon")

def area(self):
# Area of a regular pentagon (It's a bit tricky)
return 0.25 * (self.num_sides * (self.num_sides + 2 * (self.num_sides**0.5))) ** 0.5 * self.side_length ** 2

def main():
shape = Shape(7, 2)
shape.show_type()

triangle = Triangle(3) # This refers to side length
triangle.show_type()
print(triangle.area())

pent = Pentagon(5) # This refers to side length
pent.show_type()
print(pent.area())

if __name__=="__main__":
main()

### Question 3

Create a Clock class. It should have three attributes: hour, minute, and second. It should also have a method called show_time() that displays the time in 24 hour time. It should also have a method called tick() that advances the time by 1 second.

Create a Calendar class. It should have three attributes: day, month, and year. It should have two methods, one called show_date() and the other called next() that advances the date to the next day.

Create a third class called CalendarClock that inherits from both Clock and Calendar. It should have one method called tick() that advances the time by 1 second, and a second method, show_date_time() that shows the date and time.

When implemented correctly, you should be able to use your classes as follows:

>>> clock = Clock(23, 59, 59)
>>> clock.show_time()
The time is 23:59:59
>>> clock.tick()
>>> clock.show_time()
The time is 00:00:00
>>> cal = Calendar(30, 12, 2019)
>>> cal.show_date()
The date is 30/12/2019
>>> cal.next()
>>> cal.show_date()
The date is 31/12/2019
>>> calClock = CalendarClock(31, 12, 2019, 23, 59, 59)
>>> calClock.show_date_time()
The date is 31/12/2019 and the time is 23:59:59
>>> calClock.tick()
>>> calClock.show_date_time()
The date is 01/01/2020 and the time is 00:00:00

Note: There are a few ways of completing this question, however I want you to use multiple inheritance. If you do, then the code for CalendarClock should be quite short.

#### Solution

class Clock():
def __init__(self, hour, minute, second):
self.hour = hour
self.minute = minute
self.second = second

def tick(self):
if self.second == 59:
self.second = 0
if self.minute == 59:
self.minute = 0
self.hour = 0 if self.hour == 23 else self.hour + 1
else:
self.minute += 1
else:
self.second += 1

def __str__(self):
return "{:02d}:{:02d}:{:02d}".format(self.hour, self.minute, self.second)

class Calendar():
MONTHS = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

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

def leapyear(self, year):
if year % 4:
# Not a leap year
return False
else:
if year % 100:
return True
else:
if year % 400:
return False
return True

def next(self):
months = Calendar.MONTHS
max_days = months[self.month - 1]
if self.month == 2:
max_days += self.leapyear(self.year)
if self.day == max_days:
self.day = 1
if self.month == 12:
self.month = 1
self.year += 1
else:
self.month += 1
else:
self.day += 1

def __str__(self):
return "{}/{}/{}".format(self.day, self.month, self.year)

class CalendarClock(Clock, Calendar):
def __init__(self, day, month, year, hour, minute, second):
Calendar.__init__(self, day, month, year)
Clock.__init__(self, hour, minute, second)

def tick(self):
Clock.tick(self)
if CalendarClock.is_new_day(self.hour, self.minute, self.second):
Calendar.next(self)

@staticmethod
def is_new_day(h, m, s):
return h == 0 and m == 0 and s == 0

def __str__(self):
return Calendar.__str__(self) + ", " + Clock.__str__(self)

def main():
x = CalendarClock(31, 12, 1998, 23, 59, 59)
print(x)
x.tick()
print(x)
x.tick()
print(x)

if __name__=="__main__":
main()

## Chapter 21 Solutions

### Question 1

You are given two strings S and T. Both strings either contain alphanumeric characters or a '#' character. A '#' means backspace. Your goal is to use your knowledge of stacks to design a function that will decide whether both strings are equal after the back space operation has been applied. For example:

123456789101112131415Input: S = "xy#z", T = "xw#z"
Output: True
Explanation: When the backspace operation is applied, both strings become "xz"

Input: S = "abcd##", T = "acbd##"
Output: False
Explanation: S becomes 'ab' and T becomes 'ac' which are not the same

Input: S = "z##y", T="#d#y"
Output: True
Explanation: Both strings become 'y'

Input: S = "er##", T = "u#u#"
Output: true
Explanation: Both S and T become '' (empty string)

#### Solution

Assuming the Stack class exists:

def backspace(s, t):
s_stack = Stack()
for char in s:
if not char == "#":
s_stack.push(char)
else:
if not s_stack.isEmpty():
s_stack.pop()

t_stack = Stack()
for char in t:
if not char == "#":
t_stack.push(char)
else:
if not t_stack.isEmpty():
t_stack.pop()

return s_stack == t_stack

def main():
s, t = "xy#z", "xw#z"
print(backspace(s, t))

s, t = "abcd##", "acbd##"
print(backspace(s, t))

s, t = "z##y", "#d#y"
print(backspace(s, t))

s, t = "er##", "u#u#"
print(backspace(s, t))

if __name__=="__main__":
main()

### Question 2

It is possible to create a queue through the use of two stacks. Implement a queue class like above, except rather than using a list to implement the queue you use two stacks.

#### Solution

Assuming the Stack class from before exists:

class Queue:
def __init__(self):
self.s1 = Stack()
self.s2 = Stack()

def enqueue(self, elem):
# Move all elements in s1 to s2
while not self.s1.isEmpty():
self.s2.push(self.s1.pop())

# push item onto s1
self.s1.push(elem)

# Push everything else back onto s1 from s2
while not self.s2.isEmpty():
self.s1.push(self.s2.pop())

def dequeue(self):
return self.s1.pop()

def main():
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

if __name__=="__main__":
main()

### Question 3

It is also possible to create a stack through the use of two queues. Implement a stack class like the one we have seen earlier, except rather than using a list to implement the stack, use two queues.

#### Solution

Assuming the Queue class from this chapter exists:

class Stack:
def __init__(self):
self.q1 = Queue()
self.q2 = Queue()
self.size = 0

def push(self, elem):
self.q1.enqueue(elem)
while not self.q2.isEmpty():
x = self.q2.dequeue()
self.q1.enqueue(x)

# Swap the queue references
self.q1, self.q2 = self.q2, self.q1

def pop(self):
return self.q2.dequeue()

def isEmpty(self):
return self.q2.isEmpty()

def main():
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.isEmpty())
print(stack.pop())
print(stack.pop())
print(stack.isEmpty())

if __name__=="__main__":
main()

## Chapter 22 Solutions

### Question 1

We talked earlier about the run-time complexities of the Linked List methods we implemented. I mentioned that we could improve their complexities.

Currently, the add() method has a run-time complexity of O(n).

Change the implementation of the add() method so that it's run-time complexity is O(1).

#### Solution

Our solution is to add the new element to the front of the linked list rather than the end

class Node:
def __init__(self, elem):
self.elem = elem
self.next = None

def __init__(self):

else:
self.head = new_head

### Question 2

Change the implementation of the add() or remove() methods on the Linked List class in order to achieve a Linked List that behaves like:

• A Stack
• A Queue

Try to give optimized implementations of add() and/or remove() when doing this.

#### Solution

To implement a stack

class Node:
def __init__(self, elem):
self.elem = elem
self.next = None

def __init__(self):

# Mimics the stack push() method
else:

# Mimics the stack pop() method
def delete(self):
return None
return elem

def main():
print(ll.delete())
print(ll.delete())

if __name__=="__main__":
main()

To implement a Queue

class Node:
def __init__(self, elem):
self.elem = elem
self.next = None

def __init__(self):

# Mimics the queue enqueue() method
new_node = Node(elem)

if self.end == None:
return
self.end.next = new_node
self.end = new_node

# Mimics the queue dequeue() method
def delete(self):
return

self.end = None
return tmp.elem

def main():
print(ll.delete())
print(ll.delete())

if __name__=="__main__":
main()

### Question 3

Another useful method our Linked List class may have is a length() method. That is, it returns the number of elements in the linked list.

Implement the length() method.

#### Solution

There are two solutions to this question. The first is to iterate over every node in the linked list, adding 1 to a length variable each time then returning that number when you reach the end. This approach means the length() method has a runtime complexity of O(n).

A better solution is to add a size attribute to the LinkedList class. This should be incremented by 1 every time we add an element and decremented by 1 every time we remove an element. This means the length method has a runtime of O(1) as when length() is called, we just return self.size.

class Node:
def __init__(self, elem):
self.elem = elem
self.next = None

def __init__(self):
self.size = 0

self.size += 1
else:
self.size += 1

def delete(self, val):
return
self.size -= 1
return val

while curr.next != None and curr.next.elem != val:
curr = curr.next

if curr.next == None:
return
else:
curr.next = curr.next.next
self.size -= 1
return val

def length(self):
return self.size

def main():
print(ll.length())

print(ll.length())

print(ll.length())

ll.delete(7) # Should return None - doesn't exist
ll.delete(5)
print(ll.length())

ll.delete(6)
print(ll.length())

if __name__=="__main__":
main()

### Question 4

If you thought carefully about your implementation of the length() method from the previous exercise then you might be able to skip this question. However, I'm not expecting that you did.

If my guess is correct, your length() method iterates over each element in the list, adding 1 to your length each time until you reach the end of the list. This will give your length() method a run-time complexity of O(n).

We can do better than that though. How might you change the Linked List class so that the run-time complexity of your length() method is O(1)?

#### Solution

The answer to this question is the solution to the last question.

### Question 5

The height (depth) of a Tree is the number of edges on the longest path from the root node to leaf node.

You should write a recursive method to find the height of any given binary search tree

#### Solution

    def height(self):
if self.root is None:
return 0
# We subtract 1 because the root node height is 0 not 1
return self.recursive_height(self.root) - 1

def recursive_height(self, node):
if node == None:
return 0
return 1 + max(self.recursive_height(node.left), self.recursive_height(node.right))

### Question 6

This question is very difficult

Consider what happens when we add elements to the tree in the following order: {2, 5, 7, 12, 13}. We end up with a Linked List. That means that our search and insert is no longer O(log n). It's now O(n). This isn't really that great for us.

We can however, make an optimization to our binary search tree so that our search and insert are always O(log n), regardless of what order we enter the elements.

The optimization is that the difference between height of the left and right subtrees is no greater than one for all nodes. When the difference between left and right subtrees height is no greater than 1, we say the tree is balanced. This means, if we insert or remove an element and the height between left and right subtrees becomes greater than 1 then we must rearrange the nodes.

This optimization means that our binary search tree will become self balancing.

This type of self balancing binary search tree has a special name. It's called an AVL Tree.

Remember: This question is very difficult, I don't expect you to be able to answer this, but I encourage you to give it a go!

#### Solution

class Node():
def __init__(self, value):
self.value = value
self.left = None
self.right = None

class AVLTree():
def __init__(self):
self.node = None
self.height = -1
self.balance = 0

def insert(self, value):
node = Node(value)
# Tree is empty, initialize root
if self.node == None:
self.node = node
self.node.left = AVLTree()
self.node.right = AVLTree()
# Insert into left subtree
elif value < self.node.value:
self.node.left.insert(value)
# Insert into right subtree
elif value > self.node.value:
self.node.right.insert(value)
# Rebalance if needed
self.rebalance()

def remove(self, value):
if self.node != None:
# Found the node delete it
if self.node.value == value:
# Node is a leaf node - Just remove
if not self.node.left.node and not self.node.right.node:
self.node = None
# Only one subtree - the right subtree - replace root with that
elif not self.node.left.node:
self.node = self.node.right.node
# Only one subtree - the left subtree - replace root with that
elif not self.node.right.node:
self.node = self.node.left.node
else:
# Find successor as smallest node in the right subtree or
# predecessor as largest node in left subtree
successor = self.node.right.node
while successor and successor.left.node:
successor = successor.left.node

if successor:
self.node.value = successor.value
# Delete successor from the replaced node right subtree
self.node.right.remove(successor.value)
# Remove from left subtree
elif value < self.node.value:
self.node.left.remove(value)
# Remove from right subtree
elif value > self.node.value:
self.node.right.remove(value)
# Rebalance if needed
self.rebalance()

def is_balanced(self):
if self.node is None:
return True
# Left subtree height
lst = self.node.left.height
# Right subtree height
rst = self.node.right.height
if (abs(lst - rst) <= 1) and self.node.left.is_balanced() is True and self.node.right.is_balanced() is True:
return True
return False

def rebalance(self):
self.update_heights()
self.update_balances()
# If balance is < -1 or > 1 then rotations are still necessary to perform
while self.balance < -1 or self.balance > 1:
# Left subtree is larger than right subtree so rotate to the left
if self.balance > 1:
if self.node.left.balance < 0:
self.node.left.rotate_left()
self.update_heights()
self.update_balances()
self.rotate_right()
self.update_heights()
self.update_balances()

# Right subtree larger than left subtree so rotate to the right
if self.balance < -1:
if self.node.right.balance > 0:
self.node.right.rotate_right()
self.update_heights()
self.update_balances()
self.rotate_left()
self.update_heights()
self.update_balances()

def update_heights(self):
# Height is max height of left or right subtrees + 1 for the root
if self.node:
if self.node.left:
self.node.left.update_heights()
if self.node.right:
self.node.right.update_heights()
self.height = 1 + max(self.node.left.height, self.node.right.height)
else:
self.height = -1

def update_balances(self):
# Calculate the balance factor of the tree
# Balance factor calculated as follows:
#     BF = height(left_subtree) - height(right_subtree)
if self.node:
if self.node.left:
self.node.left.update_balances()
if self.node.right:
self.node.right.update_balances()
self.balance = self.node.left.height - self.node.right.height
else:
self.balance = 0

def rotate_right(self):
# Set self as the subtree of the left subtree
new_root = self.node.left.node
new_left_sub = new_root.right.node
old_root = self.node

self.node = new_root
old_root.left.node = new_left_sub
new_root.right.node = old_root

def rotate_left(self):
# Set self as the left subtree of the right subtree
new_root = self.node.right.node
new_left_sub =new_root.left.node
old_root = self.node

self.node = new_root
old_root.right.node = new_left_sub
new_root.left.node = old_root`

Previous Chapter