Do all the problems from f13 quiz3 (the first version, and you may skip the bonus). In addition, do just #1 (the strings portion) from s12 quiz5. As usual, though you can be brief in your supporting work, be sure to show at least some work (or you will not receive credit!). Submit the solutions to these problems in a triple-quoted string at the top of hw3.py (it is already there for you).
Background: for this problem, we will only be concerned with non-negative integers. A number n is palindromic if it is the same forwards as backwards. So 12321 is palindromic. We will say that a number is nearly palindromic (a coined term) if it is not palindromic, but could become palindromic by changing a single digit (not counting leading 0's, which cannot be changed). For example, 12241 is nearly palindromic, because we could change the first 2 to a 4 to obtain the palindrome 14241 (or, if you prefer, we could change the 4 to a 2 to obtain the palindrome 12221). With this in mind, write the function nthNearlyPalindromicPrime(n) that takes a non-negative int n and returns the nth number that is both prime and nearly palindromic. Since single-digit numbers are palindromic, as is 11, the first nearly palindromic prime is 13. Hence, nthNearlyPalindromicPrime(0) returns 13.
Write the function nthCarolPrime(n), which takes a non-negative int and returns the nth Carol Prime, which is a prime number of the form
((2k - 1)2 -2)
for some value positive int k. For example, if k equals 3, ((23 - 1)2 -2) equals 47, which is prime, and so 47 is a Carol Prime. The first several Carol primes are:
7, 47, 223, 3967, 16127, 1046527, 16769023,...
As such, nthCarolPrime(0) returns 7.
Note: You must use a reasonably efficient approach that quickly works up to n==9, which will return a 12-digit answer! In particular, this means you cannot just edit nthPrime (or fasterIsPrime) to call isCarolPrime instead of isPrime.
Background: a Kaprekar number is a non-negative integer, the representation of whose square can be split into two parts (where the right part is not zero) that add up to the original number again. For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45. You can read more about Kaprekar numbers here. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999 , 2223, 2728,... With this in mind, write the function nearestKaprekarNumber(n) that takes a numeric value n and returns the Kaprekar number closest to n, with ties going to smaller value. For example, nearestKaprekarNumber(49) returns 45, and nearestKaprekarNumber(51) returns 55. And since ties go to the smaller number, nearestKaprekarNumber(50) returns 45.
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".
Big Hint: use ord(c) to convert a character to its ASCII/Unicode value. Use chr(v) to go the other way, converting ASCII/Unicode back into a character. So: ord("A") is 65, and chr(65) is "A". And chr(ord("A")+1) is "B".
- 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
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
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 [2
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".
Aside: as we will cover more carefully later in the course, a function may take another function as an argument. For example, consider this code:
def h(n):
return n+5
def f(g, x):
return 2*g(x)
print f(h,3) # prints 16
Here, we define a function f whose first argument is another function. On the last line, we call f providing the function h, which is bound in f to the parameter g. Hence, calls to g in f are really calls to h. Play around with the sample code to get the hang of this idea. Then, read the next preliminary topic...
In mathematics, one way to numerically (as opposed to algebraically) find a zero of a function f(x) is to use what amounts to binary search. To start, we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1) have different signs (so one is positive and the other is negative). Hence, by the Intermediate Value Theorem, we know there is some value x in the range [x0,x1] such that f(x)=0. It is that value of x that we are seeking. How? First, try the value xmid, which is the midpoint between x0 and x1. If f(xmid) is exactly 0, we are done! Otherwise, we can divide our range in half as such: if f(xmid) and f(x0) are the same sign, use the range [xmid, x1]. Otherwise, f(xmid) and f(x1) must share the same sign, so use the range [x0, xmid]. We repeat this in a loop until x0 and x1 are within some suitably small epsilon.
With this in mind, write the function findZeroWithBisection that takes a function f, a float x0, a float x1, and a float epsilon, and returns an approximate value x in [x0,x1] where f(x) is approximately zero. Your function should stop when x0 and x1 are within epsilon, and at that time should return the midpoint of that range. Note that if it is not true that exactly one of f(x0) and f(x1) is negative, your function should return the Python value None, signifying that the bisection method cannot be used on the given range.
Let's see this in action! First, we'll use it to approximate the square root of 2 without the ** operator:
print "use bisection to approximate sqrt(2):"
def f1(x): return x*x - 2 # root at x=sqrt(2)
x = findZeroWithBisection(f1, 0, 2, 0.000000001)
print " x =", x # prints x = 1.41421356192
print " check: x**2 =", (x*x) # prints check: x**2 = 1.99999999871 (really close!)
Next, let's use it to approximate phi (the golden ratio), without using the closed-form solution ((1 + sqrt(5))/2), instead using the interesting property of phi that adding one to it is the same as squaring it. That is, ((phi + 1) == phi**2). How do use that? Simple, convert it into an equation equal to 0: phi**2 - (phi + 1) == 0. Now we're set! (Of course, we could just use the Quadratic Formula here, but it's more interesting to use bisection, now that we have it!).
print "use bisection to approximate phi (the golden ratio):"
def f2(x): return x**2 - (x + 1) # root at x=phi
x = findZeroWithBisection(f2, 0, 2, 0.000000001)
print " x =", x # prints x = 1.61803398887
phi = (1 + 5**0.5)/2 # the actual value (to within Python's floating point accuracy)
print " check: x/phi =", (x/phi) # prints check: check: x/phi = 1.00000000007 (nice!)
The previous two examples are nice, but simpler techniques than bisection would have worked as well. So let's solve a problem that would be hard to solve without bisection (or some other numeric approximation algorithm). Specifically, find a number x such that x5 == 2x:
print "use bisection to approximate x where x**5 == 2**x"
def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
x = findZeroWithBisection(f3, 1, 2, 0.000000001)
print " x =", x # prints x = 1.17727855081
print " check: x**5 - 2**x =", (x**5 - 2**x) # prints check: x**5 - 2**x = 3.63570817896e-09 (great!)
Hopefully this bisection excursion helps you appreciate the awesome computational power that about 10 lines of Python can have!
Note: For this problem only: as with hw2's bonus graphics problem, this will be graded only in person on Tuesday or Wednesday night at office hours.
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.