Do not use sets, dictionaries, try/except, classes, or recursion this week.
The autograder should reject your submission entirely if you do.
-
movieAwards(oscarResults) [10 pts]
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", "The Shape of Water"),
("Best Actor", "Darkest Hour"),
("Best Actress", "Three Billboards Outside Ebbing, Missouri"),
("Best Director", "The Shape of Water"),
("Best Supporting Actor", "Three Billboards Outside Ebbing, Missouri"),
("Best Supporting Actress", "I, Tonya"),
("Best Original Score", "The Shape of Water")
}
the program should return:
{
"Darkest Hour" : 1,
"Three Billboards Outside Ebbing, Missouri" : 2,
"The Shape of Water" : 3,
"I, Tonya" : 1
}
Note: Remember that sets and dictionaries are unordered! For the example above, the returned set may be in a different order than what we have shown, and that is ok.
-
friendsOfFriends(d) [10 pts]
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 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.
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: your function should not modify the initial provided dictionary!
Note 2: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
Note 3: you may assume that a person will never be included in their own friend set. You should also not include people in their own friends-of-friends sets!
Note 4: 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.
Hint: How is this different or similar to the facebook friends problem?
-
groupAnagrams(S) [10 pts]
Given a list of strings S, group the anagrams together.
Two strings are anagrams if each can be reordered into the other. Treat "a" and
"A" as the same letters (so "Aba" and "BAA" are anagrams).
The function should return a list of groups, in any order. Each group is a set
of strings where all the strings are anagrams of each other.
Some examples:
S = ["eat","tea","tan","ate","nat","bat"]
groupAnagrams(S) will group the strings in the following way:
[{"bat"},{"nat","tan"},{"ate","eat","tea"}]
S = ["own", "read", "dare", "eat", "now", "stop", "now", "spot", "15112", "tea"]
groupAnagrams(S) will group the strings in the following way:
[{"own", "now"}, {"read","dare"}, {"eat","tea"}, {"stop", "spot"}, {"15112"}]
The order of the groups in the returned list is not important. The size
of S will be large, therefore you should avoid using lists
operations as much as possible, otherwise your solution will be too slow and
will timeout. We expect that your code processes an input of 30K words in less
than a minute.
-
largestSumOfPairs(a) [10 pts]
Write the function largestSumOfPairs(a) that takes a list of integers, and returns the largest sum of any two elements in that list, or None if the list is of size 1 or smaller. So, largestSumOfPairs([8,4,2,8]) returns the largest of (8+4), (8+2), (8+8), (4+2), (4+8), and (2+8), or 16.
The naive solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow. Your solution should be more efficient.
-
containsPythagoreanTriple(a) [10 pts]
Write the function containsPythagoreanTriple(a) 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).
A naive solution would be to check every possible triple (a,b,c) in the list. That runs in O(n**3). You'll have to do better than that.
-
recursive capitalizeWords(wordList) [10 pts]
Write a recursive function that takes a list of words and returns a list that
contains all the words capitalized.
For example,
assert(capitalizeWords(['foo', 'bar', 'world', 'hello']) == ['FOO', 'BAR', 'WORLD', 'HELLO'])
Your solution should not use any loops; you must solve the problem using
recursion.
-
Recursion-Only onlyEvenDigits(L) [10 pts]
Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the
same numbers only without their odd digits
(if that leaves no digits, then replace the number with 0). So:
onlyEvenDigits([43, 23265, 17, 58344]) returns
[4, 226, 0, 844].
Also the function returns the empty list if the original list is empty.
Remember to not use strings.
You may not use loops/iteration in this problem.
Hint: We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.
-
recursive alternatingSum(lst) [10 pts]
Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list,
where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3).
If lst is empty, return 0.
-
recursive isBalanced(exp) [10 pts]
Write the function isBalanced(exp) that checks if a string has properly "balanced" characters:
You may assume that the string contains only parentheses, brackets, less/greater-than, and curly braces.
You should return true or false according to whether that expression has properly balanced operators.
Your function should operate recursively by making use of the recursive insight that such a string is balanced if and
only if one of the following two conditions holds:
- The string is empty.
- It contains "()" , "[]" , "<>" , or "{}" as a substring and is still balanced if you remove that substring.
For example, you can show that the string "[(){}]" is balanced by the following recursive chain of reasoning:
isBalanced("[()<{}>]") is true because
isBalanced("[<{}>]") is true because
isBalanced("[<>]") is true because
isBalanced("[]") is true because
isBalanced("") is true because the argument is empty.
You must verify exactly the definition of balance described above. The
above definition implies that a string such as "([)]" or ")(" is not balanced,
because it does not meet condition 1 or 2 above. You may take advantage of
various member functions of string s such as length , find , substr , replace ,
and erase . But your solution should not use any loops or data structures; you
must solve the problem using recursion. Your solution should avoid redundancy;
if you are repeating similar code, extract it into a helper function.
-
recursive isPalindrome(word) [10 pts]
A string is a palindrome if it is exactly the same forwards and backwards. Write
a recursive function that takes a string and returns True if the
string is palindrome, False otherwise.
For example,
assert(isPalindrome("abcba")==True)
assert(isPalindrome("accba")==False)
assert(isPalindrome("a")==True)
Your solution should not use any loops; you must solve the problem using recursion.