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

Read these instructions first!

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!!!", """
    ******   ******
    irates   !!!GoP

    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!",
                       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:

                       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


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

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