• This part of the hw is SOLO.  As explained in the course syllabus, you must not discuss these problems or share your code with anyone else except for the course staff and the tutors at Academic Development.  This includes students from former semesters (who may indeed have the answers to these problems!).
   
• This part is worth 60 pts.  Hw4b is worth 40 pts.
   
• Be sure to name your functions exactly as specified, and take exactly the same parameters as specified!
   
• There is no starter file nor any public autograder this week.  Be sure to write your own test functions!!!

1. sameChars [15 pts]
   Write the function sameChars(s1, s2) that takes two strings and returns True if the two strings are composed of the same characters (though perhaps in different numbers and in different orders) -- that is, if every character that is in the first string, is in the second, and vice versa -- and False otherwise. This test is case-sensitive, so "ABC" and "abc" do not contain the same characters. The function returns False if either parameter is not a string, but returns True if both strings are empty (why?).
    
2. isPalindrome [15 pts]
   Write the function isPalindrome that takes a possibly-empty string and returns True if the letters in that string form a palindrome (same forwards as backwards).  Ignore case, so "AbBa" is a palindrome.  And ignore punctuation and other non-letters.  The empty string is a palindrome.  So, for example, "Madam, I'm Adam" is a palindrome.
    
3. encodeRightLeftRouteCipher [15 pts]
   Background:  A right-left route cipher is a fairly simple way to encrypt a message.  It takes two values, some plaintext and a number of rows, and it first constructs a grid with that number of rows and the minimum number of columns required, writing the message in successive columns.  For example, if the message is WEATTACKATDAWN, with 4 rows, the grid would be:
      W T A W
      E A T N
      A C D
      T K A
   We will assume the message only contains uppercase letters.  We'll fill in the missing grid entries with lowercase letters starting from z and going in reverse (wrapping around if necessary), so we have:
      W T A W
      E A T N
      A C D z
      T K A y
   Next, we encrypt the text by reading alternating rows first to the right ("WTAW"), then to the left ("NTAE"), then back to the right ("ACDz"), and back to the left ("yAKT"), until we finish all rows.  We precede these values with the number of rows itself in the string.  So the encrypted value for the message WEATTACKATDAWN with 4 rows is "4WTAWNTAEACDzyAKT".
   
   With this in mind, write the function encodeRightLeftRouteCipher that takes an all-uppercase message and a positive integer number of rows, and returns the encoding as just described.
    
4. decodeRightLeftRouteCipher [15 pts]
   Write the function decodeRightLeftRouteCipher, which takes an encoding from the previous problem and runs it in reverse, returning the plaintext that generated the encoding.  For example, decodeRightLeftRouteCipher("4WTAWNTAEACDzyAKT") returns "WEATTACKATDAWN".
    
5. bonus/optional:  numberGuesser [1 pt]
   Background:  we will say that a number guessing function f is a function that lets you play the number guessing game.  How?  The function is trying to help you guess some goal value.  When you call f(n), where n is your current guess, the function return +1 if n>goal, 0 if n==goal, and -1 if n<goal.  In this way, with repeated calls to f(n), you can discover the value of the goal.  What fun!
   
   With this in mind, write the function numberGuesser, that takes one of these number guessing functions and simply determines the goal that the function is using, and return this integer value.  For example, say f is defined as such:
   
   def f(n):
       goal = 42
       if (n > goal): return +1
       elif (n == goal): return 0
       else: return -1
   
   Then, a call to numberGuesser(f) should return 42 (the hidden goal in the function).
   
   Note that you must be reasonably efficient, so you may not use linear search.  This basically means to use binary search, except that you do not know the range of the goal number (it may be a very large positive or very small negative number).  You have to be clever to first put some limits on this range.
    
6. bonus/optional:  extremeOfParabolaThroughLineIntersections [1 pt]
   Write the function extremeOfParabolaThroughLineIntersections, that takes 6 values -- m1, b1, m2, b2, m3, b3.  These describe 3 lines of the form y=mx+b.  Each line is guaranteed to intersect the other two lines, for 3 total points of intersection.   There is exactly one parabola that fits these 3 points (and you are assured the 3 points are not collinear and no 2 of them are on a vertical line).  Find that parabola.  Finally, find the nearest lattice point (that is, with integer x and y values) to the vertex of that parabola (that is, its highest or lowest point).  Return this (x,y) point.
   
   For example, consider the call extremeOfParabolaThroughLineIntersections(-10, 13, -8, 15-, -6, 13).  This describes these 3 lines:
       y = -10x + 13
       y = -8x + 15
       y = -6x + 13
   These lines intersect at these 3 points:
       (-1,23), (0,13), (1,7)
   The parabola that fits these 3 points is this:
       y = 2x**2 - 8x + 13
   And finally, the vertex of this parabola is this:
       (2,5)
   This actually is a lattice point, so we just return the tuple (2,5).
    
7. bonus/optional:  isTautology [2 pts]
   Write the function isTautology, that takes a string that is a valid Python boolean expression and returns True if that expression is a tautology (that is, is always True, regardless of the values of its variables), and False otherwise (that is, if there is any assignment of values to its variables that makes it false).  For example, isTautology("X") returns False, since the expression X is False if, well, x is False.  On the other hand, isTautology("X or not X") returns True, because "X or not X" is always True.
   
   You can assume the following:
   • The expression will not have syntax errors.
   • It will only use: variables, and, or, not, (, ), ==
   • The variables will only be single-character and uppercase (A, B, ..)
   • Here are a couple more-complicated hints...
     • In our solution for isTautology, we stored variable names in other variables, then used locals()[varname] to set those values, then used eval(expr) to evaluate expressions using those variables.  Here is a simple example:
       def f():
           var1 = "x"
           var2 = "y"
           locals()[var1] = 42
           locals()[var2] = 7
           return eval("x+y")
       print f() # prints 49
        
     • In our solution for isTautology, assuming we had n variables, we counted from 0 to 2**n, using the n-bit binary representation of each value in this range to represent a different assignment of truth values to the n variables.  Think about it...

   Good luck!

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