CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3 (Due Sat 20-Feb at 8pm ET (Pittsburgh-time))

With one exception (see next item), 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.
The encode/decode problems are collaborative. See the writeup below for details. These are the only collaborative problems on this assignment. Everything else is solo.
To start:
1. Create a folder named 'week3'
2. Download all of these to that folder:
3. Edit hw3.py using VSCode
4. When you have completed and fully tested hw3, submit hw3.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 this week.
Do not hardcode the test cases in your solutions.

Homework3 overview:

Part 1 Standard or Spicy [40 pts]
This week, you can do any combination of spicy and non-spicy part1 problems that together add up to 40 points.
- Part 1 Standard [40 pts]
  1. largestNumber [10 pts]
  2. rotateStringLeft [10 pts]
  3. isRotation [10 pts]
  4. topScorer [10 pts]
- Part 1 Spicy [40 pts]
  1. mastermindScore [20 pts]
  2. topLevelFunctionNames [20 pts]

Part 2 Required [40 pts]
Everyone must do these problems. We suggest completing part1 before attempting part2.
1. drawFlagOfQatar [20 pts]
2. playPoker [20 pts]

Part 3 Collaborative and Required [20 pts]
These problems (encodeRightLeftRouteCipher and decodeRightLeftRouteCipher) -- and only these problems -- are collaborative. See the writeup below for details. Everyone must do these problems.
1. Right-Left Route Ciphers (encode + decode) [20 pts]

Part 4 Bonus/Optional [up to 5 bonus pts]
These are bonus/optional. They are fun, interesting problems that are worth very few points. If you attempt these, do them for the fun and the learning, not the points.
1. patternedMessage [1 pt]
2. getEvalSteps [1 pt]
3. Fun Decoders [up to 3 pts]

Standard Problems
This week, you can do any combination of spicy and non-spicy part1 problems that together add up to 40 points.

largestNumber [standard, 10 pts]
Write the function largestNumber(text) that takes a string of text and returns the largest int value that occurs within that text, or None if no such value occurs. You may assume that the only numbers in the text are non-negative integers and that numbers are always composed of consecutive digits (without commas, for example). For example:
```
    largestNumber("I saw 3 dogs, 17 cats, and 14 cows!")
```
returns 17 (the int value 17, not the string "17"). And
```
    largestNumber("One person ate two hot dogs!")
```
returns None (the value None, not the string "None").

rotateStringLeft [standard, 10 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 [standard, 10 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.

topScorer [standard, 10 pts]
Write the function topScorer(data) that takes a multi-line string encoding scores as csv data for some kind of competition with players receiving scores, so each line has comma-separated values. The first value on each line is the name of the player (which you can assume has no integers in it), and each value after that is an individual score (which you can assume is a non-negative integer). You should add all the scores for that player, and then return the player with the highest total score. If there is a tie, return all the tied players in a comma-separated string with the names in the same order they appeared in the original data. If nobody wins (there is no data), return None (not the string "None"). So, for example:
data = '''\ Fred,10,20,30,40 Wilma,10,20,30 ''' assert(topScorer(data) == 'Fred') data = '''\ Fred,10,20,30 Wilma,10,20,30,40 ''' assert(topScorer(data) == 'Wilma') data = '''\ Fred,11,20,30 Wilma,10,20,30,1 ''' assert(topScorer(data) == 'Fred,Wilma') assert(topScorer('') == None)
Hint: you may want to use both splitlines() and split(',') here!

Spicy Problems
This week, you can do any combination of spicy and non-spicy part1 problems that together add up to 40 points.

mastermindScore [spicy, 20 pts]
This problem is inspired by the game of Mastermind. We will slightly adapt the game, and then we will not play the entire game, but rather just compute the score for a single guess. For that, we will be given a target string of lowercase letters, like say 'ccba', and then a guess string of the same length and also of lowercase letters, like say 'ddbc'. We have to compute two different values: the number of characters in the guess that are an exact match -- that is, the same character as the target in the same location. And then we also have to compute the number of characters in the guess that are a partial match -- the right character, but not in the right location. In the example, with a target of 'ccba' and a guess of 'ddbc', 'b' is an exact match, and 'c' is a partial match.

Your function should return a string describing the matches, with the exact match count first followed by the partial match count. In the example above, we get:
assert(mastermindScore('ccba', 'ddbc') == '1 exact match, 1 partial match')
If there are multiple matches, report them like so:
assert(mastermindScore('abcd', 'aabd') == '2 exact matches, 1 partial match')
If there is only one kind of match -- exact or partial -- then leave off the other kind from the report, like so:
assert(mastermindScore('efgh', 'abef') == '2 partial matches') assert(mastermindScore('efgh', 'efef') == '2 exact matches')
If there are no matches at all, return 'No matches', like so:
assert(mastermindScore('ijkl', 'mnop') == 'No matches')
Finally, if the two strings are in fact equal, then return 'You win!!!' like so:
assert(mastermindScore('wxyz', 'wxyz') == 'You win!!!')
Hint: Remember not to include any exactly-matched characters in your computation for partially-matched characters!

topLevelFunctionNames [spicy, 20 pts]
Write the function topLevelFunctionNames(code) that takes a possibly-multi-line string of Python code, and returns a string with the names of the top-level functions in that code, separated by dots ("."), in the order they appear in the code.

You may assume that the code is syntactically correct, with no non-ascii or non-printable characters in it. You may further assume that every top-level function is defined with a "def" statement, where the "def" is left-flush (so no spaces before the "def"), following by exactly one space (" "), followed by the function name, followed by no spaces, followed by the open parenthesis for the parameters.

This task is complicated by the fact that there can be multi-line strings in the code, and a "def" inside a multi-line string is not a function definition, and should be ignored.

This is further complicated by the fact that there can be comments (#) in the code, and everything after the comment on that line should be ignored, including any potential string delimiters.

Also, note that comment characters (#) can appear inside strings, in which case they are not the start of comments, and should be ignored.

Here is a sample test case for you:
```
    # f is redefined
    code = """\
def f(x): return x+42
def g(x): return x+f(x)
def f(x): return x-42
"""
    assert(topLevelFunctionNames(code) == "f.g")
```
And here is another one:
```
    # g() is in triple-quotes (""")
    code = '''\
def f(): return """
def g(): pass"""
'''
    assert(topLevelFunctionNames(code) == "f")
```

Required Problems
Everyone must do all these required problems.

drawFlagOfQatar [required, 20 pts]
Write the function drawFlagOfQatar(canvas, x0, y0, x1, y1) that takes a canvas and 4 values that describe a region on that canvas, with (x0, y0) at the top-left of the region and (x1, y1) at the bottom-right, and draws a flag of Qatar:

Be sure to follow these guidelines:
- Colors do not have to perfectly match but should be close.
- The flag must have a thin black border around it.
- The flag must have the name 'Qatar' in bold, centered just above the top.
Hint: You may find it helpful to use a loop to draw a series of small triangles.

The test function in the starter file calls your drawFlagOfQatar function 3 times. Here is what the resulting drawing should look like (again, colors do not have to match perfectly):

playPoker [required, 20 pts]
Note: even though this is a longer writeup, it is still a non-spicy problem because the logic is not as complex as the spicy problems, and we are also providing some very strong hints (be sure to read those hints, at the end of the problem writeup).

Background: Here we will play a simplified game of 2-card poker. To start, we need to represent a single playing card. We will do that using a 2-character string like '2D'. The first character represents the rank and the second represents the suit. So '2D' is the 2 of Diamonds. The ranks in order from lowest to highest are Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King (so in our game, Ace is always lowest), and we will represent them using this string:
ranks = 'A23456789TJQK' # ordered from lowest to highest
And the suits in order from lowest to highest are Clubs, Diamonds, Hearts, Spades, and we we will represent them using this string:
suits = 'CDHS' # also ordered from lowest to highest
Now that we can represent single cards, we need to represent a deck of cards. For that, we will simply place dashes between each card, like so:
deck = '2S-AD-TC'
While a deck can have up to 52 cards, this particular deck has just 3 cards -- the first card (on the top of the deck) is the 2 of Spades, then the Ace of Diamonds, and then the Ten of Clubs.

A hand is simply 2 cards. Hands are scored as such:
1. Straight Flush: this is the best possible hand. Here, the cards form both a straight, so they have consecutive ranks, and also a flush, so they have the same suit. For example, '8D-9D' is a straight flush, as is '9D-8D' since the order of the cards in the hand does not matter.
2. Flush: this is the second-best hand. Here, the cards just form a flush (but not a straight), so they have the same suit. For example, '8D-2D' is a flush.
3. Straight: this is the third-best hand. Here, the cards just form a straight (but not a flush), so they have consecutive ranks. For example, '8D-7S' is a straight.
4. Pair: this is the fourth-best hand. Here, the cards do not form a straight or a flush, but they have the same rank. For example, '8D-8H' is a pair.
5. High Card: this is the worst possible hand. Here, the cards do not form any of the hands above (no flush, no straight, no pair). In this case, we have to list the high card itself, so for example, '8D-5H' is 'a high card of 8D'.
Next, we have to consider ties. What happens if two players both get a flush, for example? Ties are resolved by the highest card in each hand. So instead of reporting '8D-5D' as just a flush, we will refer to it as 'a flush to 8D'. Now, '6H-9H' is also a flush, but it is 'a flush to 9H'. Should these two hands occur in the same game, the winner would be the second hand, since 9H is higher than 8D.

Note that ties in individual cards are resolved first by rank, but if they have the same rank, then by suit. So '2D-7C' is 'a high card of 7C', and '7H-5S' is 'a high card of 7H'. So if these two hands occur in the same game, then the second hand wins, because '7H' is better than '7C' (hearts are better than clubs).

Finally, let's consider how we deal (that is, distribute) cards from a deck to multiple players. This is done by dealing one card to each player (with players numbered starting at 1, not 0), and then a second card to each player. So, say we have this deck:
deck = '2S-AD-TC-AH-4H-9C'
Then:
- If we have only one player, that player gets the hand '2S-AD'. So Player 1 wins with 'a high card of 2S' (the high card is not the Ace because Aces are always low by our rules).
- If we have 2 players with this deck, then Player 1 gets '2S-TC' and Player 2 gets 'AD-AH'. So Player 2 wins with 'a pair to AH'.
- If we have 3 players with this deck, then Player 1 gets '2S-AH', Player 2 gets 'AD-4H', and Player 3 gets 'TC-9C'. So Player 3 wins with 'a straight flush to TC'.
- Finally, we have 4 or more players with this deck, then we cannot play because there are not enough cards.
With all that background in mind, write the function playPoker(deck, players) that takes a string representing a deck of cards as described above, and a positive integer number of players, and returns a description of the winning hand. Here are some examples for you:
assert(playPoker('QD-3S', 1) == 'Player 1 wins with a high card of QD') assert(playPoker('QD-QC', 1) == 'Player 1 wins with a pair to QD') assert(playPoker('QD-JS', 1) == 'Player 1 wins with a straight to QD') assert(playPoker('TD-QD', 1) == 'Player 1 wins with a flush to QD') assert(playPoker('QD-JD', 1) == 'Player 1 wins with a straight flush to QD') assert(playPoker('QD-JD', 2) == 'Not enough cards') assert(playPoker('AS-2H-3C-4D', 2) == 'Player 2 wins with a high card of 4D') assert(playPoker('5S-2H-3C-4D', 2) == 'Player 1 wins with a high card of 5S') assert(playPoker('AS-2H-3C-2D', 2) == 'Player 2 wins with a pair to 2H') assert(playPoker('3S-2H-3C-2D', 2) == 'Player 1 wins with a pair to 3S') assert(playPoker('AS-2H-2C-2D', 2) == 'Player 1 wins with a straight to 2C') assert(playPoker('AS-2H-2C-3D', 2) == 'Player 2 wins with a straight to 3D') assert(playPoker('AS-2H-4S-3D', 2) == 'Player 1 wins with a flush to 4S') assert(playPoker('AS-2H-4S-3H', 2) == 'Player 2 wins with a straight flush to 3H') assert(playPoker('2S-2H-3S-3H', 2) == 'Player 1 wins with a straight flush to 3S') assert(playPoker('AS-2D-3C-4C-5H-6D-7S-8D', 2) == 'Player 2 wins with a high card of 4C') assert(playPoker('AS-2D-3S-4C-5H-6D-7S-8D', 4) == 'Player 3 wins with a flush to 7S')

Here are some important hints (and that's all they are, hints, you can ignore them if you wish):
1. While players are numbered starting from 1 in the output, we found it very helpful to still number players starting from 0 in our code, then only add 1 right at the end.
2. We found it very helpful to write the helper function getHand(deck, player, players) that takes the deck, the player number, and the total number of players, and returns just that player's hand. For example, getHand('AS-2H-3C-4D', 0, 2) would return 'AS-3C'.
3. We also wrote getRankAndSuitIndexes(card) that takes a card and returns two values -- the index of the rank in the string of ranks ('A23456789TJQK') and the index of the suit in the string of suits ('CDHS'). So for example, getRankAndSuitIndexes('AD') returns the values (0, 1) and getRankAndSuitIndexes('2C') returns the values (1, 0). Note that '2' is at index 1 because 'A' is at index 0.
4. Next, we found it super helpful to assign a numeric score to each hand. This made it easier to compare hands. To do this, we decided (and you can decide differently!) that a hand scored 500 for a straight flush, 400 for a flush, 300 for a straight, 200 for a pair, and 100 for a high card. Then, we added a numeric value for the highest card. For that, we used (4*rank + suit). So, say the hand is '2D-7D'. This is 'a flush to 7D'. It gets 400 for the flush. Then we see that 7D has a rank of 6 (because Ace has a rank of 0, not 1), and a suit of 1, so it has a card value of (4*rank + suit) which is (4*6 + 1) which is 25. So the value of '2D-7D' is 425. We can use this value to compare two hands and determine which one is better.
5. Finally, we wrote evalHand(hand) that takes a hand and returns two values: the numeric score, as just described, and the string describing the hand. So, for example, evalHand('2D-7D') returns the values (425, 'a flush to 7D').
That's it! Have fun!

Collaborative Required Problems
These problems ((encodeRightLeftRouteCipher and decodeRightLeftRouteCipher)), and only these problems, are collaborative. Everyone must do all these required problems.

Here are the rules regarding collaboration on these problems:

Everyone must read all of these rules, even if you opt out of collaborating.
Collaboration is optional.
Collaboration is in groups of 2-3, arranged by your TA.
If you do collaborate, you must arrange this with your TA from your cohort, who must know which students in the cohort are collaborating with which other students.
You may only collaborate with other students in your cohort.
You may not change your collaborators once you have chosen them (except with written permission from the faculty if your partner becomes nonresponsive).
You must list the andrew id's of your collaborators in a comment just above your solutions to this section.
You must be an effective collaborator, working together as much as possible.
It is strictly forbidden for you to simply copy the code of your collaborators. That is not collaborating, that is cheating. Instead, you must type all your own code, without copying from others. You can discuss all parts of the problem with your collaborators. They can even help you debug. But still, you must write your own code.
Reminder from the syllabus: when we say "do not copy" we always mean visually, verbally, electronically, or in any other way, even if you copy and modify it".

Right-Left Route Ciphers (encode + decode) [collaborative, 20 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".

Bonus Problems
Bonus problems are entirely optional and worth few points. Do them for the fun and the learning.

patternedMessage [bonus, 1 pt]
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 (where any leading or trailing newlines in the pattern are first removed), with the message repeating over and over again until the pattern is complete. As a first example:

call	result
patternedMessage("Go Pirates!!!", """ ************* ** ** ************* """)	GoPirates!!!GoP irates !!!GoP irates!!!GoPira

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. Again, 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

Hint: In our sample solution, we started with an empty result string, then built up the answer character by character. How did we determine the next character? Using both the message and the pattern in some way...

And here is one last example, just for fun:

patternedMessage("Go Steelers!",
"""
                          oooo$$$$$$$$$$$$oooo
                      oo$$$$$$$$$$$$$$$$$$$$$$$$o
                   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:

                          GoSteelers!GoSteeler
                      s!GoSteelers!GoSteelers!GoS
                   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
                                ers!GoSteele
                                    rs!GoSteeler
                                     s!GoSteeler
                                      s!GoS

getEvalSteps [bonus, 1 pt]
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.

Fun Decoders [bonus, up to 3 pts]

funDecode1(msg) [1 pt]
For this problem, you are given the function bonusEncode1(msg). This function takes a string, msg, and returns an encoded version of the string. The encoding is fairly straightforward. Your job is to write the corresponding decoder. Specifically, write the function funDecode1(msg) so that, for any string s:
```
assert(funDecode1(bonusEncode1(s)) == s)
```
To make things more interesting, you are not given the function bonusEncode1(msg), but rather you are given the result of calling that function on itself, so you have the encoded version of the encoder! You still write the plaintext decoder! Here is the encoded encoder:
```
efg cpovtEodpef1(nth):
    sftvmu = ""
    gps d jo nth:
        jg (d.jtmpxfs()):
            d = dis(pse('b') + (pse(d) - pse('b') + 1)%26)
        sftvmu += d
    sfuvso sftvmu
```
To make sure your decoder works, you should replace the encoder function in your hw file with the decoded (that is, runnable) version of it.

Have fun!

funDecode2(msg) [1 pt]
Same basic problem: write funDecode2(msg) given this self-encoded version of bonusEncode2(msg):

ddd 7jhnkvd1c00N(5aX):
    0MZ0QX = ""
    I = HHEuyq.izinm_nftscoo + kkh7b3.Y2Z0a8
    PXZ O MQ SAMEB(GyG(DIv)):
        e = kpc[c]
        1X (R VZ Z): I = R[(O.CEIx(u) - v) % tlt(t)]
        j5ij9g += U
    3P33ZU WIVWMT

funDecode3(msg) [1 pt]
Once more: write funDecode3(msg) given this self-encoded version of bonusEncode3(msg):

100,1,1,-70,66,13,-1,7,-2,-46,41,-11,12,-11,
1,-50,-11,69,6,-12,-62,17,-48,22,0,0,0,82,-13,
14,2,-9,8,-84,29,-29,2,0,-24,22,0,0,0,80,
2,-13,17,-86,29,-29,16,-38,22,0,0,0,70,9,3,
-82,73,-73,73,5,-78,82,-17,13,-7,-2,-61,68,-7,9,
-70,69,6,-12,-62,0,17,-48,22,0,0,0,0,0,0,
0,67,18,-3,0,-82,29,-29,79,3,-14,-60,69,6,-12,
-12,14,-12,-52,-31,22,0,0,0,0,0,0,0,73,-3,
-70,8,74,-13,14,2,-9,8,-84,1,28,-29,2,0,7,
17,-26,82,-13,14,2,-9,8,-84,11,18,-29,2,10,-10,
-24,22,0,0,0,0,0,0,0,73,-3,-70,8,0,65,
-62,6,-8,-9,5,-5,17,4,-21,29,0,-29,16,-7,17,
-26,82,-13,14,2,-9,8,-84,11,18,-29,2,58,18,-76,
-24,22,0,0,0,0,0,0,0,82,-13,14,2,-9,8,
-84,11,18,-29,83,1,-2,-74,59,18,-3,0,-82,13,-13,
80,2,-13,17,-77,-31,22,0,0,0,0,0,0,0,80,
2,-13,17,-86,29,-29,67,18,-3,0,-104,22,0,0,0,
82,-13,15,1,-3,-4,-78,82,-13,14,2,-9,8

CMU 15-112: Fundamentals of Programming and Computer Science Homework 3 (Due Sat 20-Feb at 8pm ET (Pittsburgh-time))

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3 (Due Sat 20-Feb at 8pm ET (Pittsburgh-time))