15-112 Spring 2014 Homework 3
Due Monday, 3-Feb, at 10pm
[Late submissions due Tuesday, 4-Feb, at 8pm]

• This entire hw is strictly SOLO.  See hw1 for details.

• Starting this week, you may use strings and imports, but (as usual) you may not use constructs we have not yet covered (lists (except implicitly, such as looping through s.splitlines()), sets, maps, recursion, etc).

• Also starting this week, style counts!

• This week, there is a limit of 5 submissions to Autolab.

• We are not providing you with test functions this week.  There are some empty test functions defined in hw3.py for you -- you will surely want to add tests of your own to them.  As a suggestion, you might consider turning some of the examples included in this writeup into tests in your test functions!

Additional hints (as posted on Piazza, and then collected here):

1) Do not use strings for testing if a number is a palindrome.  For numbers, use arithmetic, not strings.

2) For nearlyPalindromicPrime, you can solve this how you wish, but you might think about this:  in my sample solution, I did not actually create the palindrome but just determined it could be done in one step.  For example, with 1227, I did not change it to 1221 nor to 7227, but instead I determined that this could be done with one change.  How?  Well, that's left to you.  :-)

3) For nthCarolPrime, do not modify fasterIsPrime (except you might just call it isPrime).  That's not how to speed this up.  We are not looking for, and do not want, any amazing math here.  No.  It's just that you have to be clever about how you decide which numbers to check if they are prime.  Don't just do what nthPrime does, trying every number to see if it's both prime and a Carol number.  Instead, look at the definition of Carol numbers and see if you can limit which numbers you need to consider....

4) For nearestKaprekar(n), do not start counting from 0 up to n.  For example, what if we asked for nearestKaprekar(123456789), and let's just say that the answer was within 10 from there.  Of course, it could be in either direction, but still, it's nearby...  Is the best way to solve this really to start counting up from 0?

5) For patternedMessage, again solve it how you wish, but...  My sample solution did not use replace in any way.  Instead, I built up the result character by character.  I started with an empty string, and just kept adding the next character to it.  How did I determine the next character?  Using both the message and the pattern in some way....

6) For encrypt, read the Big Hint in the writeup.

7) More for nthCarolPrime:  Say that a number is wowish (goofy made up term) if it is both a power of 7 and also contains the digit 9 somewhere. Now, without using Python, what if I asked you what the 5th wowish number is? How would you find it? I don't think it's a good idea to check 1, 2, 3, 4, 5, ...  See?  Once you figure out how to find the nth wowish, you need to relate that back to the nthCarolPrime problem.  In case the analogy is lost, you'll treat the Carol numbers analogously to how you treated the powers of 7 in wowish.  And you'll treat the prime test analgously to how you treated the has-9 test in wowish.

And even more...

8) Numeric palindromes can be solved almost identically to string palindromes.  For strings, we needed to find the kth character (from each side).  Is there a similar way to find the kth digit of an integer?

9) If you must, you can solve a numeric problem with strings.  You'll lose the 2 style points, but that's all.  You'll get the correctness points.

10) Leading and trailing whitespace can be stripped away with s.strip().  You can check if a character is any whitespace (space, tab, newline, etc), with c.isspace().  You can check if a character is a newline with (c == '\n').  You can add a newline to a string with:  s += '\n'.

11) Don't forget about using the % operator for "wraparound", or a repeating function of some kind.

12) Be sure to include some floating-point numbers in your test cases for nearestKaprekarNumber.  Many students have infinite loops in that case, and the autograder will only report that your code took too long to run, without giving you the case that caused that!  So test it yourself!

13) In nthCarolPrime, some students were confused by other hints.  To be clear:  you can and should use isPrime (well, fasterIsPrime).  You just can't check every number from 0, 1, 2, 3, ....  The cleverness required here is in limiting which numbers you check in some way.  That's where the wowish hint helps.

14) Study the notes!!!  Some students are getting lost on hw3 because they basically do not yet understand the basics of loops, conditionals, or strings.  If you are in that boat, stop doing hw3 and go back and study the notes, do the practice problems, and learn the core material. Then come back here and try to solve these problems.  It will go much better then!

Good luck!!!

1. Previous Quizzes [20 pts]
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).

2. nthNearlyPalindromicPrime [15 pts]
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.

3. nthCarolPrime [15 pts]
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.

4. nearestKaprekarNumber  [15 pts]
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.

5. patternedMessage [15 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.  As a first example:

 call result patternedMessage("Go Pirates!!!", """*********************   *********************""") GoPirates!!!GoPirates   !!!GoPirates!!!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```

6. Simple Encryption [20 pts]
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".

1. 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".

2. 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).

7. Bonus/Optional:  Cracking Simple Encryption [2 pts]

2. 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:

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.

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".

8. Bonus/Optional:  findZeroWithBisection [1 very interesting and intellectually worthwhile pt]
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!

9. Bonus/Optional: drawKeplerPolygon [up to 3 pts]
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.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem