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
