CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3a (Due Friday 18-Sep at 8pm)

This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
To start:
1. Create a folder named 'week3'
2. Download these files into that folder:
  1. hw3a.py
  2. cs112_f20_week3_linter.py
3. Edit hw3a.py using VSCode
4. When you have completed and fully tested hw3a, submit hw3a.py to Autolab. For this hw, you may submit up to 7 times, but only your last submission counts.
Do not use lists, list indexing, or recursion in this unit.
Do not hardcode the test cases in your solutions.

Note about standard and spicy parts!
As always, you can mix-and-match standard and spicy problems as you prefer. We very much hope that some of you take on the challenge of the spicy problems, should they be appropriate for you.

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 (this is in total, across hw3a and hw3b). 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!

Important note: This hw is split into two parts, both entirely solo, as such:

Hw3a (this part) is due Friday at 8pm and is worth 70 points. It contains 4 standard problems and 2 spicy problems.
Hw3b is due Saturday at 8pm and is worth 30 points. It contains another two standard problems (everyone has their choice of which one they will do) and some bonus problems.

We added the Saturday deadline because we will discuss the non-bonus Saturday problems in recitation on Friday, including some really useful hints, and we wanted everyone in every timezone to have the time to absorb those hints for those problems.

Again, both parts are entirely solo.

Standard Problems

vowelCount(s) [15 pts]
Write the function vowelCount(s), that takes a string s, and returns the number of vowels in s, ignoring case, so "A" and "a" are both vowels. The vowels are "a", "e", "i", "o", and "u". So, for example:
assert(vowelCount("Abc def!!! a? yzyzyz!") == 3) # two a's and one e

applyCaesarCipher(message, shift) [20 pts]
A Caesar Cipher is a simple cipher that works by shifting each letter in the given message by a certain number. For example, if we shift the message "We Attack At Dawn" by 1 letter, it becomes "Xf Buubdl Bu Ebxo".

Write the function applyCaesarCipher(message, shift) which shifts the given message by shift letters. You are guaranteed that message is a string, and that shift is an integer between -25 and 25. Capital letters should stay capital and lowercase letters should stay lowercase, and non-letter characters should not be changed. Note that "Z" wraps around to "A". So, for example:
assert(applyCaesarCipher("We Attack At Dawn", 1) == "Xf Buubdl Bu Ebxo") assert(applyCaesarCipher("zodiac", -2) == "xmbgya")

rotateStringLeft(s, n) [20 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) [15 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: The previous problem may be helpful here.

Spicy Problems

Right-Left Route Ciphers (encode + decode) [35 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.

Here are a few more examples to consider:

assert(encodeRightLeftRouteCipher("WEATTACKATDAWN",4) == "4WTAWNTAEACDzyAKT") assert(encodeRightLeftRouteCipher("WEATTACKATDAWN",3) == "3WTCTWNDKTEAAAAz") assert(encodeRightLeftRouteCipher("WEATTACKATDAWN",5) == "5WADACEAKWNATTTz")
Be sure to take the time to fully understand each of those examples!

Hint: the grid described above is only conceptual. Your code will never actually construct a 2-dimensional grid (especially as you may not yet use lists!). Instead, you should use a clever scheme of indexing the message string where you translate a row and column into a single index into the message string.

More complete hint: let's do this example in a bit more detail, and we'll even provide an idea or two on how to simplify solving this:
```
assert(encodeRightLeftRouteCipher("WEATTACKATDAWN",3) == "3WTCTWNDKTEAAAAz") 
```
1. Find the dimensions of the conceptual 2d grid
  Since len('WEATTACKATDAWN') is 14, and we have 3 rows, we need math.ceil(14/3) or 5 columns.
2. Pad the string
  We need 3*5, or 15 letters. We have 14. We have to add one. So we now have 'WEATTACKATDAWNz'
3. Imagine the conceptual 2d grid
  We do not create this part. We just imagine it. But this is the 2d grid we imagine:
```
W T C T W
E T K D N
A A A A z
```
4. Label your rows and cols
  To be sure we are visualizing the grid properly, let's add row and col labels, like so:
```
       col0  col1  col2  col3  col4
row0:    W     T     C     T     W
row1:    E     T     K     D     N
row2:    A     A     A     A     z
```
5. Label the padded string with row, col, and i
  Let's use these row and col labels, but write them over the padded string (instead of the conceptual 2d grid). We'll also include the index i, like so:
```
    row:  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2
    col:  0  0  0  1  1  1  2  2  2  3  3  3  4  4  4
    i:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
          W  E  A  T  T  A  C  K  A  T  D  A  W  N  z
```
6. Find a function f(row,col) --> i
  Look at the patterns in the row, col, and i in the table we just made. See if you can find a function f(row, col) that takes any row and col (in the conceptual 2d grid) and returns the corresponding index i (in the padded string). Also, name this function something better than f.
  - Hint: from the table above, we see that the K is in row 1 and column 2, and the K is at index 7 in the padded string, so... f(1,2) == 7
  - Hint: see how the row in the table above repeats: 0, 1, 2, 0, 1, 2,... What does this have to do with the fact that we have 3 total rows?
7. Now, traverse the 2d grid top-to-bottom, left-to-right
  This step is not required, but it is super helpful. As only a temporary measure, we will solve a slightly easier version of the problem: we will simply ignore that every other row goes right-to-left. We'll make every row go left-to-right just for now. So use two loops, one going over every row, and inside that, one going over every column. For each row,col pair, use your function f() that you just wrote (and renamed) to find the index in the padded string. Remember that this was the conceptual grid:
```
WTCTW
ETKDN
AAAAz
```
  And so, when you are done with this step, you should have a string like this (which, again, is not the real solution, since we always go left-to-right):
```
WTCTWETKDNAAAAz
```
8. Now alternate left-to-right and right-to-left
  Now make every-other-row go the other way. So the second row will change from ETKDN to NDKTE, like so:
```
WTCTWNDKTEAAAAz
```
9. Add the rows as a prefix
  Easy enough:
```
3WTCTWNDKTEAAAAz
```
10. Return that string
  We are done. To remind ourselves, here was the test case:
  assert(encodeRightLeftRouteCipher("WEATTACKATDAWN",3) == "3WTCTWNDKTEAAAAz")
Whew! And now that you have written the encoder, we need to write the decoder. For that, 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".

getEvalSteps(expr) [35 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.

CMU 15-112: Fundamentals of Programming and Computer Science Homework 3a (Due Friday 18-Sep at 8pm)

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3a (Due Friday 18-Sep at 8pm)