please code in python Suppose you record a list of birthdays for your classmates, recorded as month day tuples. An example is given below. # The 2nd to last tuple needs the int(2) in it so that it is uniquely stored in memory compared to (2,8) # Under the hood Python 3.7 changed how these are stored so (2,8) and (2,8) are stored in the same location # and then the algorithm below doesn't work dates = [(3,14),(2,8),(10,25),(5,17),(3,2),(7,25),(4,30),(8,7),(int(2),8),(1,22),(2, int(8))] You read about the famous birthday problem and you become interested in the number of pairs of classmates that share the same birthday. Below is an algorithm you write to do this. (Note: the is operator tests that two operands point to the same object) def birthday_original(dates_list): count = 0 for person_a in dates_list: for person_b in dates_list: # Make sure we have different people if person_a is person_b: continue # Check both month and day if person_a[0] == person_b[0] and person_a[1] == person_b[1]: count += 1 # We counted each pair twice (e.g. jane-bob and bob-jane) so divide by 2: return count//2 birthday_original(dates) You notice that your initial algorithm is inefficient in that it counts each pair twice. For example, it will increment count once when person_a is Jane and person_b is Bob, and again when person_a is Bob and person_b is Jane. Revise the algorithm so that it only looks at each pair once and has an average run-time of ϴ(n). Put that code in the function below - the function just needs to return the integer number of Total birthday pairs. Note: Your code needs to duplicate the functionality of the algorithm above. It is suggested that you make new dates lists and pass them to both functions to test that the results are the same! def birthday_count(dates_list): """Returns the total number of birthday pairs in the dates_list""" pass # delete this statement before entering your code!
please code in python
Suppose you record a list of birthdays for your classmates, recorded as month day tuples. An example is given below.
# The 2nd to last tuple needs the int(2) in it so that it is uniquely stored in memory compared to (2,8)
# Under the hood Python 3.7 changed how these are stored so (2,8) and (2,8) are stored in the same location
# and then the
dates = [(3,14),(2,8),(10,25),(5,17),(3,2),(7,25),(4,30),(8,7),(int(2),8),(1,22),(2, int(8))]
You read about the famous birthday problem and you become interested in the number of pairs of classmates that share the same birthday. Below is an algorithm you write to do this. (Note: the is operator tests that two operands point to the same object)
def birthday_original(dates_list):
count = 0
for person_a in dates_list:
for person_b in dates_list:
# Make sure we have different people
if person_a is person_b:
continue
# Check both month and day
if person_a[0] == person_b[0] and person_a[1] == person_b[1]:
count += 1
# We counted each pair twice (e.g. jane-bob and bob-jane) so divide by 2:
return count//2
birthday_original(dates)
You notice that your initial algorithm is inefficient in that it counts each pair twice. For example, it will increment count once when person_a is Jane and person_b is Bob, and again when person_a is Bob and person_b is Jane. Revise the algorithm so that it only looks at each pair once and has an average run-time of ϴ(n). Put that code in the function below - the function just needs to return the integer number of Total birthday pairs.
Note: Your code needs to duplicate the functionality of the algorithm above. It is suggested that you make new dates lists and pass them to both functions to test that the results are the same!
def birthday_count(dates_list):
"""Returns the total number of birthday pairs in the dates_list"""
pass # delete this statement before entering your code!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
