%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
import base64
code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def assertEqual(want, got):
if want == got:
print("Test case passed.")
return
print()
print("--------- Test case failed. ---------")
print(f"Want: {repr(want)} (type: {type(want).__name__})")
print(f"Got: {repr(got)} (type: {type(got).__name__})")
print("-------------------------------------")
print()
country_to_capital = {
'Jamaica': 'Kingston',
'Canada': 'Ottawa',
'Iran': 'Teheran',
'Turkey': 'Ankara'
}
This dictionary maps the names of each country (the key) to the name of its capital (the value). Given a dictionary, we can retrieve the value corresponding to a given key using square bracket notation.
print(country_to_capital['Jamaica'])
Notice that this syntax is similar to looking up value associated with an index in a list (dictionaries are often called "associative arrays").
Dictionaries are also mutable: the value for a key can be updated, also in a syntax similar to array mutation.
country_to_capital['Iran'] = 'Teheran'
country_to_capital['Taiwan'] = 'Taipei'
print(country_to_capital['Iran'])
print(country_to_capital['Taiwan'])
There are also a few useful ways to access the dictionary's keys, access to the values, or the query the number of entries.
print(list(country_to_capital.keys())) # Countries.
print(list(country_to_capital.values())) # Their capitals.
print(len(country_to_capital)) # Number of countries the dictionary contains.
You can also check if a key exists in the dictionary using the in operator.
print('Jamaica' in country_to_capital)
print('Kingston' in country_to_capital)
1.1 What would Python do?¶
Below is a dictionary, users, that maps a person's username to their name. What would the following code print?
users = {
'bereket_molla': 'Bereket Molla',
'bryan20': 'Bryan Baker',
'minilek': 'Jelani Nelson',
'tylerhou': 'Tyler Hou',
}
print("Keys:", users.keys())
print("Values:", users.values())
print("Length:", len(users))
print("minilek:", "minilek" in users)
print("chronixx", "chronixx" in users)
2. My friends, and I¶
2.1 friends¶
Write a dictionary my_friends mapping the names of five of your friends to their ages. (Don't worry about being accurate.). In other words, we want a dictionary with students names as keys and ages as values.
my_friends = # YOUR CODE HERE
assertEqual("dict", type(my_friends).__name__)
assertEqual(5, len(my_friends))
2.2 average_friends_age¶
Write a function average_friends_age that takes a dictionary d. d maps the names of friends to their ages. average_friends_age should return the average age of all the friends in the dictionary.
def average_friends_age(d):
"""Computes the average age of friends in the given dictionary.
Arguments:
d (dict): A dictionary that contains friends' names and their ages.
Returns: (float) The average age of all friends.
Effects: None.
"""
# YOUR CODE HERE
test_friends = {"Barney": 500, "Cailou": 4, "Lala": 2, "Blue": 19, "Jimmy Newtron": 14}
print("Test cases:")
assertEqual(107.8, average_friends_age(test_friends))
2.3 add_friend¶
Now, write a function add_friend(d, name, age) that adds a new friend with name name and age age to the dictionary d of friends.
def add_friend(d, name, age):
"""Records your new friend's name and age in the dictionary, mutating it.
Arguments:
d (dict): The dictionary in which to add your new friend.
name (str): Your new friend's name.
age (int): Your new friend's age.
Returns: None.
Effects: Adds a new friend in the dictionary `d`.
"""
# YOUR CODE HERE
test_friends = {"Barney": 500, "Cailou": 4, "Lala": 2, "Blue": 19, "Jimmy Newtron": 14}
assertEqual(None, add_friend(test_friends, 'Damerae', 19))
assertEqual(19, test_friends['Damerae'])
2.4 The potion of youth¶
You and your friends have discovered a magic potion that makes the drinker 2 years younger. Write a function drink_magic_potion that takes your friend's name and updates their age in the dictionary to be two years younger.
def drink_magic_potion(d, name):
"""Applies the effects of a youthening potion to the drinker.
Arguments:
d: The dictionary containing your friends.
name: The drinker's name.
Returns: None.
Effects: Makes the drinker two years younger in the dictionary `d`.
"""
test_friends = {"Barney": 500, "Cailou": 4, "Lala": 2, "Blue": 19, "Jimmy Newtron": 14}
assertEqual(None, drink_magic_potion(test_friends, "Barney"))
assertEqual(498, test_friends["Barney"])
3. One fish, two fish...¶
3.1 No fish?!?¶
A common use for a dictionary is to keep track of how many times we have seen a particular item. The keys of the dictionary are the items, while the values are the count. For example, the following dictionary represents that a has a count of 2 and b has a count of 3.
counter = {
'a': 2,
'b': 3,
}
If an item is not in the dictionary, it is useful to to think of it as having count 0. Write a function get_count(counter, item) that returns the current count of an item. (Remember that if an item is not in the dictionary, we should return 0.)
def get_count(counter, item):
"""Retrieves the current item's count from the counter.
If we have not seen the item so far, returns 0.
Arguments:
counter (dict): The counter dict.
item (str): The item whose count we are retrieving.
Returns: (int) The item's current count. If not seen, 0.
"""
counter = {
'a': 2,
'b': 3,
}
assertEqual(2, get_count(counter, 'a'))
assertEqual(3, get_count(counter, 'b'))
assertEqual(0, get_count(counter, 'c'))
3.2. Red fish¶
In Lecture 5 Exercises (Part 1), we wrote a function num_times(s, letter) that returned how many times letter appears in s.
Now, we want to rewrite this function using a dictionary.
def num_times(s, letter):
"""Counts how many times `letter` appears in `s`.
Arguments:
s (str): The string in which to look for `letter`.
letter (str): The letter whose occurences to count.
Returns: (int) The number of times `letter` appears in `s`.
Effects: None.
"""
assertEqual(2, num_times("hello", "l"))
assertEqual(0, num_times("intermediate", "s"))
assertEqual(0, num_times("", "s"))
3.3 Blue fish¶
Previously, we wrote a function that found the most common character in a string. Now we will rewrite that function using a dictionary.
Write a function most_common_char(s) that takes in a string s and finds the most common character in a string. If there is more than one character tied for the most common character, return any one.
For example, most_common_char('chronixx') == 'x'. Also, most_common_char('common') should return either m or n.
Hint: You can use the get_count function defined above to simplify your code!
def most_common_char(s):
"""Finds the most common character in `s`.
Arguments:
s (str): The input string.
Returns: (str) A character which occurs the most frequently in `s.
Effects: None.
"""
assertEqual('l', most_common_char('hello'))
assertEqual('b', most_common_char('aabbbccdd'))
4. Group By First Character of Name.¶
Warm-up¶
We are given a list of strings names that contains the names of students in a classroom. As a warm-up, we want you to count the number of students that have similar first name initials.
Write a function num_similar_first_letters for this problem.
Example: num_similar_first_letters(['Daniel', 'Basi', 'Bereket', 'Dim', 'Leello'] returns {'B': 2, 'D': 2, 'L': 1}
def num_similar_first_letters(names):
"""finds the number of people with similar first character of names
Arguments:
names (list): The input list contianing strings.
Returns:
(dict) keys: (str) first letter of the names,
values: (int) number of people with same first letter in the name
Effects: None.
"""
names = ['Daniel', 'Basi', 'Bereket', 'Dim', 'Leello']
assertEqual(num_similar_first_letters(names), {'B': 2, 'D': 2, 'L': 1})
Now, the teacher of the class wants to group the students so that students having similar first name initials are grouped together in a list.
Write a function called group_by_initials to solve this problem.
Example, For example, group_by_initials(['Daniel', 'Basi', 'Bereket', 'Dim', 'Leello']
returns {'B': ['Basi', 'Bereket'], 'D': ['Daniel', 'Dim'], 'L': ['Leello']}
Use dictionary to solve this problem.
def group_by_initials(names):
"""Groups students by the first letter of their first name.
Arguments:
names (list): The input list contianing strings.
Returns: (dict)
key: (str) First letter of the name.
values: (List[str]) List of names that have the corresponding first letter.
Effects: None.
"""
names = ['Daniel', 'Basi', 'Bereket', 'Dim', 'Leello']
want = {
'B': ['Basi', 'Bereket'],
'D': ['Daniel', 'Dim'],
'L': ['Leello'],
}
assertEqual(want, group_by_initials(names))
5.¶
We are given a dictionary friends mapping people to their friends. We want to write a function getFriendsOfFriends(d) where d would be that dictionary mapping people to their friends, that returns anonther dictionary mapping the same keys of people to friends of their friends. We can assume each person can't be friends with themselves.
For example,
getFriendsOfFriends({'Amy': ['Daniel', 'Basi', 'Teddy'],
'Teddy': ['Rupal', 'Elvis', 'Amy']})
returns {'Amy': ['Rupal', 'Elvis'], 'Teddy': ['Daniel', 'Basi']}
def getFriendsOfFriends(friends):
# Fill in your code here.
friends = {
'Basi': ['Leello', 'Jessica', 'Corina', 'Isabelle'],
'Jessica': ['Rupal', 'Daniel', 'Dim'],
'Arash': ['Will', 'Mike'],
'Mike': ['Will', 'Jessica', 'Arash'],
'Corina': ['Basi', 'Leello'],
'Isabelle': ['Arash', 'Rupal', 'Mike'],
'Daniel': [] # :(
}
getFriendsOfFriends(friends)
friendsOfFriends = {
'Basi': ['Rupal', 'Daniel', 'Dim', 'Leello', 'Arash', 'Mike'],
'Jessica': [],
'Arash': ['Will', 'Jessica'],
'Mike': ['Rupal', 'Daniel', 'Dim', 'Will'],
'Corina': ['Leello', 'Jessica', 'Isabelle'],
'Isabelle': ['Will', 'Mike', 'Jessica', 'Arash'],
'Daniel': []
}
assert getFriendsOfFriends(
friends) == friendsOfFriends, 'The solution is incorrect'
Question 6¶
There has been a case of food poisoning at the cafeteria Monday. We want to write a function getDistinctEntriesCount(d) that takes d, which is a dictionary mapping the days of the week to a list of entries in the cafeteria. The function should return another dictionary mapping the day to the number of distinct people who ate at the cafeteria each day.
For example, getDistinctEntriesCount({'Monday': ['rupal', 'rupal']}) returns {'Monday': 1}
Also, getDistinctEntriesCount({'Monday': ['rupal', 'rupal'], 'Arb': ['isa']}) returns {'Monday': 1, 'Arb': 1}
def getDistinctEntriesCount(entries):
# Complete the function here
entries = {
'Monday': ['arash', 'arash', 'isa', 'rupal', 'arash', 'leello'],
'Tuesday': ['leello', 'dim', 'arash', 'arash', 'isa', 'rupal', 'nati', 'arash', 'nati', 'basi'],
'Wednesday': ['leello', 'dim', 'dim', 'dim', 'arash'],
'Thursday': ['arash', 'arash', 'rupal', 'arash'],
'Friday': ['leello', 'leello', 'isa', 'dim', 'rupal', 'corina', 'basi', 'nati']
}
getDistinctEntriesCount(entries)
distinctEntries = {
'Monday': 4,
'Tuesday': 7,
'Wednesday': 3,
'Thursday': 2,
'Friday': 7
}
assert distinctEntries == getDistinctEntriesCount(
entries), 'The solution is incorrect'
Now, let's review concepts in time complexity¶
Time complexity is defined as the amount of operations taken by an algorithm to run, as a function of the length of the input. It explains how the time it takes a an algorithm to complete grows with respect to the growth in the size of inputs.
Consider the following code.
The function addNums takes a number n and adds all the numbers from 0 to n - 1
def addNums(n):
answer = 0
for i in range(n):
answer += i
return answer
# For how many iterations is the loop going to run?
# Put your answer below.
Now let's consider another function addNumList(n). It takes in a list of numbers, and calls the addNums function for each item in the list.
def addNumList(lst):
for i in lst:
addNums(i)
# How many times does the addNumList function call addNums()?
# [Your answer here]
# Now, how many addition operations are going to be performed in total?
# [Your answer here]
Consider the following loop
for i in range(len(n)):
for j in range(len(n)):
for k in range(len(n)):
print(i, k, j)
If you run the above code with n = 1000,000 how many times does the function call print ?
# [Your code here]
Let's go back to fibonacci for a second.¶
Assume fib only gets numbers >= 0
def fib(n):
if n <= 1:
return 1
return fib(n-1) + fib(n-2)
Try running values fib(10), fib(20), fib(30), fib(40) ... fib(100)
and see how long it takes for each of the cases. Explain your observation below interms of time complexity.
How many recursive function calls do we need to solve for each of the cases above?