Write each of the functions below. Use the function names and parameters specified.
The unit test is at CodeHS and at GitHub. If you do, you'll get a report file each time your run. As always, the unit test will crash if not all functions are defined.
You now know that it's often helpful to write helper functions that are not themselves united tested. Remember: keep your functions single-task if at all possible; and if this means that some of the work done in a function will be offloaded into another, then so be it. For instance, my make_perm functions has three helper functions.
Many of the functions below will output dictionaries, and some of those will be complex. For instance, word_count outputs a dictionary in which the keys are words in a longish passage and the values are word-counts.
The same is true for some of those functions that output strings: the outputs are sometimes complex.
This means that, if your function outputs an incorrect value, it can be tricky to find the place in the output where it went wrong. This is why is wrote you two little functions - compare_strings and compare_dcts. They will take two objects, compare them, and then give a detailed report about how they differ (if in fact they do differ).
Let's make use of a dictionary to count the number of each letter in a string. The key in each key-value pair should be a letter, and its associated value should be the number of times that letter occurs in the string. We won't distinguish between uppercase and lowercase; and let's agree that the keys in the dictionary returned will be lowercase
The function should be named letter_count. It should take a string and return a dictionary. It is not a mutator.
Test Cases:
>>> Arthur = "Strange women lying in ponds, distributing swords, is no basis for a system of government!"
>>> letter_count(Arthur)
{'a': 3, 'b': 2, 'c': 0, 'd': 3, 'e': 5, 'f': 2, 'g': 4, 'h': 0, 'i': 7, 'j': 0, 'k': 0, 'l': 1, 'm': 3, 'n': 9, 'o': 7, 'p': 1, 'q': 0, 'r': 5, 's': 10, 't': 5, 'u': 1, 'v': 1, 'w': 2, 'x': 0, 'y': 2, 'z': 0}
>>> letter_count('')
{'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
Write a function named word_count that takes a string and returns a dictionary whose keys are words and whose values are word counts. The value associated with a particular key will of course be the count of that word in the string. Don't distinguish between uppercase and lowercase; your keys should all be all lowercase. Assume that the last letter of a word always occurs immediately before a space, a comma a semicolon or a period.
The function is not a mutator.
Test Cases:
>>> LotR = '''Three Rings for the Elven-kings under the sky,
Seven for the Dwarf-lords in their halls of stone,
Nine for Mortal Men doomed to die,
One for the Dark Lord on his dark throne,
In the Land of Mordor where the Shadows lie.
One Ring to rule them all, One Ring to find them,
One Ring to bring them all, and in the darkness bind them,
In the Land of Mordor where the Shadows lie.'''
>>> word_count(LotR)
{'three': 1, 'rings': 1, 'for': 4, 'the': 9, 'elven-kings': 1, 'under': 1, 'sky': 1, 'seven': 1, 'dwarf-lords': 1, 'in': 4, 'their': 1, 'halls': 1, 'of': 3, 'stone': 1, 'nine': 1, 'mortal': 1, 'men': 1, 'doomed': 1, 'to': 4, 'die': 1, 'one': 4, 'dark': 2, 'lord': 1, 'on': 1, 'his': 1, 'throne': 1, 'land': 2, 'mordor': 2, 'where': 2, 'shadows': 2, 'lie': 2, 'ring': 3, 'rule': 1, 'them': 4, 'all': 2, 'find': 1, 'bring': 1, 'and': 1, 'darkness': 1, 'bind': 1}
Recall that dictionaries are not ordered. The order of key-value pairs in your output might not match mine.
Write a function named to_morse that translates a alphanumeric string into Morse code. Use the International Telecommunication Union standard. The output should in all cases have precisely once space between any two Morse symbols. You may assume that the input string will contain only letters, numbers and spaces.
The function is not a mutator.
Be careful not to place a space at the end of your output. You won't see it, but the unit test will.
Test Cases:
>>> chars = 'abcdefghijklmnopqrstuvwxyz1234567890'
>>> to_morse(chars)
'.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.. .---- ..--- ...-- ....- ..... -.... --... ---.. ----. -----'
>>> to_morse('sos')
... --- ...
>>> to_morse('')
In a substitution cipher, each letter of the alphabet is mapped to a unique letter; and that association of letters is used to encrypt a string. For instance, if 'c' maps to 'd', 'a' maps to 'o' and 't' maps to 'g', the encryption of 'cat' is 'dog'.
Write a function named subst_cipher that implements a substitution cipher. It should take a dictionary and a string and return a string. The input string will be encrypted by use of the letter associations in the dictionary; and the encrypted string that results will be returned.
Note that, though I'll give you a dictionary that includes only lower case letters, I wish you to replace upper case with upper case. How? The upper case maps should follow the lower case ones. If for instance the given dictionary maps 'a' to 'm', then 'A' should map to 'M'.
When you encrypt, leave any non-letters unchanged; and if you encounter a newline character (which is '\n') convert it into a space.
The function is not a mutator.
Test Cases:
>>> letter_map = {'a': 'm', 'b': 'k', 'c': 'n', 'd': 'o', 'e': 'c', 'f': 'v', 'g': 'w', 'h': 'z', 'i': 'b', 'j': 't', 'k': 'y', 'l': 'r', 'm': 'x', 'n': 'd', 'o': 'u', 'p': 'p', 'q': 'a', 'r': 'i', 's': 's', 't': 'f', 'u': 'q', 'v': 'e', 'w': 'l', 'x': 'g', 'y': 'j', 'z': 'h'}
>>> subst_cipher(letter_map, 'Spam and Eggs')
'Spmx mdo Cwws'
Now let's do the opposite. Take a letter map like the example for above and a encrypted string (that is, the output of the subst_cipher function above) and returns the original, unencrypted string. Name your function decrypt.
The function is not a mutator.
Test Cases:
>>> letter_map = {'a': 'm', 'b': 'k', 'c': 'n', 'd': 'o', 'e': 'c', 'f': 'v', 'g': 'w', 'h': 'z', 'i': 'b', 'j': 't', 'k': 'y', 'l': 'r', 'm': 'x', 'n': 'd', 'o': 'u', 'p': 'p', 'q': 'a', 'r': 'i', 's': 's', 't': 'f', 'u': 'q', 'v': 'e', 'w': 'l', 'x': 'g', 'y': 'j', 'z': 'h'}
>>> decrypt(letter_map, 'pjfzud')
'python'
>>> decrypt(letter_map, subst_cipher(letter_map, 'spam and eggs'))
'spam and eggs'
decrypt and subst_cipher are inverses of one another; each undoes what the other does.
Write a function named next_date that takes three inputs - day, month and year - and returns the day, month and year of the next day. The inputs and the outputs should all be integers. (Notice again the order I specify. Day first. Month second. Year last.)
We could have done this back in the Selection chapter, but dictionaries make it possible to really shorten the code. What dictionary will you make? I suggest one that has months (given as integers) for keys and the number of days in that month for values.
Also, I do expect that your code will give the proper output for the 28th and the 29th of February in a leap year. (Recall that in a previous chapter we wrote a function that returns True when and only when an input year is a leap year.)
Raise a value error if the input date is invalid.
The function is not a mutator.
Test Cases:
>>> next_date(1,1,2020)
(2, 1, 2020)
>>> next_date(31,1,2020)
(1, 2, 2020)
>>> next_date(28,2,2020)
(29, 2, 2020)
>>> next_date(29,2,2020)
(1, 3, 2020)
>>> next_date(31,12,2020)
(1, 1, 2021)
>>> next_date(32,12,2020)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 15, in next_date
ValueError: invalid date
Write me a function named number_name that takes an integer and, as it were, writes it out in words. 1 is "one", 11 is "eleven", 101 is "one hundred one", 30841 is "thirty thousand eight hundred forty one". Don't use dashes. Keep it all lower case. No "and"s should be used in the output. Be able to handle up to decillions.
The function is not a mutator.
Test Cases:
>>> number_name(123456789)
'one hundred twenty three million four hundred fifty six thousand seven hundred eighty nine'
>>> number_name(9876543210987654321)
'nine quintillion eight hundred seventy six quadrillion five hundred forty three trillion two hundred ten billion nine hundred eighty seven million six hundred fifty four thousand three hundred twenty one'
In a dictionary, every key must have one and only one associated value. So for instance the dictionary {1: 'a', 1: 'b'} cannot exist, for it would associate the key 1 with the value 'a' and the value 'b'.
A value, however, can have more than one associated key. For instance the dictionary {1; 'a', 2: 'a'} is perfectly possible.
Let's borrow a term from mathematics. Let's say that a dictionary is bijective if no value is associated with more than one key. So {1: 'a', 2: 'b'} is bijective and {1: 'a', 2: 'a'} is not.
Write is function named is_bijective that takes a dictionary and returns True if that dictionary is bijective and False otherwise.
The function is not a mutator.
Test Cases:
>>> is_bijective({1: 'a', 2: 'a'})
False
>>> is_bijective({1: 'a', 2: 'b'})
True
>>> is_bijective({})
True
If a dictionary isn't bijective, then at least one value has two or more associated keys. Let the deviation degree of a dictionary be the greatest number of times that any value appears in a dictionary. If a dictionary has deviation degree 0 or 1, it's bijective. If a dictionary has deviation degree 2, at least one value appears twice and no value appears more than twice, etc.
Write a function name deviation that takes a dictionary and returns a positive integer that gives its deviation degree.
The function is not a mutator.
Test Cases:
>>> deviation({1: 'a', 2: 'b', 3: 'c'})
1
>>> deviation({1: 'a', 2: 'b', 3: 'a'})
2
>>> deviation({})
0
Write a function named reverse_dct that takes a dictionary that reverses all its key-value pairs it if it's bijective and raises a value error if it's not. (How does one raise a value error? One perhaps looks again at the Lists and Tuples function set. Or one asks Google.)
The function is not a mutator.
Test Cases:
>>> reverse_dct({1: 'a', 2: 'b', 3: 'c'})
{'a': 1, 'b': 2, 'c': 3}
>>> reverse_dct({})
{}
>>> reverse_dct({1: 'a', 2: 'b', 3: 'a'})
ValueError: Not Reversable
Let's say we have these two dictionaries: D = {'a':1, 'b':2, 'c':3} and T = {1:True, 2:False, 3:True}. The composition of D with T is {'a':True, 'b':False, 'c':True}. (Call the composition "C".)
How did we get that? Note that the keys in C are the same as the keys in D; and note that the values in C are the same as the values in T. How does a key in C gets its value? We take a value from D, look for it as a key in T, and (if we find it) take the value of that key from T. An example will help. Consider the key of 'a' from D. D associates 'a' with the value 1. So we go to T and look for the key 1. It's there, and its value is True. Thus in C the key of 'a' is associated with True.
So we had 'a':1 and 1:True and ended up with 'a':True. Composition as it were eliminated the middleman of 1.
We could of course do this with more than two dictionaries. For instance if we have 'z':1 in the first, 1:True in the second and True:None in the third, the composition would have 'z':None. 'z' carried us to 1, which carried us to True, which carried us to None. So when we compose, 'z' carries us to None.
Write me a function named dict_comp that takes a list of dictionaries and returns a dictionary that is the composition of the input list of dictionaries (in the order given of course).
Do no assume that every key in the first dictionary in the input list of dictionaries will appear as a key in the output dictionary. This will happen when some key in a dictionary in the input list is not a value in the dictionary before it.
Note that the composition of dictionary D with the dictionary T need not be the same as (indeed will probably be different from) the composition of dictionary T with dictionary D. You'll see an example of this below.
The function is not a mutator.
Test cases:
>>> Q = {1:2, 2:4, 3:6}
>>> R = {2:4, 4:16, 6:36}
>>> S = {4:2, 16:8, 36:18}
>>> dict_comp([Q, R, S])
{1: 2, 2: 8, 3: 18}
>>> dict_comp([Q, S])
{2: 2}
>>> dict_comp([S, Q])
{4: 4}
>>> dict_comp([R, Q])
{}
>>> dict_comp([Q, {}])
{}
>>> dict_comp([{}, {}])
{}
When we permute a sequence of objects, we change their order. For instance, a permutation of "abc" is "cba"; another is "bac".
Consider the permutation that takes "abc" and returns "cba". The position that was occupied by "a" is now occupied by "c". The position that was occupied by "b" is still occupied by "b". (That is, "b" is fixed.) The position that was occupied by "c" is now occupied by "a". So we might specify the permutation in this way:
"a" → "c", "b" → "b", "c" → "a"
Read this as: "a maps to c, b maps to b and c maps to a".
Here's a compact way to represent the permutation that takes "abc" to "cba":
(ac)(b)
We read from left to right; and inside each set of parentheses, we read from left to right. Thus we begin with "(ac)", and in that we go from "a" to "c". What does "(ac)" tell us? Since "c" follows "a", it tells us that "a" maps to "c"; and since "c" is the last letter, we wrap back around to the start and say that "c" maps to "a". Of course, then, "(b)" means that "b" maps to itself.
Note that, if a letter maps to itself, we typically don't include it. So the above permutation is typically given as just "(ac)", not "(ac)(b)".
Another example: "(acb)(de)" tells us that "a" maps to "c", "c" maps to "b", "b" maps to "a", "d" maps to "e" and "e" maps to "d".
Now let's have an example where we apply a permutation specified in this way. Let's say we begin with the sequence "abcdefg" and apply the permutation given by "(aeg)(bd)(cf)". We should get:
"edfbgca"
Take a moment to verify that this is correct. If you can't do it by hand, you won't be able to write code to do it.
Write me a function named apply_perm that takes a sequence of letters (like the "abc" and "abcdefg" from the examples above) and a permutation specified with the parentheses notation described above (like the "(aeg)(bd)(cf)" of the last example) and returns the result of that permutation applied to that sequence.
Let's agree to represent the permutation that leaves everything where it is as simply "()". (That's the identity permutation.) You may assume that in a permutation specified in the way described above, no letter appears more than once.
Dictionaries do seem like the obvious way to store and to apply a permutation. For instance, the dictionary {'a':'b', 'b':'c', 'c':'a'} tells us that 'a' maps to 'b', 'b' maps to 'c' and 'c' maps to 'a'.
Test cases:
>>> apply_perm('', '()')
''
>>> apply_perm('abc', '()')
'abc'
>>> apply_perm('abc', '(ca)')
'cba'
>>> apply_perm('abcdefg', '(aeg)(bd)(cf)')
'edfbgca'
>>> apply_perm('abcdefghijklmnop', '(adfg)(imnop)(kl)')
'dbcfegahmjlknopi'
Let's consider permutations that contain multiple occurrences of a letter. An example is "(abc)(cb)". Note that "c" occurs both in the first and second chunk.
How do we interpret a permutation with multiple occurrences of a letter? I'll take "(abc)(cb)" as my example.
We read from left to right; and we begin with the leftmost chunk, which in this case is "abc". (Let's agree to call a sequence of letters flanked by parentheses a chunk.) So chunk one tells us that "a" maps to "b".
Now move to the second chuck, the "cb" chunk, and look for a "b". It's there, and it maps "b" to "c".
So we have "a" mapped to "b" and then "b" mapped to "c". This is the same as if we simply mapped "a" to "c". The middleman "b" is dropped.
Now let's do "b". "abc" maps "b" to "c" and then "cb" maps that "c" to "b". So, when the middleman is dropped, "b" maps to "b".
Finally, "abc" maps "c" to "a"; and since "a" is not in "cb", "c" remains mapped to "a".
In sum (where as before the arrow means "maps to"): "a" → "c", "b" → "b", "c" → "a".
If you peek back at the previous function's description, you'll find that "(abc)(cb)" does precisely what "(ac)" did! They are thus equivalent permutations; they produce the same rearrangement. As should be clear, we now allow letters to occur in multiple chunks.
Write a function named eq_perms that takes a pair of permutations and determines whether that pair are equivalent.
Test Cases:
>>> eq_perms('()', '()')
True
>>> eq_perms('(ab)', '(ba)')
True
>>> eq_perms('(acb)', '(abc)')
False
>>> eq_perms('(ab)(ba)', '()')
True
>>> eq_perms('(adbc)(bd)', '(bd)(adbc)')
False
>>> eq_perms('(ac)(bd)(cafeg)(hamec)(cad)', '(ameghdbcf)')
True
Two permutations are inverses of one another is one "undoes" what the other does. More precisely, two permutations are inverses if when we apply one to a sequence and then the other to that rearrangement, the sequence ends in the same order as it began.
So, for instance, the permutations "(acb)" and "(cab)" are inverses of one another. For if we apply the "(acb)" to the sequence "abc", we get "cab"; and if we apply "(cab)" to that, we get "abc", which is where we began.
Write me a function named inverse_perms that takes a pair of permutations and returns True if they are inverses of one another and False if they are not.
Test Cases:
>>> inverse_perms('()', '()')
True
>>> inverse_perms('(a)', '()')
True
>>> inverse_perms('(a)', '(b)')
True
>>> inverse_perms('(ab)', '()')
False
>>> inverse_perms('(ab)', '(ba)')
True
>>> inverse_perms('(abc)', '(abc)')
False
>>> inverse_perms('(abc)', '(bac)')
True
>>> inverse_perms('(cdeg)(abdef)', '(ecg)(fdba)')
True
Let's say we take a sequence and permute it. And then take the result and permute it that same way again. And then take the result and permute it that same way again. Etc. We will, if we continue lone enough, eventually arrive back at the original arrangement. (You might take a moment to think about why that has to be true.)
For instance, if we apply the permutation "(ab)" to the sequence "abc", we get "bac". And if we then apply "(ab)" to "bac", we get "abc". That's where we began!
Notice that in this case we had to apply the permutation "(ab)" twice to arrive back at the original arrangement.
Here's another example. The sequence is "abcdefg" and the permutation is "(abd)(cf)(bdfg)". Here's the sequence that gets us back to the original arrangement:
dfgaecb
acbdegf
dgfaebc
abcdefg
So in this case we had to apply the permutation "(abd)(cf)(bdfg)" four times to arrive back at the original arrangement.
Let's say that the number of times we must apply a permutation to get back to the original arrangement is the cycle length of that permutation.
Write a function named cycle_length that takes a permutation and returns how many times the permutation must be applied to a sequence to bring it back to its original arrangement. Note that I do not need to specify the sequence, for it can be any sequences that contains at least the letters in the permutation.
Test cases:
>>> cycle_length('()')
1
>>> cycle_length('(ab)')
2
>>> cycle_length('(abc)')
3
>>> cycle_length('(ab)(ab)')
1
>>> cycle_length('(abd)(cf)(bdfg)')
4
We saw above that the permutations "(abc)(cb)" and "(ac)" are equivalent; that is, they rearrange a sequence in precisely the same way. Note too that the second, unlike the first, contains no more than one occurrence of any letter.
In general, every permutation that contains more than one occurrence of a letter is equivalent to one that does not contain multiples occurrences of any letter.
Write a function named compress_perm that takes a permutation and produces an equivalent permutation without repetition.
There are various forms that such an equivalent permutation might make, for there are always ways to rewrite a permutation. For instance, "(abc)(de)" is equivalent to each of these permutations (and others too): "(de)(abc)", "(cab)(de)", "(ed)(cab)". The unit test will count any of the correct forms as correct.
Test Cases:
>>> compress_perm('()')
'()'
>>> compress_perm('(a)')
'()'
>>> compress_perm('(a)(b)')
'()'
>>> compress_perm('(ab)')
'(ab)'
>>> compress_perm('(ab)(ab)')
'()'
>>> compress_perm('(abc)(bac)')
'()'
>>> compress_perm('(abc)(caf)(gd)(deh)')
'(ab)(cf)(gehd)'
Write each of the set functions described below. You may iterate through a set with for. You may use the add method. You may use the in operator. You may create an empty set with set(). You may do nothing else set-related.
No function described below is a mutator. Each should create a return a new set.
The union of two sets S and T is the set that contains all and only those elements contained by either S or T.
Name: union
Parameter(s): two sets S and T
Return: the union of S and T
>>> S = {1, 2, 3}
>>> T = {3, 4, 5}
>>> union(S, T)
{1, 2, 3, 4, 5}
The intersection of two sets S and T is the set that contains all and only those elements contained in both S and T.
Name: intersect
Parameter(s): two sets S and T
Return: the intersection of S and T
>>> S = {1, 2, 3}
>>> T = {3, 4, 5}
>>> intersect(S, T)
{3}
The difference of sets S and T is the set of all elements of S that are not in T.
Name: diff
Parameter(s): two sets S and T
Return: the set of all elements of S that are not in T
>>> S = {1, 2, 3}
>>> T = {3, 4, 5}
>>> diff(S, T)
{1, 2}
Set S is a subset of set T just if every element of S is an element of T.
Name: is_subset
Parameter(s): two sets S and T
Return: True if every element of S is an element of T, False otherwise
>>> S = {1, 2, 3}
>>> T = {1, 2}
>>> U = {1, 2, 3}
>>> V = {1, 2, 3, 4}
>>> is_subset(T, S)
True
>>> is_subset(U, S)
True
>>> is_subset(V, S)
False
Set S is a proper subset of set T just if S is a subset of T and T contains at least one element that is not an element of S.
Name: proper_subset
Parameter(s): two sets S and T
Return: True if S is a subset of T that is not identical to T, False otherwise
>>> S = {1, 2, 3}
>>> T = {1, 2}
>>> U = {1, 2, 3}
>>> V = {1, 2, 3, 4}
>>> proper_subset(T, S)
True
>>> proper_subset(U, S)
False
>>> proper_subset(V, S)
False
The power set of a set S is the set of all subsets of S.
Name: power_set
Parameter(s): set S
Return: the list of all subsets of S
Note that the powerset of a set includes the empty set. Note too that if S has n elements, then the powerset of S has 2**n elements.
(You might wander why I asked for the list of subsets of S and not the set of subsets of S. We might discuss that. Or you could Google it.)
Test cases:
>>> S = {1, 2, 3}
>>> power_set(S)
[set(), {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}]
You see the empty set, don't you? It's set(). The empty set is the set that contains nothing.