Homework 8 (Due Sun 29-Oct at 8pm)

• Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, sample solution videos, etc.
• 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.
• You will need these files:
  • hw8.py
  • cs112_f22_week8_linter.py
  • cmu_112_graphics.py
  • lilAl_elements.csv
  • lilAl_reactions.csv
  • lilAl_elements_small.csv
  • lilAl_reactions_small.csv
• For this hw, you may submit up to 6 times but only your last submission counts.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.
• As always, all your functions must be non-destructive unless the problem specifically indicates otherwise.
• Also, if Python happens to provide a function that basically outright solves a problem, do not use that function. Naturally, we are looking for you to write the core logic of the problem.

1. Little Alchemy
2. getPairSum
3. containsPythagoreanTriple
4. movieAwards
5. Actor and Movie classes

1. Little Alchemy!
We've created a cmu_112_graphics version of the Little Alchemy game. But, we need your help to process the data using dictionaries and sets!

Our version of the game will lauch when you run hw8.py. It works, but it won't be very fun until you implement the functions below.
Note: You can comment out playLittleAlchemy() in hw8.py:main() to skip the game while you are focused on testing your code.

Functions:
• loadElementData
• loadReactionData
• tryReaction
• isTerminalElement
• allNextElements
• bestNextElement

loadElementData(filename) [5 pts]

Write the function loadElementData(filename) that takes in the file path to a data file stored in CSV (comma-separated values) format and returns a dictionary with the data from the file.
See example files lilAl_elements.csv and lilAl_elements_small.csv

Each row in the CSV file will be an entry in the dictionary. The string in the first column (element name) will be the key and the string in the second column (icon URL) will be the value. (You don't need to try to load the URL; the app will take care of this; just store the string in the dictionary.)
The CSV file contains a header row that you will have to skip.

Example file contents:

Name	Icon
fire	https://littlealchemy.com/cheats/img/base/2.png
earth	https://littlealchemy.com/cheats/img/base/2.png
air	https://littlealchemy.com/cheats/img/base/2.png

The above data would lead to the following dictionary:

{
    "fire":"https://littlealchemy.com/cheats/img/base/2.png",
    "earth":"https://littlealchemy.com/cheats/img/base/2.png",
    "air":"https://littlealchemy.com/cheats/img/base/2.png"
}


loadReactionData(filename) [5 pts]

Write the function loadReactionData(filename) that takes in the file path to a data file stored in CSV format and returns a dictionary with the data from the file.
See example files lilAl_reactions.csv and lilAl_reactions_small.csv

Each row in the CSV file will be an entry in the dictionary. The strings in the first two columns will combine as a tuple, (Element1, Element2), to be the key and the string in the third column, Element3, will be the value.
The CSV file contains a header row that you will have to skip.

Example file contents:

Element1	Element2	Element3
earth	fire	lava
air	air	pressure
air	fire	energy

The above data would lead to the following dictionary:

{
    ("earth","fire"):"lava",
    ("air","air"):"pressure",
    ("air","fire"):"energy"
}


Note: Note to keep things simple, our version of Little Alchemy doesn't have any reactions that create more than one element. (The official game has a few of these.)

tryReaction(elem1, elem2, reactionsDict) [5 pts]

Write the function tryReaction(elem1, elem2, reactionsDict) that takes in strings elem1 and elem2 (element names) and returns the resulting element name (as a string) if elem1 and elem2 (in either order) lead to a reaction in the given reactionsDict. Return None if the two elements (in either order) don't lead to a reaction.

isTerminalElement(elem, reactionsDict) [5 pts]

The Little Alchemy app is already set up to render the element name with an underline if it is a "terminal element". A "terminal element" is an element that doesn't lead to any reactions.

Write the function isTerminalElement(elem, reactionsDict) that uses the reactionsDict to check if elem (element name string) reacts with any other element (including itself) to produce another element. The function returns True if elem is a "terminal element" and returns False otherwise. Note if the element doesn't appear anywhere in the reactionsDict, then the function returns True (i.e., this element doesn't technically react with anything, so it would be a "terminal element").

allNextElements(elementSet, reactionsDict) [5 pts]

Write the function allNextElements(elementSet, reactionsDict) that references the reactionsDict to create and return the set of all new elements (element name strings) that can be created directly from elements in current set, elementSet. Return an empty set if no more elements can be created.

Efficiency: This doesn't need to be super efficient. A nice O(N^2) implementation that compares all pairs of the N elements in elementSet is fine.

Note: This is the list that will show up when you hit the 'A' key in our game.

Example: Starting with "fire", "earth", and "air" and the reactionsDict from lilAl_reactions_small.csv, allNextElements should return the set containing: "dust", "energy", "pressure", and "lava":


bestNextElement(elementSet, reactionsDict) [5 pts]

This function will provide a really great hint in our game (by pressing the 'B' key)!

Among all possible new elements that could be created directly from our current set of elements, find the element that, when added to our current set, will lead to the largest set of next possible elements.

Write the function bestNextElement(elementSet, reactionsDict) that references the reactionsDict to return the element name (string) that:
• Is not in the current set of element, elementSet,
• Can be created directly from elements in elementSet, and
• Can be combined with the current set to create more new elements than any other element in allNextElements(elementSet, reactionsDict)

Notes: Any ties between best next element should be broken by returning the element name first in alphabetical order. Return None if there are no next elements.

Example: Starting with "fire", "earth", and "air" and the reactionsDict from lilAl_reactions_small.csv, bestNextElement should return the "energy" (which wins the tie breaker with "lava"):


Play our version of Little Alchemy
That's it! Once you've finished the methods above, you should be able to play a pretty decent cmu_112_graphics version of Little Alchemy. This is just for fun, no additional tasks or points. Just make sure you don't get sucked into playing and forget to finish the rest of the assignment!


---



2. getPairSum(L, target) [15 pts: 7.5 pts autograded for correctness, 7.5 pts manually graded for efficiency (only if also correct)]
   Write the function getPairSum(L, target) that takes a list of integers and a target value (also an integer), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair as a tuple; otherwise, it returns None. If there is more than one valid pair, you can return any of them. For example:
   
   

   getPairSum([1], 1) == None
   getPairSum([5, 2], 7) in [ (5, 2), (2, 5) ]
   getPairSum([10, -1, 1, -8, 3, 1], 2) in [ (10, -8), (-8, 10), (-1, 3), (3, -1), (1, 1) ]
   getPairSum([10, -1, 1, -8, 3, 1], 10) == None

   A naive solution would be to check every possible pair in the list. That runs in O(N**2). To get full credit for the problem, your solution must run in no worse than O(N) time.


3. containsPythagoreanTriple(L) [15 pts: 7.5 pts autograded for correctness, 7.5 pts manually graded for efficiency (only if also correct)]
   Write the function containsPythagoreanTriple(L) that takes a list of positive integers and returns True if there are 3 values (a, b, c) anywhere in the list such that (a, b, c) form a Pythagorean Triple (where a**2 + b**2 == c**2). So [1, 3, 6, 2, 5, 1, 4] returns True because of (3,4,5): 3**2 + 4**2 == 5**2. [1, 3, 6, 2, 1, 4] returns False, because it contains no triple.
   
   A naive solution would be to check every possible triple (a, b, c) in the list. That runs in O(N**3). To get full credit for the problem, your solution must run in no worse than O(N**2) time.


4. movieAwards(oscarResults) [20 pts: 10 pts autograded for correctness, 10 pts manually graded for efficiency (only if also correct)]
   Write the function movieAwards(oscarResults) that takes a set of tuples, where each tuple holds the name of a category and the name of the winning movie, then returns a dictionary mapping each movie to the number of the awards that it won. For example, if we provide the set:

     { 
       ("Best Picture", "Green Book"), 
       ("Best Actor", "Bohemian Rhapsody"),
       ("Best Actress", "The Favourite"),
       ("Film Editing", "Bohemian Rhapsody"),
       ("Best Original Score", "Black Panther"),
       ("Costume Design", "Black Panther"),
       ("Sound Editing", "Bohemian Rhapsody"),
       ("Best Director", "Roma")
     }
   

   the program should return:

     { 
       "Black Panther" : 2,
       "Bohemian Rhapsody" : 3,
       "The Favourite" : 1,
       "Green Book" : 1,
       "Roma" : 1
     }
   

   
   Note 1: Remember that sets and dictionaries are unordered! For the example above, the returned dictionary may be in a different order than what we have shown, and that is ok.
   
   Note 2: Regarding efficiency, your solution needs to run faster than the naive solution using lists instead of some other appropriate, more-efficient data structures.



5. Actor and Movie classes [20 pts] [autograded]
   Write the classes Actor and Movie so that the following test code passes:

   def testActorMovieClasses():
       print('Testing Actor and Movie Classes...')
   
       # Actor class
       tom = Actor("Tom Hanks")
       # Note that tom != "Tom Hanks" - one is an object, and the other is a string.
       assert(isinstance(tom, Actor))
       assert(tom.getName() == "Tom Hanks")
   
       # Movie class
       mrRogers = Movie("A Beatiful Day in the Neighborhood", 2019)
       assert(isinstance(mrRogers, Movie))
       assert(mrRogers.getTitle() == "A Beatiful Day in the Neighborhood")
       assert(mrRogers.getYear() == 2019)
   
       # Note: actor.getMovies() returns a list of Movie objects that
       #       that this actor is in, listed in the order that
       #       they were added. This will start off empty.
       # Note: actor.getMovieTitles() returns a list of strings, the
       #       titles of the movies this actor was in.  This list is sorted!
       assert(tom.getMovies() == [])
       assert(tom.getMovieTitles() == [])
       # Similarly, getCast returns a list of Actor objects, while
       # getCastNames returns a sorted list of Actor names
       assert(mrRogers.getCast() == [])
       assert(mrRogers.getCastNames() == [])
   
       mrRogers.addActor(tom)
       assert(mrRogers.getCast() == [tom])
       assert(mrRogers.getCastNames() == ["Tom Hanks"])
       # Adding an actor also updates the actor
       assert(tom.getMovies() == [mrRogers])
       assert(tom.getMovieTitles() == ["A Beatiful Day in the Neighborhood"])
   
       diego = Actor("Diego Luna")
       terminal = Movie("The Terminal", 2004)
       terminal.addCast([tom, diego])
       assert(terminal.getCast() == [tom, diego])
       assert(terminal.getCastNames() == ["Diego Luna", "Tom Hanks"])
       terminal.addActor(tom)
       assert(terminal.getCast() == [tom, diego]) # Don't add twice
   
       felicity = Actor("Felicity Jones")
       rogue = Movie("Rogue One", 2016)
       rogue.addCast([felicity, diego])
   
       inferno = Movie("Inferno", 2016)
       felicity.addMovie(inferno)
       tom.addMovie(inferno)
       assert(felicity.getMovies() == [rogue, inferno])
       assert(tom.getMovieTitles() == ["A Beatiful Day in the Neighborhood",
           "Inferno", "The Terminal"])
   
       print('Passed!')

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