CMU 15-112: Fundamentals of Programming and Computer Science
Homework 9 (Due Saturday 3-Apr at 8pm EDT)

• Hw9 bonus will be submitted separately in Autolab, in hw9-bonus (in the etc category).
• There is no grace day for hw9-bonus, even if you use a grace day for hw9.
• There is no starter file for hw9-bonus.
• With that, have fun!!! :-)

• To start, download all of these to that folder:
  • hw9.py
  • cs112_s21_week9_linter.py
• Edit hw9.py
• When you have completed and fully tested hw9, submit your hw9 file to Autolab. For this hw, you may submit up to 7 times, but only your last submission counts.

---

Notes:
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

1. TA-led mini-lecture [10 pts]
2. Person class [20 pts]
3. getPairSum(L, target) [15 pts]
4. containsPythagoreanTriple(L) [15 pts]
5. movieAwards(oscarResults) [20 pts]
6. friendsOfFriends(d) [20 pts]
7. bonus: Sorting animation [3 pts]

1. Attend one TA-led mini-lecture in-person (over zoom) [10 pts] [manually graded]
   Please see the piazza announcements here and here for details, and then attend at least one of the TA-led mini-lectures this week (in person, live, over zoom). You may optionally watch as many others as you wish, either live or by recording. Enjoy!


2. Person class [20 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)
       # Note: person.getFriends() returns a list of Person objects who
       #       are the friends of this person, listed in the order that
       #       they were added.
       # Note: person.getFriendNames() returns a list of strings, the
       #       names of the friends of this person.  This list is sorted!
       assert(fred.getFriends() == [ ])
       assert(fred.getFriendsNames() == [ ])
   
       wilma = Person('wilma', 35)
       assert(wilma.getName() == 'wilma')
       assert(wilma.getAge() == 35)
       assert(wilma.getFriends() == [ ])
   
       wilma.addFriend(fred)
       assert(wilma.getFriends() == [fred])
       assert(wilma.getFriendsNames() == ['fred'])
       assert(fred.getFriends() == [wilma]) # friends are mutual!
       assert(fred.getFriendsNames() == ['wilma'])
   
       wilma.addFriend(fred)
       assert(wilma.getFriends() == [fred]) # don't add twice!
   
       betty = Person('betty', 29)
       fred.addFriend(betty)
       assert(fred.getFriendsNames() == ['betty', 'wilma'])
   
       pebbles = Person('pebbles', 4)
       betty.addFriend(pebbles)
       assert(betty.getFriendsNames() == ['fred', 'pebbles'])
   
       barney = Person('barney', 28)
       barney.addFriend(pebbles)
       barney.addFriend(betty)
       barney.addFriends(fred) # add ALL of Fred's friends as Barney's friends
       assert(barney.getFriends() == [pebbles, betty, wilma])
       assert(barney.getFriendsNames() == ['betty', 'pebbles', 'wilma'])
       fred.addFriend(wilma)
       fred.addFriend(barney)
       assert(fred.getFriends() == [wilma, betty, barney])
       assert(fred.getFriendsNames() == ['barney', 'betty', 'wilma']) # sorted!
       assert(barney.getFriends() == [pebbles, betty, wilma, fred])
       assert(barney.getFriendsNames() == ['betty', 'fred', 'pebbles', 'wilma'])
       print('Passed!')
   

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


3. 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.


4. 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.


5. 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 are unordered! For the example above, the returned set 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.


6. friendsOfFriends(d) [20 pts: 10 pts autograded for correctness, 10 pts manually graded for efficiency (only if also correct)]
   Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
   d = { } d["jon"] = set(["arya", "tyrion"]) d["tyrion"] = set(["jon", "jaime", "pod"]) d["arya"] = set(["jon"]) d["jaime"] = set(["tyrion", "brienne"]) d["brienne"] = set(["jaime", "pod"]) d["pod"] = set(["tyrion", "brienne", "jaime"]) d["ramsay"] = set()
   
   With this in mind, write the nondestructive function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends-of-friends. For example, since Tyrion is a friend of Pod, and Jon is a friend of Tyrion, Jon is a friend-of-friend of Pod. This set should exclude any direct friends, so Jaime does not count as a friend-of-friend of Pod (since he is simply a friend of Pod) despite also being a friend of Tyrion's. Additionally, a person cannot be a friend or a friend-of-friend of themself.
   
   Thus, in this example, friendsOfFriends should return:
   { 'tyrion': {'arya', 'brienne'}, 'pod': {'jon'}, 'brienne': {'tyrion'}, 'arya': {'tyrion'}, 'jon': {'pod', 'jaime'}, 'jaime': {'pod', 'jon'}, 'ramsay': set() }
   
   Note 1: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
   
   Note 2: you may not assume that if Person1 lists Person2 as a friend, Person2 will list Person1 as a friend! Sometimes friendships are only one-way. =(
   
   Note 3: regarding efficiency, your solution needs to run faster than the naive solution using lists instead of some other appropriate, more-efficient data structures.


7. Bonus/Optional: Sorting animation [3 pts] [manually graded]
   Note: this will be submitted separately from hw9, in hw9-bonus, and is due Saturday even if you take a grace day on hw9. As such, do not include this in your hw9.py submission!
   
   Write an animation function for your favorite sorting algorithm! You'll want to use the animation starter code, but you can be creative regarding how you visualize the sorting process. The only requirements are the following features:
   
   
   • Clearly indicate the name of the sorting algorithm being demonstrated
   • Demonstrate using a randomly-generated shuffled list of the numbers from 0 to 20
   • Clearly demonstrate each comparison, move, swap, etc.
   • Use the right arrow key to move the sort a step forward, and the left key to move a step back
   • Type the "r" key to reset the animation to a new shuffled list
   
   Feel free to look at the sorting links in the efficiency course notes for inspiration! There's lots of cool visualizations and sorting algorithms out there.
   
   Reminder: If you attempt this bonus problem, do not include it in your hw9.py submission, and submit it separately to hw9-bonus.