CMU 15-112: Fundamentals of Programming and Computer Science
Homework 4 (Due Saturday 21-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.
The exercises included here are worth 75% of your homework score. The other 25% come from this week's writing session.

Helpful forms
Note: you must be authenticated to andrew.cmu.edu for these to work:
- 15-112-f19 Extension Request Form
- Note: this week all Hw4 Booster Sessions are walk-in only except for Friday. For Friday's session only, please use this form to sign up.

To start:
1. Create a folder named 'week4'
2. Download both hw4.py and cs112_f19_week4_linter.py to that folder
3. Edit hw4.py
4. When you have completed and fully tested hw4, submit hw4.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
Do not use recursion this week.
Do not hardcode the test cases in your solutions.

bestScrabbleScore(dictionary, letterScores, hand) [25 pts] [autograded]
Background: in a Scrabble-like game, players each have a hand, which is a list of lowercase letters. There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letterScores, which is length 26, where letterScores[i] contains the point value for the ith character in the alphabet (so letterScores[0] contains the point value for 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. The point value for a word is 0 if it is not in the dictionary; otherwise it is the sum of the point values of each letter in the word, according to the letterScores list (pretty much as it works in actual Scrabble).

In case you are interested, here is a list of the actual letterScores for Scrabble:
```
letterScores = [
#  a, b, c, d, e, f, g, h, i, j, k, l, m,
   1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3,
#  n, o, p, q, r, s, t, u, v, w, x, y, z
   1, 1, 3,10, 1, 1, 1, 1, 4, 4, 8, 4,10
]
```
Note that your function must work for any list of letterScores that is provided by the caller.

With this in mind, write the function bestScrabbleScore(dictionary, letterScores, hand) that takes 3 lists -- dictionary (a list of lowercase words), letterScores (a list of 26 integers), and hand (a list of lowercase characters) -- and finds the highest-scoring word in the dictionary that can be formed by some arrangement of some set of letters in the hand.
- If there is only one highest-scoring word, return it and its score in a tuple.
- If there are multiple highest-scoring words, return a tuple with two elements: a list of all the highest-scoring words in the order they appear in the dictionary, then the score.
- If no highest-scoring word exists (ie, if no legal words can be formed from the hand), return None instead of a tuple.
The dictionary in this problem is a list of words, and thus not a true Python dictionary (which we haven't taught you and you may not use in this assignment)! It is ok to loop through the dictionary, even if the dictionary we provide is large.

Hint: You should definitely write helper functions for this problem! In fact, try to think of at least two helper functions you could use before writing any code at all.

Another Hint: You may not use itertools for this problem! In fact, do not create permutations of the letters at all -- that is, do not try to generate all the possible ways to arrange the hand! If you do, your solution will take too long and Autolab will time out (hence, fail). There's a much simpler way to find all the legal words you can create...

Yet one more hint: Consider: if you had a single word w, and you have a single hand h, could you write a function f(w,h) (perhaps with a better name) that tells you whether or not that word could be constructed using that hand? And how might you use that function to help solve this problem?

Person class [10 pts] [autograded]
Write the class Person so that the following test code passes:

def testPersonClass():
    print('Testing Person Class...', end='')
    fred = Person('fred', 32)
    assert(isinstance(fred, Person))
    assert(fred.getName() == 'fred')
    assert(fred.getAge() == 32)
    assert(fred.getFriends() == None)

    wilma = Person('wilma', 35)
    assert(wilma.getName() == 'wilma')
    assert(wilma.getAge() == 35)
    assert(wilma.getFriends() == None)

    wilma.addFriend(fred)
    assert(wilma.getFriends() == [fred])
    assert(fred.getFriends() == None)    # friends are not necessarily reciprocal!
    wilma.addFriend(fred)
    assert(wilma.getFriends() == [fred]) # don't add twice!

    barney = Person('barney', 28)
    fred.addFriend(wilma)
    fred.addFriend(barney)
    assert(fred.getFriends() == [wilma, barney])
 
    fred.addFriend(barney)  # don't add twice
    fred.addFriend(fred)    # ignore self as a friend
    assert(fred.getFriends() == [wilma, barney])
    print('Passed!')

Note that your solution must work in general, and not hardcode to these specific test cases.

playMyTextAdventureGame() [40 pts] [manually graded]
Note: The point of this exercise is for you to have fun while learning about classes and 1d lists, and also for you to build something creative to help you prepare for your term projects, which will be much more substantial and sophisticated creative projects.

Time check: Just reading this writeup, playing the games, carefully watching the video, and answering the questions will take about 1 hour. We then expect game design to take about 1 hour, and game implementation to take perhaps 2 hours. So this whole exercise should take perhaps 4 hours. That's an estimate, and then on average, so some may be quicker, and some will naturally require more time.

Here each of you will write your own fun, creative, original text adventure game (well, a fairly simple start of one, at least, but still, one that shows you could write a more complete game if you wished).
1. Play Zork and Adventureland (very briefly)
  To start, watch the first minute or so of this video. Then, go to the Zork (and other text adventures) website and actually play around with Zork and Adventureland, at least enough to duplicate the commands shown in the video (so, in Zork, read the leaflet, and in Adventureland, climb the tree, see the meadow, go down and get to the meadow).
2. Play our Sample game
  Ok, now download simple-text-adventure-game.py , and play it until you win by drinking the water. The steps are shown in the video (starting around 1:20 or so), though you can have fun and try other steps as well. If you are curious, the code itself also tells you how to win (right?).
3. Watch the whole video, all 20 minutes, very carefully!
  Now, watch the entire video very carefully. The video is long but crucial for you to view and understand. Skipping this step, or skimming the video, will make every part of this exercise much harder and take much longer. Easily, the shortest and most effective and most fun way to do this is to really watch the video!
4. Answer these questions (in your hw4.py file)
  In a triple-quoted string inside your hw4.py file, just above where you will place your own text adventure game, copy-paste the following questions, and then add your own short but precise answers to them. The goal is to be sure that you really understand the code in simple-text-adventure-game.py before you start writing your own game.
  1. If kitchen is a Room instance, what is kitchen.exits[2]?
  2. When we call room.setExit('South', otherRoom), how does the setExit method convert the direction name 'South' into the index 1?
  3. Say we did not include the last line of the Room constructor, the one that sets self.items = [ ]. Eventually, our code would crash. What player action would make the code crash, and what precise Python error would we get?
  4. Why does room.getAvailableDirNames use the string join method?
  5. What is the difference between an item's name and its shortName?
  6. What is game.inventory?
  7. Why does game.getCommand use the string split method?
  8. How are we able to use game.findItem from both game.doGet (where we look through the items in the current room) and also in game.doPut (where we look through the items in the player's inventory)?
  9. In this version of the game, the player cannot carry more than 2 items. In which method is this enforced, and precisely how is it enforced?
  10. How does game.doDrink tell if the glass is full or not?
5. Write your own game!
  Ok, now we're at the fun part! You should write your own game!
  
  You can use parts of simple-text-adventure-game.py, so long as you cite them -- just include a simple comment like this in your code above each method you borrow:
```
    # from simple-text-adventure-game.py
```
  If it's a tiny change or two, maybe more like this:
```
    # from simple-text-adventure-game.py (with slight edits)
```
  The key in citing is to make clear what is yours and what is not, or in a mixed case, about how much is yours.
  
  Here are our grading criteria:
  1. Your game must be original.
  2. You may not use the same items as we did (no pitcher, no glass, no frog) nor the same rooms (no kitchen, no porch, ec) nor the same basic gameplay. So don't just gently adapt our gameplay. Make your own unique gameplay.
  3. The game should be reasonably fun and engaging. We do not expect amazing interactive fiction here. But we do want clear evidence that you thought about this and created a reasonably fun and engaging game.
  4. The game should be playable. Players should not have to randomly guess at what to do. The gameplay itself should provide hints and context. For example, in Zork, they want you to read the pamphlet, so they tell you there is a mailbox. They leave it to you to open the mailbox, see the pamphlet, and then read it. But they give you that first hint, seeing the mailbox, which makes the game playable.
  5. The game should be winnable, and that should ideally require some modest problem solving (consider in our sample game, you had to drink the water, which required filling the glass).
  6. The game should include the command help (which is already provided), and it should list all the verbs (commands) available. The TA's will use this to help grade your game.
  7. The game should include the command superhelp (all one word). This command prints all the steps required to win the game (from the start -- not necessarily from where the player currently is). TA's will also use this to help them grade your game.
  8. The game should have at least 3 rooms, at least 3 game-specific items, at least 3 game-specific verbs (not counting look/go/get/put/help/superhelp/quit) and winning should require at least 6 steps (including getting and putting items and moving to different rooms). These are easily-achieved minimums. We'd encourage you to do more as your gameplay requires.
  9. Some modest bonus points may be awarded as such:
    - Adding at least one more meaningful class to the game design.
    - Making the game especially fun and engaging.
That's it! Be creative! Learn about classes and 1d lists! Have fun!

Bonus/Optional: linearRegression(a) [2.5 pts] [autograded]
Write the function linearRegression(a) that takes a list of (x,y) points and finds the line of best fit through those points. Specifically, your function should return a triple of floats (a,b,r) such that y = ax+b is the line of best fit through the given points and r is the correlation coefficient as explained here (and yes, you must follow this exact approach). For example (taken from the text), linearRegression([(1,3), (2,5), (4,8)]) should return a triple of 3 values approximately equal to (1.6429, 1.5, 0.9972), indicating that the line of best fit is y = 1.6429x + 1.5, with a correlation coefficient of 0.9972 (so it's a really good fit, too). Note that the result is approximately equal to these values. Also note: the notes we refer you to do not discuss the meaning of the sign of r, so just return the absolute value |r|. And: you may ignore the case of a vertical line in your linearRegression code.

Bonus/Optional: runSimpleProgram(program, args) [2.5 pts] [autograded]
First, carefully watch this video that describes this problem:

Then, write the function runSimpleProgram(program, args) that works as described in the video, taking a legal program (do not worry about syntax or runtime errors, as we will not test for those cases) and runs it with the given args, and returns the result.

Here are the legal expressions in this language:
- [Non-negative Integer]
  Any non-negative integer, such as 0 or 123, is a legal expression.
- A[N]
  The letter A followed by a non-negative integer, such as A0 or A123, is a legal expression, and refers to the given argument. A0 is the value at index 0 of the supplied args list. It is an error to set arg values, and it is an error to get arg values that are not supplied. And you may ignore these errors, as we will not test for them!
- L[N]
  The letter L followed by a non-negative integer, such as L0 or L123, is a legal expression, and refers to the given local variable. It is ok to get an unassigned local variable, in which case its value should be 0.
- [operator] [operand1] [operand2]
  This language allows so-called prefix expressions, where the operator precedes the operands. The operator can be either + or -, and the operands must each be one of the legal expression types listed above (non-negative integer, A[N] or L[N]).
And here are the legal statements in this language (noting that statements occur one per line, and leading and trailing whitespace is ignored):
- ! comment
  Lines that start with an exclamation (!), after the ignored whitespace, are comments and are ignored.
- L[N] [expr]
  Lines that start with L[N] are assignment statements, and are followed by the expression (as described above) to be stored into the given local variable. For example: L5 - L2 42 This line assigns (L2 - 42) into L5.
- [label]:
  Lines that contain only a lowercase word followed by a colon are labels, which are ignored except for when they are targets of jump statements.
- JMP [label]
  This is a jump statement, and control is transferred to the line number where the given label is located. It is an error for such a label to not exist, and you may ignore that error.
- JMP+ [expr] [label]
  This is a conditional jump, and control is transferred to the line number where the given label is located only if the given expression is positive. Otherwise, the statement is ignored.
- JMP0 [expr] [label]
  This is another kind of conditional jump, and control is transferred only if the given expression is 0.
- RTN [expr]
  This is a return statement, and the given expression is returned.
Hints:
1. Do not try to translate the program into Python! Even if you could do so, it is not allowed here. Instead, you are going to write a so-called interpreter. Just keep track of the local variables, and move line-by-line through the program, simulating the execution of the line as appropriate.
2. You will find it useful to keep track of the current line number.
3. How long do you run the program? Until you hit a RTN statement! You may assume that will always eventually happen.
4. We used strip, split, and splitlines in our sample solution, though you of course may solve this how you wish.
Finally, here is a sample test function for you. You surely will want to add some addition test cases. In fact, a hint would be to build your function incrementally, starting with the simplest test cases you can think up, which use the fewest expression and statement syntax rules. Then add more test cases as you implement more of the language.
def testRunSimpleProgram(): print("Testing runSimpleProgram()...", end="") largest = """! largest: Returns max(A0, A1) L0 - A0 A1 JMP+ L0 a0 RTN A1 a0: RTN A0""" assert(runSimpleProgram(largest, [5, 6]) == 6) assert(runSimpleProgram(largest, [6, 5]) == 6) sumToN = """! SumToN: Returns 1 + ... + A0 ! L0 is a counter, L1 is the result L0 0 L1 0 loop: L2 - L0 A0 JMP0 L2 done L0 + L0 1 L1 + L1 L0 JMP loop done: RTN L1""" assert(runSimpleProgram(sumToN, [5]) == 1+2+3+4+5) assert(runSimpleProgram(sumToN, [10]) == 10*11//2) print("Passed!")

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

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