In a tournament that works with a knockout system over $$n$$ rounds, $$2^n$$ ($$n \in \mathbb{N}$$) countries compete for the win. In each round, all remaining countries are linked to another country: the first country plays a match against the second country, the third country against the fourth country, and so on. The winner of each match advances to the next round, whereas the tournament ends for the loser. In this way, the number of countries is halved after each round, yielding a single country after $$n$$ round. That country wins the tournament.

In a knockout system, each match must yield a winner. During the ordinary time of a match, each country gets a score: the higher the score the better. If there's no winner at the end of the ordinary time, both countries can increase their score during extra time. If there's still no winner at the end of the extra time, penalties must decide who wins the match.

In the example below, for each match the score after ordinary time is indicated in yellow, and the score after extra time in gray. In this case, no match was decided by penalties.

If country $$a$$ (with capital $$c_a$$) plays a match against country $$b$$ (with capital $$c_b$$), we use a fixed procedure to determine the winner. After ordinary time, the score for country $$a$$ is equal to the number of common letters with capital $$c_b$$. Analogously, the score for country $$b$$ is equal to the number of common letters with capital $$c_a$$. This includes double letters. Some examples:

• Switzerland (Bern) v Estonia (Tallinn). Switzerland scores 5 goals because the five bold letters in Switzerland also occur in in Tallinn. Estonia scores 2 goals because the letters E and N also occur in Bern. The score after ordinary time is therefore 5–2 and Switzerland wins the match.

• Saudi Arabia (Riyadh) v Bangladesh (Dhaka). Saudi Arabia scores 3 goals because it has three letters in common with Dhaka. This is how it looks like in bold: Saudi Arabia and Dhaka. Note that the third and fourth occurrences of the letter A in Saudi Arabia are not counted, because A only occurs twice in Dhaka. Bangladesh also scores 3 goals, as only the letters A, D and H occur once in Riyadh. As a result, the score after ordinary time is 3–3 and the match continues into extra time.

In extra time, all letters that occur on both sides are taken into account. How this works is most easily explained with a couple of examples:

• Saudi Arabia (Riyadh) v Bangladesh (Dhaka). Saudi Arabia and Dhaka have A and D as common letters. The letter A occurs four times in Saudi Arabia and twice in Dhaka, so it contributes $$4 \times 2 = 8$$ to the score. The letter D only occurs once on both sides, and therefore has a contribution of $$1 \times 1 = 1$$. Saudi Arabia therefore scored $$8 + 1 = 9$$ goals at the end of extra time. Bangladesh scores an extra goal because of the double A and therefore scores a total of 4 goals. The score after extra time is therefore 9–4 and Saudi Arabia wins the match.

• Australia (Canberra) v Grenada (Saint George's) ends 5–5 after ordinary time. The letters A, E, N and R occur in both Grenada and Canberra. The letter A occurs twice on both sides and therefore has a contribution of $$2 \times 2$$. The letters E and N each occur once on both sides and therefore both of them have a contribution of $$1 \times 1$$. The letter R occurs once in Grenada and twice in Canberra and therefore contributes $$1 \times 2$$. This results in a score of $$2 \times 2 + 1 \times 1 + 1 \times 1 + 1 \times 2 = 8$$. Conversely, Australia also scores 8 goals after extra time because of five common letters with Saint George's: A ($$3 \times 1$$), I ($$1 \times 1$$), R ($$1 \times 1$$), S ($$1 \times 2$$) and T ($$1 \times 1$$). This gives a score of 8–8 after the extra time, and so penalties follow.

With penalties, the country that comes first alphabetically wins the match. In the latter example, Australia wins on penalties against Grenada.

Assignment

Define a function letter_frequencies that takes a string $$s$$ (str). The function must return a dictionary (dict) that maps each letter (str) in $$s$$ onto its number of occurrences (int). The function should make no distinction between uppercase and lowercase letters in counting the number of occurrences, and the dictionary should use uppercase letters as keys. If $$s$$ contains characters that are no letters, they must be ignored.

In addition, also define a class Knockout that can be used to simulate the knockout stages of a tournament, based on the scoring procedure introduced above. The location of a CSV file¹ must be passed when creating a tournament (Knockout). Each line of the file must contain the following six field with information about a country, separated by commas: i) country name, ii) capital name, iii) capital latitude, iv) capital longitude, v) country code and vi) continent name.

In addition, a tournament $$t$$ (Knockout) must support at least the following methods:

• A method capital that takes a country name $$c$$ (str). The method must return the capital name of the given country, as written in the given CSV file.
  

• A method ordinary_time that takes two country names $$c_1$$ and  $$c_2$$ (str). The method must return the score (tuple) after ordinary time in a match between the two countries $$c_1$$ and  $$c_2$$ in tournament $$t$$.

• A method extra_time that takes two country names $$c_1$$ and  $$c_2$$ (str). The method must return the score (tuple) after extra time in a match between the two countries $$c_1$$ and  $$c_2$$ in tournament $$t$$.

• A method match that takes two country names $$c_1$$ and  $$c_2$$ (str). The method must return the winner of a match between the two countries $$c_1$$ and  $$c_2$$ in tournament $$t$$.

• A method winner that takes a list or a tuple of $$2^n$$ ($$n \in \mathbb{N}$$) country names (str). The method must return the winner of tournament $$t$$, in which the given countries compete against each other with a knockout system.

  Note

  You may assume that a list or a tuple with $$2^n$$ ($$n \in \mathbb{N}$$) country names is passed to the method, without the need to check this explicitly.

The methods should not make a distinction between uppercase and lowercase letter when processing country names passed as argument, nor when processing capitals of these countries. If a country name that does not occur in the given CSV file is passed to one of these methods, an AssertionError must be raised with the message unknown country.

Example

In the following interactive session, we assume the CSV file countries.csv² to be located in the current directory.

>>> letter_frequencies('Russia')
{'R': 1, 'U': 1, 'S': 2, 'I': 1, 'A': 1}
>>> letter_frequencies('Moscou')
{'M': 1, 'O': 2, 'S': 1, 'C': 1, 'U': 1}
>>> letter_frequencies('Puerto Rico')
{'P': 1, 'U': 1, 'E': 1, 'R': 2, 'T': 1, 'O': 2, 'I': 1, 'C': 1}
>>> letter_frequencies('Guinea-Bissau')
{'G': 1, 'U': 2, 'I': 2, 'N': 1, 'E': 1, 'A': 2, 'B': 1, 'S': 2}

>>> tournament = Knockout('countries.csv3')
>>> tournament.capital('Switzerland')
'Bern'
>>> tournament.capital('Estonia')
'Tallinn'
>>> tournament.ordinary_time('Switzerland', 'Estonia')
(5, 2)
>>> tournament.ordinary_time('Belgium', 'Denmark')
(2, 2)
>>> tournament.ordinary_time('Portugal', 'Austria')
(1, 2)
>>> tournament.ordinary_time('Netherlands', 'Lithuania')
(3, 3)
>>> tournament.extra_time('Belgium', 'Denmark')
(3, 2)
>>> tournament.extra_time('Netherlands', 'Lithuania')
(4, 5)
>>> tournament.match('Switzerland', 'Estonia')
'Switzerland'
>>> tournament.match('Belgium', 'Denmark')
'Belgium'
>>> tournament.match('Portugal', 'Austria')
'Austria'
>>> tournament.match('Netherlands', 'Lithuania')
'Lithuania'
>>> tournament.winner(['Switzerland', 'Estonia', 'Belgium', 'Denmark', 'Portugal', 'Austria', 'Netherlands', 'Lithuania'])
'Switzerland'