Back in the days, phone numbers were looked up in a phone book: a long listing of telephone subscribers in a geographical area, with subscriber names listed in alphabetical order. The advent of the Internet and smart phones in the 21st century greatly reduced the need for paper phone books.
Assignment
Because the list of phone numbers could grow quite long, phone books were traditionally subdivided into multiple volumes. Each of these volumes contained the phone numbers of subscribers whose names start with a sequence of letters from the alphabet. We will use two ways of describing a partitioning of a phone book.
A string representation (str) describes each volume of a partitioning by two uppercase letters that are separated by a dash. These uppercase letters are the first and the last letter in the sequence of letters of the alphabet with which the names in the volume start. The successive volumes are separated from each other by a single space. Here's an example string representation of a partitioning of a phone book:
A-D E-J K-O P-Z
The string representation should describe a partitioning of the entire alphabet and the volumes must be consecutive. As a shorthand, volumes that are limited to names starting with a single letter are simply represented by this one letter. As a consequence, we do not write D-D but D for short.
A numerical representation describes a partitioning of a phone book as a tuple of strictly positive integers (int). Each of these integers indicates the number of letters in the sequence of letters of the alphabet with which the names in the volume start. For example, the partitioning that was used as an example above can also be described as $$(4, 6, 5, 11)$$: the first volume contains the first 4 letters (A-D), the second volume the next 6 letters (E-J), the third volume the next 5 letters (K-O) and the fourth volume the last 11 letters (P-Z). It must hold that the sum of the numbers of the numerical representation equals 26.
Say that we know the distribution of the first letters of telephone subscriber's last names, for example:
A B C D E F G H I J K L M N 0 P Q R S T U V W X Y Z 16 4 17 10 15 4 4 6 7 14 9 17 27 6 1 9 0 12 20 8 0 3 4 0 3 4
There are 220 names in total. The telephone company has decided to print 4 volumes. Ideally, each of these volumes should thus contain $$\frac{220}{4} = 55$$ names. One possible partitioning is A-D E-J K-O P-Z with counts of 47, 50, 60 and 63 names. In absolute value these counts deviate 8, 5, 5 and 8 names from the ideal 55 names per volume. We refer to the total sum of these deviations as the delta of the partitioning of the phone book. For this partitioning, the delta is thus equal to 26. Another partitioning is A-G H-O P Q-Z, with name counts of 70, 87, 9 and 54, deviations of 15, 32, 46 and 1 from the ideal 55 names per volume, and a delta of 94. We might ask you to look for the optimal partitioning (the one having the smallest delta), but this would lead us to far. You are asked to:
-
Write a function volumes that takes the numerical representation (tuple) of a partitioning of a phone book. If the argument passed to the function does not represent a valid numerical representation of a partitioning of a phone book, the function must raise an AssertionError with the message invalid partitioning. Otherwise, the function must return the string representation (str) of the given partitioning.
-
Write a function counts that takes the string representation (str) of a partitioning of a phone book. If the argument passed to the function does not represent a valid string representation of a partitioning of a phone book, the function must raise an AssertionError with the message invalid partitioning. Otherwise, the function must return the numerical representation (tuple) of the given partitioning.
-
Write a function delta that takes two arguments: i) a partitioning of a phone book and ii) a sequence (list or tuple) containing the distribution of the first letters of telephone subscriber's last names (int). If the first argument does not represent a valid numerical or string representation of a partitioning of a phone book, the function must raise an AssertionError with the message invalid partitioning. Otherwise, the function must return the delta (float) of the given partitioning of the phone book for the given distribution of the first letters of telephone subscriber's last names.
Examples
>>> volumes((4, 6, 5, 11))
'A-D E-J K-O P-Z'
>>> volumes((7, 8, 1, 10))
'A-G H-O P Q-Z'
>>> volumes((4, 7, 5, 10))
'A-D E-K L-P Q-Z'
>>> volumes((8, 3, 9, 7))
Traceback (most recent call last):
AssertionError: invalid partitioning
>>> counts('A-D E-J K-O P-Z')
(4, 6, 5, 11)
>>> counts('A-G H-O P Q-Z')
(7, 8, 1, 10)
>>> counts('A-D E-K L-P Q-Z')
(4, 7, 5, 10)
>>> counts('A-D F-K L-P Q-Z')
Traceback (most recent call last):
AssertionError: invalid partitioning
>>> names = (16, 4, 17, 10, 15, 4, 4, 6, 7, 14, 9, 17, 27, 6, 1, 9, 0, 12, 20, 8, 0, 3, 4, 0, 3, 4)
>>> delta('A-D E-J K-O P-Z', names)
26.0
>>> delta((7, 8, 1, 10), names)
94.0
>>> delta('A-D E-K L-P Q-Z', names)
18.0
>>> delta(42, names)
Traceback (most recent call last):
AssertionError: invalid partitioning