This lab covers sorting algorithms and regular expressions.
Instructions:
Modify this notebook by adding the Python code described below.
Test your code using the menu item Cell ► Run All
Submit the notebook (the .ipynb file) to the appropriate dropbox on the course web site.
Q1: Write a function lswap(l,i,j) that exchanges the ith and jth elements of the list l. Your function may not use any other functions.
def lswap(l,i,j):
l[i],l[j]=l[j],l[i]
Q2: Write a funtion bsort(l) that uses a bubble sort algorithm and returns the list l sorted in icreasing order. Your function may only use the functions len, range, lswap, bsort.
def bsort(l):
n=len(l)
for i in range(n):
for j in range(i,n):
if l[j]<l[i]:
lswap(l,i,j)
return l
# or:
def bsort(l):
if len(l) <= 1:
return l
for i in range(len(l)):
if l[i] < l[0]:
lswap(l,0,i)
return [l[0]]+bsort(l[1:])
Q3: Write a function merge(a,b) that returns the merge of lists a and b. a and b are sorted in increasing order as should be the return value. Your function may only use the functions pop and append.
def merge(a,b):
l=[]
while a and b:
if a[0] < b[0]:
l.append(a.pop(0))
else:
l.append(b.pop(0))
return l+a+b
Q4: Write a function msort(l) that uses the merge-sort algorithm to sort and return the list l. Your function may only use the functions len(), merge() and msort().
def msort(l):
n=len(l)
if n <= 1:
return l
else:
p = n // 2
return merge(msort(l[:p]),msort(l[p:]))
Q5: The file words.txt on the course web site is a text file containing one word on each line. Copy this file to the same directory (folder) where you have your notebook file.
Read the file words.txt and set the variable words to a list consisting of all of the lines in the file, one line per list element, with any leading and trailing whitespace removed.
words=list(map(lambda s: s.strip(),open('words.txt')))
Q6: Use a regular expression to find the words in words that begin and end with a vowel and put these words in the list w1. Vowels are a, e, i, o and u.
import re
w1=[s for s in words if re.search(r'^[aeiou].*[aeiou]$',s)]
Q7: Use a regular expression to find the words in words where the first letter is the same as the last and put these words in the list w2.
w2=[s for s in words if re.search(r'^(.).*\1$',s)]
Q8: Use a regular expression to find the words in words that have a repeated consonant (two or more consonants next to each other) and put these words in the list w3. You may assume any letter that is not a vowel is a consonant.
w3=[s for s in words if re.search(r'([^aeiou])\1{1,}',s)]
# lab validation code; do not modify
def labcheck():
def checksorted(l):
assert all((l[i] <= l[i+1] for i in range(len(l)-1))), \
"result is not sorted: {}".format(l)
def checkfunctions(f,l):
u=[s for s in f.__code__.co_names if s not in l]
assert not u, "You used the function(s): {}".format(u)
def checkhash(l,n):
import hashlib
# print(hashlib.md5(''.join(l).encode('utf8')).hexdigest())
assert hashlib.md5(''.join(l).encode('utf8')).hexdigest() == n, \
'wrong values in list: {} ... {}'.format(l[0],l[-1])
def q1():
import random
l=random.choices(range(10),k=10)
a,b=random.choices(range(10),k=2)
old=l[a],l[b]
lswap(l,a,b)
assert (l[b],l[a]) == old
checkfunctions(lswap,[])
def q2():
import random
l=random.choices(range(-10,10),k=random.randint(10,20))
l=bsort(l)
checksorted(l)
checkfunctions(bsort,('len', 'range', 'lswap', 'bsort'))
def q3():
import random
l1,l2=(sorted(random.choices(range(-10,10),k=random.randint(5,10)))
for i in (1,2))
l=sorted(l1+l2)
assert merge(l1,l2) == l, "merge() of {} and {} is not: {}".format(l1,l2,l)
checkfunctions(merge,('pop','append'))
def q4():
import random
l=random.choices(range(-10,10),k=random.randint(10,20))
l=msort(l)
checksorted(l)
checkfunctions(msort,('len','merge','msort'))
def q5():
checkhash(words,'ea78a7c0a9e1d1630915161ef433507c')
def q6():
checkhash(w1,'e2a6fc5cd2a28e86f96ccd691eeb532a')
def q7():
checkhash(w2,'c4d866edd7b1455045ab452d350780c8')
def q8():
checkhash(w3,'47a20196ea05f6ad05bee551f7287af7')
for i,s in ((i,'q%d'%i) for i in range(1,20)):
if s in locals():
try:
locals()[s]
print("Question {} OK.".format(i))
except Exception as e:
print("Failed check for Question {}: {}".format(i,e))
labcheck()