- nthEmirpsPrime [10 pts]
This time, you'll be writing an nthPrime-type function without pre-determined helper functions! (Though writing helper functions is still a great idea and we encourage it.)
Write the function nthEmirpsPrime(n) that takes a non-negative int n and returns the nth "Emirp prime", where an Emirp prime is a prime number which becomes a different prime number when its decimal digits are reversed. For example, 13 is an Emirp prime because when we reverse the digits we get 31, which is also prime. 2, 3, 5, 7, and 11 are all examples of primes that are not Emirp primes because they are the same prime when the digits are reversed. Here are the first several Emirp primes: 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199,... So nthEmirpsPrime(0) returns 13.
Note: you are not allowed to use strings in this problem. You should only use concepts from when we learned loops.
Aside: in case you missed it, emirp is prime spelled backwards. We didn't make this up (check out "emirp" on Wikipedia)!
- areAnagrams(s1, s2) [10 pts]
Write the function areAnagrams(s1, s2) that takes two strings, s1 and s2,
that you may assume contain only upper and/or lower case letters, and returns True if the strings are anagrams, and False otherwise. Two strings are
anagrams if each can be reordered into the other. Treat "a" and "A" as
the same letters (so "Aba" and
"BAA" are anagrams). You may not use sort() or sorted() or any other
list-based functions or approaches. Hint: you may use s.count(), which
could be quite handy here.
- longestCommonSubstring(s1, s2) [25 pts]
Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:
longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
longestCommonSubstring("abcdef", "ghi") returns "" (the empty string)
If there are two or more longest common substrings, return the
lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:
longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"
Hint: Start by solving a simpler problem: how would you find and return the longest-matching substring starting from the beginning of each of the strings? Under this restriction:
longestCommonSubstringFromStart("abcdef", "abqrcdest") returns "ab"
Now imagine you have a helper function that implements that simpler version of longestCommonSubstring. With that helper function, you can solve longestCommonSubstring by generating all possible combinations of the starting places of s1 and s2, and calling the helper function with each. This can help you identify which sequence of matching characters is the longest.
- bestStudentAndAvg(gradebook) [25 pts]
Background: for this problem, a "gradebook" is a multiline string where each row contains a student's name (one
word, all lowercase) followed by one or more comma-separated integer grades. A gradebook
always contains at least one student, and each row always contains at least one grade. Gradebooks
can also contain blank lines and lines starting with the "#" character, which should be ignored.
With this in mind, write the function
bestStudentAndAvg(gradebook), that takes a gradebook and
finds the student with the best average (ignoring the case where there is a tie) and returns a
string
of that student's name followed by
a colon (":") followed by his/her average (rounded using the provided roundHalfUp). For example, here is
a test case:
gradebook = """
# ignore blank lines and lines starting with #'s
wilma,91,93
fred,80,85,90,95,100
betty,88
"""
assert(bestStudentAndAvg(gradebook) == "wilma:92"))
Note: you most likely will want to use both s.split(",") and s.splitlines() in your solution.
- patternedMessage(message, pattern) [30 pts]
Write the function patternedMessage(message, pattern) that takes two strings, a message and a pattern, and returns a string produced by replacing the non-whitespace characters in the pattern with the non-whitespace characters in the message (where any leading or trailing newlines in the pattern are first removed). As a first example:
| call | result |
patternedMessage("Go Pirates!!!", """
***************
****** ******
***************
""")
|
GoPirates!!!GoP
irates !!!GoP
irates!!!GoPira
|
Here, the message is "Go Pirates!!!" and the pattern is a block of asterisks with a few missing in the middle. Notice how the whitespace in the pattern is preserved, but the whitespace in the message is removed. Again, note that any leading or trailing newlines in the pattern are removed.
Here is another example:
| call | result |
patternedMessage("Three Diamonds!","""
* * *
*** *** ***
***** ***** *****
*** *** ***
* * *
""")
|
T h r
eeD iam ond
s!Thr eeDia monds
!Th ree Dia
m o n
|
Hint: While you may solve this how you wish, our sample solution did not use replace in any way.
Instead, we started with the empty string, and built up the
result character by character. How did we determine the next character? Using both the message and the pattern in some way...
And here is one last example, just for fun:
patternedMessage("Go Steelers!",
"""
oooo$$$$$$$$$$$$oooo
oo$$$$$$$$$$$$$$$$$$$$$$$$o
oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o o$ $$ o$
o $ oo o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o $$ $$ $$o$
oo $ $ '$ o$$$$$$$$$ $$$$$$$$$$$$$ $$$$$$$$$o $$$o$$o$
'$$$$$$o$ o$$$$$$$$$ $$$$$$$$$$$ $$$$$$$$$$o $$$$$$$$
$$$$$$$ $$$$$$$$$$$ $$$$$$$$$$$ $$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$ $$$$$$$$$$$$$ $$$$$$$$$$$$$$ '$$$
'$$$'$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ '$$$
$$$ o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ '$$$o
o$$' $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$o
$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$' '$$$$$$ooooo$$$$o
o$$$oooo$$$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ o$$$$$$$$$$$$$$$$$
$$$$$$$$'$$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$$'
'''' $$$$ '$$$$$$$$$$$$$$$$$$$$$$$$$$$$' o$$$
'$$$o '$$$$$$$$$$$$$$$$$$'$$' $$$
$$$o '$$'$$$$$$' o$$$
$$$$o o$$$'
'$$$$o o$$$$$$o'$$$$o o$$$$
'$$$$$oo '$$$$o$$$$$o o$$$$'
'$$$$$oooo '$$$o$$$$$$$$$'
'$$$$$$$oo $$$$$$$$$$
'$$$$$$$$$$$
$$$$$$$$$$$$
$$$$$$$$$$'
'$$$'
""")
Returns this:
GoSteelers!GoSteeler
s!GoSteelers!GoSteelers!GoS
teelers!GoSteelers!GoSteelers!GoS te el er
s ! Go Steelers!GoSteelers!GoSteelers!GoSteel er s! GoSt
ee l e rs !GoSteeler s!GoSteelers! GoSteelers !GoSteel
ers!GoSte elers!GoSt eelers!GoSt eelers!GoSt eelers!G
oSteele rs!GoSteele rs!GoSteele rs!GoSteelers!GoSteeler
s!GoSteelers!GoSteelers !GoSteelers!G oSteelers!GoSt eele
rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSteel ers!
GoS teelers!GoSteelers!GoSteelers!GoSteelers!GoSteelers !GoSt
eele rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSt eele
rs! GoSteelers!GoSteelers!GoSteelers!GoSteelers!Go Steelers!GoSteele
rs!GoSteelers !GoSteelers!GoSteelers!GoSteelers!GoS teelers!GoSteelers
!GoSteelers!G oSteelers!GoSteelers!GoSteelers!Go Steel
ers! GoSt eelers!GoSteelers!GoSteelers!G oSte
elers !GoSteelers!GoSteelers! GoS
teel ers!GoSteel ers!
GoSte elers
!GoSte elers!GoSteele rs!Go
Steelers !GoSteelers! GoStee
lers!GoSte elers!GoSteeler
s!GoSteele rs!GoSteel
ers!GoSteele
rs!GoSteeler
s!GoSteeler
s!GoS
- Bonus: topLevelFunctionNames(code) [3 pts]
Write the function topLevelFunctionNames(code) that takes a
possibly-multi-line string of Python code, and returns a string with the names of the top-level functions in that code, separated by dots ("."), in the order they appear in the code.
You may assume that the code is syntactically correct, with no non-ascii or non-printable characters in it. You may further assume that every top-level function is defined with a "def" statement, where the "def" is left-flush (so no spaces before the "def"), following by exactly one space (" "), followed by the function name, followed by no spaces, followed by the open parenthesis for the parameters.
This task is complicated by the fact that there can be multi-line strings in the code, and a "def" inside a multi-line string is not a function definition, and should be ignored.
This is further complicated by the fact that there can be comments (#) in the code, and everything after the comment on that line should be ignored, including any potential string delimiters.
Also, note that comment characters (#) can appear inside strings, in which case they are not the start of comments, and should be ignored.
Lastly, we will not give you any test cases for this function! You should write your own test cases, so that you can be confident your function works before submitting it.
Here is a sample test case for you:
# be careful! f is defined twice
code = """\
def f(x): return x+42
def g(x): return x+f(x)
def f(x): return x-42
"""
assert(topLevelFunctionNames(code) == "f.g")
And here is another one:
# g() is in triple-quotes ("""), so it isn't actually a function!
code = '''\
def f(): return """
def g(): pass"""
'''
assert(topLevelFunctionNames(code) == "f")