CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3b (Due Saturday 19-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. hw3b.py
  2. cs112_f20_week3_linter.py
3. Edit hw3b.py using VSCode
4. When you have completed and fully tested hw3b, submit hw3b.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 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 is due Friday at 8pm and is worth 70 points. It contains 4 standard problems and 2 spicy problems.
Hw3b (this part) 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

Important Note: You only have to do ONE of the two standard problems here. It is your choice. They are both fun! Doing both will not score more points, but will be more fun! Also, there are no spicy problems on hw3b, so everyone has to do one of these two standard problems.

mastermindScore(target, guess) [30 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!

playPoker(deck, players) [30 pts]
Note: even though this is a longer writeup, it is still a standard problem because the logic is not as complex as the spicy problems, and we are also providing some very strong hints. Basically, this is as challenging as the previous problem (mastermindScore), and some of you may find this one more interesting (that's why we are providing you a choice).

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! Good luck!

Bonus Problems

topLevelFunctionNames(code) [1.5 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")
```

Fun Decoders! [1.5 pts]

funDecode1(msg) [0.5 pts]
For this problem, you are given the function bonusEncode1(msg) (note that the name includes the word "bonus" but this is not a bonus problem, just a fun spicy problem!). 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
```
Have fun!

funDecode2(msg) [0.5 pts]
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) [0.5 pts]
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 3b (Due Saturday 19-Sep at 8pm)

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 3b (Due Saturday 19-Sep at 8pm)