Homework 3

Due Tuesday 28-Jan, at 9:00pm

To start

1. Create a folder named ‘hw3’
2. Download hw3.py to that folder
3. Edit hw3.py and modify the functions as required
4. When you have completed and fully tested hw3, submit hw3.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

Some important notes

1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
2. After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
3. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
4. Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
5. Do not hardcode the test cases in your solutions.
6. The starter hw3.py file includes test functions to help you test on your own before you submit to Gradescope. When you run your file, problems will be tested in order. If you wish to temporarily bypass specific tests (say, because you have not yet completed some functions), you can comment out individual test function calls at the bottom of your file in main(). However, be sure to uncomment and test everything together before you submit! Ask a CA if you need help with this.
7. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not convert strings to lists, use lists, dictionaries, try/except, classes, or recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Starting with this assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading starts this week, so please use good style from now on!

A Note About Testing

You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

Problems

1. consonantCount(s) [5 pts]
   Write the function consonantCount(s), that takes a string s, and returns the number of consonants in s, ignoring case, so "B" and "b" are both consonants. The consonants are all of the English letters except "a", "e", "i", "o", and "u". So, for example:
   assert(consonantCount("Abc def!!! a? yzyzyz!") == 10)


2. rotateStringLeft(s, n) [5 pts]
   Note: To receive credit, do not use loops on this problem.
   Write the function rotateStringLeft(s, n) that takes a string s and a possibly-negative integer n. If n is non-negative, the function returns the string s rotated n places to the left. If n is negative, the function returns the string s rotated |n| places to the right. So, for example:
   assert(rotateStringLeft('abcd', 1) == 'bcda') assert(rotateStringLeft('abcd', -1) == 'dabc')


3. isRotation(s, t) [5 pts]
   Write the function isRotation(s, t) that takes two possibly-empty strings and returns True if one is a rotation of the other. Note that a string is not considered a rotation of itself.
   Hint: rotateStringLeft may be helpful here.


4. isFloat(n) [15 pts]
   We have seen in some lecture notes that if we want to read a float from the user, we use the function input() to read a string from the user and then use the function float() to convert that string to a float number. We also learned that if the user enters an invalid number, our program will crash. Now we don't like programs that crash. So, we would like to check if a string can be a float before we attempt to convert it to a float. This way, if the string is not float, we can print an error message and exit gracefully instead of crashing the program. If would be nice to have a function called isFloat that takes an input of string and returns back True if the input is a valid float and False if it is not. We can use this function in our programs as given below:
   inp = input("Enter your QPA: ") if( not isFloat(inp)): print("You entered a value that is not a valid QPA. Exiting gracefully :)") else: # we can safely decode the float now qpa = float(inp)
   Your task is to write the isFloat function that checks the string passed to it for validity of being a float number. If the input is a valid float number, it should return True, otherwise, it should return False. We will be calling the function as shown in the above example, so make sure the return values, function name, and input parameters are appropriate. You should NOT use a try/except structure for this function.


5. longestSubpalindrome [20 pts]
   Complete the problem longestSubpalindrome(s) from CS Academy. You must solve the problem directly on the website, doing all of your testing there. Do not write the solution in Thonny (or a different IDE) and copy/paste it into the website.


6. mostFrequentLetters(s) [25 pts]
   Write the function mostFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the letters of s in most frequently used order. (In the event of a tie between two letters, follow alphabetic order.) So:

      mostFrequentLetters("We Attack at Dawn")
   

   returns "atwcdekn". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. (And you should not use lists, sets, or maps in your solution.) Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").


7. longestCommonSubstring(s1, s2) [25 pts]
   Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:

        longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
        longestCommonSubstring("abcdef", "ghi") returns "" (the empty string)
   

   If there are two or more longest common substrings, return the lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:

       longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"
   



8. getEvalSteps(expr)[2 pts]
   Write the function getEvalSteps(expr), that takes a string containing a simple arithmetic expression, and returns a multi-line string containing the step-by-step (one operator at a time) evaluation of that expression. For example, this call:

   getEvalSteps("2+3*4-8**3%3")
   

   produces this result (which is a single multi-line string):

   2+3*4-8**3%3 = 2+3*4-512%3
                = 2+12-512%3
                = 2+12-2
                = 14-2
                = 12
   

   Here are some considerations and hints:
   • You are only responsible for legal input as described below. Numbers are limited to non-negative integers.
   • Operators are limited to +, -, *, //, %, and **.
   • All operators are binary, so they take two operands. So there are no unary operators, meaning "-5" is not a legal input. For that, you'd need "0-5".
   • In fact, the previous restriction is even stronger: no intermediate value of expr can be negative! So "1-2+3" is not legal, since it would be converted first into "-1+3" which is not legal. So you can safely ignore all such cases.
   • There are no parentheses.
   • Operators must be evaluated by precedence (** first, then *,//,%, then +,-).
   • Equal-precedence operators are evaluated left-to-right.
   • Evaluation proceeds until a single integer with no operators remains after the equals sign.
   • The equal signs must all be stacked directly over each other.
   • You may write this however you wish, though you may want to write a helper function that finds the next operator to be applied, and another helper function that just applies a single operator. Something like that. In any case, top-down design is crucial here. And don't forget to thoroughly test your helper functions before using them!
   • In our sample solution, we used very few string methods, just "find" and "isdigit". You may use others, but you should not spin your wheels trying to find that awesome string method that will make this problem remarkably easier, as that method does not exist.
   • For this function, as any other function, you may not use the eval function, so you will have to write your own equivalent just for the kinds of simple expressions you will deal with here. Eval is dangerous and should be avoided, as it can lead to serious bugs or security holes.