#### Help support the author by donating or purchasing a PDF copy of the book from EJunkie!

# 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 2^{22} as 4^{2}, instead it is evaluated as 2^{4}.

### 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: "))
r1 = int(input("Circle-1 radius: "))
x2 = int(input("Circle-2 x: "))
y2 = int(input("Circle-2 y: "))
r2 = int(input("Circle-2 radius: "))
# Raising a number to the power of 0.5
# is the same as square root
distance = ((x2 - x1)**2 + (y2 - y1)**2)**0.5
radius_total = r1 + r2
if distance >= radius_total:
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: *F*_{n} = *F*_{n − 1} + *F*_{n − 2}

*F*_{0} = 0, *F*_{1} = 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 = "$#@^"
password_strength = 0
i = 0
while i < len(password):
curr = password[i]
if curr.isdigit() and not contains_digit:
password_strength += 1
contains_digit = True
elif curr.isalpha() and curr.islower() and not contains_lower:
password_strength += 1
contains_lower = True
elif curr.isalpha() and curr.isupper() and not contains_upper:
password_strength += 1
contains_upper = True
elif curr in special_chars and not contains_special:
password_strength += 1
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*π**r*^{2}

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

Hint: Formatting is key here

```
# EXAMPLE INPUT
1
1
10
# EXAMPLE OUTPUT
Radius Area Volume
---------- ---------- ------------
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("Radius", "Area", "Volume"))
print("{:>10s}{:>16s}{:>16s}".format("----------", "----------", "----------"))
i = 0
while i < end:
area = 4 * 3.14 * radius ** 2
volume = (4/3) * 3.14 * radius ** 3
print("{:>10.1f}{:>16.2f}{:>16.2f}".format(radius, area, volume))
radius += inc
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[0]:
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())
# YOUR CODE HERE
# 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[0]
numbers[0] = 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:

- Insertion sort
- Selection sort

Give your answer in Big O notation

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

- Selection sort
- Insertion sort

Give your answer in Big O notation

#### 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
line = sys.stdin.readline()
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[1]
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
AddE
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[1]
with open(filename, "r") as f:
word = f.readline().strip()
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[1]
with open(filename, "r") as f:
# Read in text and strip any newline characters.
text = f.read().strip()
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[1]
with open(filename, "r") as f:
# Read in data line by line
for line in f.readlines():
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[1]
with open(filename, "r") as f:
# Read in data line by line
for line in f.readlines():
tokens = line.strip().split()
name = tokens[0]
number = tokens[1]
email = tokens[2]
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[1]
word_count = {}
with open(filename, "r") as f:
text = f.read().strip()
text = text.lower()
words = text.split()
for word in words:
if word[0] in punc:
word = word.replace(word[0], "")
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
return total
def multiply(*argv):
total = 1
for arg in argv:
total *= arg
return total
def divide(arg1, arg2):
return arg1 // arg2
def subtract(*argv):
total = argv[0]
i = 1
while i < len(argv):
total = total - argv[i]
i += 1
return total
def main():
print(add(4, 6, 7, 2, 3))
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**: *F*_{n} = *F*_{n − 1} + *F*_{n − 2}

*F*_{0} = 1, *F*_{1} = 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*(*l*(**o**g*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[1], "r") as f:
unique_languages = set()
for line in f.readlines():
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:

`$ py long_words.py < dictionary.txt`

#### Solution

```
import sys
long_words = [word.strip() for word in sys.stdin if len(word.strip()) >= 18]
print(long_words)
```

### Question 4

Using the dictionary you downloaded earlier, write a program that builds a list containing all the words that contain every vowel (a, e, i, o and u). For example, the word "equation" 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 vowels.py < dictionary.txt`

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

370103^{2}

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
return n + add(n-1)
def main():
print(add(100))
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[0] == 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[0]
else:
m = maximum(lst[1:])
if m > lst[0]:
return m
else:
return lst[0]
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():
def initialise(self, x_coord, y_coord, radius):
self.x_coord = x_coord
self.y_coord = y_coord
self.radius = radius
def calc_area(self):
print(3.14 * self.radius**2)
def calc_perimeter(self):
print(2 * 3.14 * self.radius)
def overlaps(self, other):
dist = ((self.x_coord - other.x_coord)**2 + (self.y_coord - other.y_coord)**2)**0.5
if dist > self.radius + other.radius:
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)
>>> s1.add_module("Python")
>>> s1.update_module_grade("Python", 87)
>>> s1.add_module("Networks")
>>> s1.update_module_grade("Networks", 77)
>>> s1.show_grades()
Noahs grades are:
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
self.grades = {}
def add_module(self, module):
self.grades[module] = 0
def update_module_grade(self, module, grade):
self.grades[module] = grade
def show_grades(self):
s = self.name + "s grades are:\n"
for module, grade in self.grades.items():
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)
def __add__(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 __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 = Person.fromBirthYear("Adam", 1990)
>>> print(adam)
"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)
adam = Person.fromBirthYear("Adam", 1990)
print(adam)
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.add_module("Python")
>>> john.update_module("Python", 88)
>>> print(john)
Name: John
Student Number: 19343553
Grades:
Python 88
>>> adam = Student("Adam")
>>> adam.add_module("Java")
>>> adam.update_module("Java", 60)
>>> print(adam)
Name: Adam
Student Number: 19343554
Grades:
Java: 60
```

#### Solution

```
class Student():
STUDENT_NUMBER = 19343553
def __init__(self, name):
self.name = name
self.grades = {}
self.student_number = Student.STUDENT_NUMBER
Student.set_next_student_number()
def add_module(self, module_name):
if not module_name in self.grades:
self.grades[module_name] = 0
def update_module(self, module_name, grade):
if module_name in self.grades:
self.grades[module_name] = grade
@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)
for module, grade in self.grades.items():
string += "{:s}: {:d}\n".format(module, grade)
return string
def main():
john = Student("John")
john.add_module("Python")
john.update_module("Python", 88)
print(john)
adam = Student("Adam")
adam.add_module("Java")
adam.update_module("Java", 60)
print(adam)
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
def isValidGrade(cls, grade):
if grade >= 0 and grade <= 100:
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.

*This might be a little tricky, you'll have to think about this*.

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

*This might be a little tricky, you'll have to think about this*.

#### 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
class LinkedList:
def __init__(self):
self.head = None
def add(self, elem):
if self.head == None:
self.head = Node(elem)
else:
new_head = Node(elem)
new_head.next = self.head
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
class LinkedListStack:
def __init__(self):
self.head = None
# Mimics the stack push() method
def add(self, elem):
if self.head == None:
self.head = Node(elem)
else:
new_head = Node(elem)
new_head.next = self.head
self.head = new_head
# Mimics the stack pop() method
def delete(self):
if self.head is None:
return None
elem = self.head.elem
self.head = self.head.next
return elem
def main():
ll = LinkedListStack()
ll.add(5)
ll.add(6)
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
class LinkedListQueue:
def __init__(self):
self.head = self.end = None
# Mimics the queue enqueue() method
def add(self, elem):
new_node = Node(elem)
if self.end == None:
self.head = self.end = new_node
return
self.end.next = new_node
self.end = new_node
# Mimics the queue dequeue() method
def delete(self):
if self.head == None:
return
tmp = self.head
self.head = tmp.next
if self.head == None:
self.end = None
return tmp.elem
def main():
ll = LinkedListQueue()
ll.add(5)
ll.add(6)
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
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def add(self, elem):
if self.head == None:
self.head = Node(elem)
self.size += 1
else:
new_head = Node(elem)
new_head.next = self.head
self.head = new_head
self.size += 1
def delete(self, val):
if self.head == None:
return
if self.head.elem == val:
self.head = self.head.next
self.size -= 1
return val
curr = self.head
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():
ll = LinkedList()
print(ll.length())
ll.add(5)
print(ll.length())
ll.add(6)
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
```

#### Help support the author by donating or purchasing a PDF copy of the book from EJunkie!

Previous Chapter