First take the following quizzes under quiz conditions, and then using a computer as you wish (and CA's, office hours, etc, but still under the "solo" rules), write a solution set to each, placing those solutions in a triple-quoted string at the top of hw3.py that you submit. Do this for each of these:
- From s12 quiz5: just #1 (strings portion)
- From s13 practice quiz3: just Code Tracing + Reasoning Over Code
- From
s13
quiz3: all
- nthCircularPrime [15 pts]
A circular prime number is a number that remains prime on any cyclic rotation of its digits . For example, consider 197. Its rotations are 197 (itself), 971, and 719, and all of these are prime, so 197 is a circular prime. The first several circular primes are: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199,... With this in mind, write the function nthCircularPrime(n) for non-negative int n. As usual, the list is 0-based, so nthCircularPrime(0) returns 2.
- nthSmithNumber [10 pts]
Write the function nthSmithNumber that takes a non-negative int n and returns the nth Smith number, where a Smith number is a composite (non-prime) the sum of whose digits are the sum of the digits of its prime factors (excluding 1). Note that if a prime number divides the Smith number multiple times, its digit sum is counted that many times. For example, 4 equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith Number. The first few Smith numbers are 4, 22, 27, 58, 85, 94, 121, ... You may read more about Smith numbers here. Again, the list is 0-based, so nthSmithNumber(0) returns 4.
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. 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. Also, 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 |
And one more, just for fun. This:
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
Background: Here we will implement a simple password-based encryption scheme. First, we will start with a plaintext (not encrypted) message, say "Go team!". We will ignore all the non-letters and convert the letters to uppercase, giving us "GOTEAM". That is the message we will encrypt. Next, we need a password, which we assume is all lowercase letters, say "azby". We will think of each letter in the password as a shift, where a is 0 and z is 25, so "azby" specifies the shifts 0, 25, 1, 24 in order. We apply these shifts to the letters of the plaintext message, with wraparound (so after "Z" we go back to "A"). So we will shift "G" by 0 (resulting in "G"), "O" by 25 (resulting in "N"), "T" by 1 (resulting in "U"), and "E" by 24 (resulting in "C"). Then we run out of password characters, so we start over from the beginning of the password. So we shift "A" by 0 (resulting in "A") and "M" by 25 (resulting in "L"). Hence, encrypting "Go team!" with the password "azby" produces the ciphertext (that is, the encrypted text) "GNUCAL".
- encrypt [15 pts]
With the explanation above in mind, write the function encrypt(plaintext, password) that takes two strings, a plaintext message and a password, and which returns the encrypted string that results from the process described above. If the password is not all-lowercase, just return the string "password must be all lowercase".
- decrypt [5 pts]
Now write the other necessary part of any encryption scheme: decryption! Specifically, write the function decrypt(ciphertext, password) that takes two strings, a ciphertext message that was encrypted as described above, and a password. This function returns the original all-caps message that was encrypted. So, for example, decrypt("GNUCAL", "azby") should return "GOTEAM". Hint: decryption is very similar to encryption (which is why it is not worth so many points).
Background: as you might have guessed, this encryption scheme is not very robust. If someone had some encrypted text, they could fairly easily deduce your password based on letter frequencies and word frequences and the like. Here, we will attack an easier problem. Say that someone got hold of a plaintext message and also the encrypted ciphertext for that same message. We'll use this information to crack the password. In the above example, if they got hold of "Go team!" and also "GNUCAL", they can use these to determine the password is "azby". The approach will be simply by brute force. We will try every possible password! First the one-letter passwords ("a", "b", ..., "z"). Then the two-letter passwords ("aa", "ab", ..., "zy", "zz"). And so on. For each password, we will check if it would encrypt the plaintext message into the ciphertext. If so, we return the password, otherwise we just keep going (though for grading purposes you may end if no password of length 4 or less is found, and return None). With this in mind, write the following functions:
- nextPassword [10 pts]
Write the function nextPassword(password) that takes an all-lowercase password and returns the next one according to the order listed above. So nextPassword("a") would return "b", and nextPassword("z") would return "aa", and nextPassword("aef") would return ("aeg"). You may do this any way you wish, but here is one sound approach: if the rightmost character is not a "z", then just advance the rightmost character by one ("a" to "b", "b" to "c", etc) and you're done. But if it is a "z", then make it an "a" and advance the next character to the left by one. And so on. If you run out of characters to the left, then add a new "a" on the left. For example, after "zzz" you will advance each to "aaa" and then add a new "a" to get "aaaa", which is the correct next password to try after "zzz".
- verifyEncryption
[5 pts]
Here, we will write a modified version of the encrypt function from above to speed up our cracking (since we can stop encrypting as soon as we know we have the wrong password). Write the function verifyEncryption(plaintext, password, ciphertext), which in addition to the plaintext and password arguments that encrypt takes, also takes a string of ciphertext. This function returns True if encrypting the plaintext with the password returns the given ciphertext, and False otherwise. So in theory you could write it like this:
def verifyEncryption(plaintext, password, ciphertext):
return (encrypt(plaintext, password) == ciphertext)
However, this will be too slow, since the plaintext and ciphertext might be very large in the autograder! So your function should actually do the work of encrypting, but compare each resulting encrypted letter to the corresponding letter in the given ciphertext. As soon as any of these differ, the function immediately returns False, thus saving perhaps a great deal of time.
- crackPassword [5
pts]
Ok, so now we have the pieces we need to actually crack the password. Write the function crackPassword(plaintext, ciphertext). This function takes two strings, the plaintext and ciphertext as described above, and returns the password used to generate that ciphertext. To do so, it just starts with the password "a" and uses the nextPassword function to repeatedly generate each possible password in turn, and then it uses the verifyEncryption function to check if that password is the right one. The function returns the password, or None if it checked all passwords from "a" to "zzzz". So, for example, crackPassword("Go team!", "GNUCAL") would return "azby".
Write the function fasterCrackPassword that works just like crackPassword, only it is not allowed to use brute force (that is, trying every possible password), but rather it is more clever, based on the relationship between the ciphertext and plaintext, to determine the password. This will be tested with increasingly long messages and passwords, with more points awarded for solutions that crack longer passwords in a fixed amount of time (say, a few seconds).
Below the #ignore_rest line in hw3.py, write the function drawKeplerPolygon(canvas, cx, cy, r), that draws the image in this picture so that it just fits inside a circle of radius r centered at (cx, cy):
You can also include code that displays a window and draws this picture in that window. Just be sure all that code is below the #ignore_rest line, or it will confuse the autograder.