Homework 3

Due Tuesday 30-Jan, at 9:00pm

To start

Create a folder named ‘hw3’
Download hw3.py to that folder
Edit hw3.py and modify the functions as required
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

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.
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.
There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
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…
Do not hardcode the test cases in your solutions.
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.
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 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

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)

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')

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.

mostFrequentLetters(s) [15 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 ("").

mostFrequentSubstring(text, n) [20 pts]
Given a string text your task is to find the most frequently occuring substring of a given length. In the event of a tie between two substrings, choose the one that comes later in the alphabet. (So "bbb" is chosen over "bba".) Consider the following example in which the length is three (n = 3) and the text is just baababacb. The most frequent substring would then be aba because this is the substring with size 3 that appears most often in the whole text (it appears twice) while the other six diﬀerent substrings appear only once (baa ; aab ; bab ; bac ; acb). You can assume length >= 0. Here are more examples:
assert(mostFrequentSubstring("baababacb", 3) == "aba") assert(mostFrequentSubstring("thequickbrownfoxjumpsoverthelazydog", 1) == "o") assert(mostFrequentSubstring("testingthecodetofindtheerrortestandtestagain", 4) == "test")

encodeColumnShuffleCipher(message, key) [30 pts]
Background: In this problem you will implement a simple encryption cipher we've called a column shuffle cipher. It takes two values, a plaintext and a key, and it constructs a grid of the letters of the message, rearranges the columns of the grid, and then reads the characters back column by column.

Consider the following example:
```
Function call: encodeColumnShuffleCipher("WEATTACKATDAWN", "1320")
Message: WEATTACKATDAWN
Key: 1320

Initial Grid:		Rearranged Grid:
W E A T			T W A E
T A C K			K T C A
A T D A			A A D T
W N - -			- W - N

Encrypted Message: TKA-WTAWACD-EATN
Message to Return: 1320TKA-WTAWACD-EATN
```
The first step is to take the message and arrange it into a grid that has as many columns as the key has characters. (In this case, 4 columns.) Any empty spaces at the end are filled with - characters. We then rearrange the grid by changing the column order to match the order specified by the key. In this case, 0 being in the 3rd position of the key tells us that the 3rd column will become the 0th column. 1 being in the 0th position tells us that the 0th column will become the 1st column. 2 being in the 2nd position tells us that the 2nd column will become the 2nd column. 3 being in the 1st position tells us that the 1st column will become the 3rd column.

Finally, we read out the encrypted message by reading down the columns from left to right. The returned value from the function is just the encrypted message prepended with the key.

With this in mind, write the function encodeColumnShuffleCipher(message, key) that takes an all-uppercase message and a valid key, and returns the encoding as just described.

Hint: In your program you won't actually build a grid. Instead, you will use the concept of the grid to help you calculate the index of individual characters in your message.

decodeColumnShuffleCipher(encodedMessage) [20 pts]
Write the function decodeColumnShuffleCipher, which takes an encoding from encodeColumnShuffleCipher and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeColumnShuffleCipher("1320TKA-WTAWACD-EATN") returns "WEATTACKATDAWN".