Optional Homework Problems for Spring Break
C200 Spring 2020 (C) Dalkilic
Introduction
This homework is written a little different than the others, since it’s optional.
Create a folder Optional in your repository and under it add the programs:
• letters.py
• travel.py, distance.txt
• sorting.py
• recur.py
When the assignment is in the gradebook, it will be out of 0. So if you choose
not to do this assignment, you will not get penalized. This will add points to
your homework grade. In the gradebook, it will read as some number over
zero, ex. 99/0. On the gradesheet that will be put in your repo, we will give
it a max score, so you can see what was the total possible points you could
have obtained.
The last day of submission for this is Wednesday March 25th, 2020
at 11:00 P.M..
1
(1) Rewrite the following recursive program below using tail recursion.
1 def foo(a):
2 if a:
3 if a[0] in x:
4 return foo(a[1:])
5 else:
6 return a[0] + foo(a[1:])
7 else:
8 return ""
9
10 def foot(a,t=""):
11 """
12 TODO:
13 Function must return a string.
14
15 Implementation must be tail -recursive.
16 """
17 # TODO: Implement
18 pass
19
20 if __name__ == "__main__":
21 x = [’a’,’e’,’i’,’o’,’u’]
22
23 s = "the lazy dog jumped over the sleeping fox ←↩
quietly"
24 print(foo(s))
25 print(foot(s))
The output
th lzy dg jmpd vr th slpng fx qtly
th lzy dg jmpd vr th slpng fx qtly
Name this program letters.py and the implementation must be done tail-
recursively.
2
(2) In this problem, you’ll read in locations on a map, then compute the total
distance taken. We’ll use Euclidean distance: Let p1 = (x1, y1), p2 = (x2, y2),
then the distance is:
d(p1, p2) =
√
(x2 − x1)2 + (y2 − y1)2 (1)
Point Value
A (1,3)
B (20,10)
C (3,30)
D (40,20)
E (10,10)
Create an ASCII of the data so that you can read it in as a file. Assume
the person travels from E to B to A to D to C. Write a program that calculates
the distance traveled. Your function should take the string “EBADC” and
(hint: dictionary) to calculate the total distance.
1 import math
2
3 def d(s,xdic):
4 # TODO: Implement Function
5 pass
6
7 if __name__ == "__main__":
8 xlst = {}
9 with open("Optional/distance.txt","r") as file:
10 for l in file.readlines ():
11 k,v = l.strip ().split(" ")
12 xlst[k] = eval(v) #converts string to ←↩
tuple
13 print(xlst)
14 print("Travel {0} = {1}".format("E->B->A->D->C", d←↩
("EBADC",xlst)))
The output
{’A’: (1, 3), ’B’: (20, 10), ’C’: (3, 30), ’D’: (40, 20), ’E’: (10, 10)}
Travel E->B->A->D->C = 111.1200872971555
3
Name this program travel.py and also include distance.txt in your Optional
folder. You are not allowed to modify any code outside of the function d.
Note: each line should look like the following:
Z (200,200)
There is only a single space, which lies between the letter and the paren-
theses. That is how it should be read
4
3. In the following problem, you’ll use the Python eval() function that turns
a string into a valid Python expression. Specifically, you’ll build a lambda
expression to sort a string, then use the eval of it to dynamically sort a set
of randomly generated 3-tuples.
1
2 import random as rn
3
4 xlst = []
5
6 for i in range(rn.randint (1,10)):
7 xlst.append ((rn.randint (1 ,100),rn.randint (1 ,100),←↩
rn.randint (1 ,100)))
8
9 print("Original List")
10 print(xlst)
11 print("You can order by one of three dimensions 0,1,2"←↩
)
12 x = input("order: ") # This will be a string that a ←↩
"0", "1", or "2".
13 """
14 Only changes go below
15 """
16
17 # TODO: Complete Function
18
19 """
20 Only changes go above
21 """
22 print(xlst)
5
Here is are a couple of runs:
Run 1
Original List
[(38, 33, 8), (21, 80, 15), (70, 81, 84), (64, 51, 62), (15, 83, 17),
(32, 37, 36), (77, 57, 50), (67, 37, 78), (18, 89, 51), (23, 39, 15)]
You can order by one of three dimensions 0,1,2
order: 1
[(38, 33, 8), (32, 37, 36), (67, 37, 78), (23, 39, 15), (64, 51, 62),
(77, 57, 50), (21, 80, 15), (70, 81, 84), (15, 83, 17), (18, 89, 51)]
Run 2
Original List
[(53, 2, 75), (73, 51, 66), (36, 7, 19)]
You can order by one of three dimensions 0,1,2
order: 2
[(36, 7, 19), (73, 51, 66), (53, 2, 75)]
Name this program sorting.py
6
4. Here is a pair of recursive equations:
x(0) = 4 (2)
x(n) = 2n− 1 + y(n− 1) (3)
y(0) = 3 (4)
y(n) = 3n− 2 + x(n− 1) (5)
Complete the Python program:
1 def x(n):
2 """
3 Implements the recursive function based on ←↩
equations 2 and 3 above.
4 """
5 # TODO: Implement function
6 pass
7
8 def y(n):
9 """
10 Implements the recursive function based on ←↩
equations 4 and 5 above.
11 """
12 # TODO: Implement function
13 pass
14
15 if __name__ == "__main__":
16 for i in range (0,10):
17 print(i,y(i))
0 3
1 5
2 8
3 15
4 23
5 35
6 48
7 65
7
8 83
9 105
Name this program recur.py. Both functions must be recursive.
8