CMU 15-112: Fundamentals of Programming and Computer Science
Homework 8 (Due Sat 23-Oct at 8pm ET)
(No Early Bird Bonus this week)

1. Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, sample solution videos, etc.
2. There is no early-bird bonus this week.
3. Except: everyone must attend this week's Friday Lab.
4. 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.
5. You will need these starter files:
   1. hw8.py
   2. cs112_f21_week8_linter.py
6. For this hw, you may submit up to 6 times but only your last submission counts.
7. Do not use recursion this week.
8. Do not hardcode the test cases in your solutions.
9. As always, all your functions must be non-destructive unless the problem specifically indicates otherwise.
10. Also, if Python happens to provide a function that basically outright solves a problem, such as statistics.median() for the median problem in hw4, do not use that function. Naturally, we are looking for you to write the core logic of the problem.

1. Midterm1 Free Responses [10 pts; 5 pts each]
   Write these free responses from this semester's midterm1 (version A):
   1. firstNAcceptedValues(n, rules) [autograded]
   2. midterm1Animation() (just called 'animation' on the midterm) [manually graded]
   The starter file includes the functions you will need for midterm1Animation.


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: because this is the second animation in the same file, we will use a fnPrefix for this problem (specifically, 'bonus_'). So, for example, you would write bonus_timerFired instead of timerFired. You only need to use the fnPrefix on the builtin animation functions, and not on any helper functions you might write.
   
   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.