In een toernooi strijden $$2^n$$ ($$n \in \mathbb{N}$$) landen om de overwinning. Er wordt gewerkt met een knockoutsysteem dat loopt over $$n$$ ronden. In elke ronde worden alle landen aan een ander land gekoppeld: het eerst land speelt een wedstrijd tegen het tweede land, het derde land tegen het vierde land, enzoverder. De winnaar van elke wedstrijd gaat door naar de volgende ronde en voor de verliezer is het toernooi voorbij. Op die manier wordt het aantal landen bij elke ronde gehalveerd, en blijft er na $$n$$ ronden nog één land over. Dat land wint het toernooi.

In een knockoutsysteem moet elke wedstrijd een winnaar opleveren. Tijdens de reguliere speeltijd van een wedstrijd behaalt elk land een score: hoe hoger de score hoe beter. Als er na de reguliere speeltijd nog geen winnaar is, dan kunnen beide landen in de extra speeltijd hun score nog verhogen. Als er na de extra speeltijd nog altijd geen winnaar is, dan moeten penalties uitmaken wie de wedstrijd wint.

In onderstaand voorbeeld wordt de score na de reguliere speeltijd van elke wedstrijd aangegeven in het geel, en de score na de extra speeltijd in het grijs. In dit geval werd geen enkele wedstrijd beslist na het nemen van penalties.

Als land $$a$$ (met hoofdstad $$h_a$$) een wedstrijd speelt tegen land $$b$$ (met hoofdstad $$h_b$$) dan gebruiken we een vaste procedure om de winnaar te bepalen. Na de reguliere speeltijd is de score voor land $$a$$ gelijk aan het aantal overeenkomstige letters met hoofdstad $$h_b$$. Analoog is de score voor land $$b$$ gelijk aan het aantal overeenkomstige letters met hoofdstad $$h_a$$. Dit is inclusief dubbele letters. Enkele voorbeelden:

• Switzerland (Bern) tegen Estonia (Tallinn). Switzerland scoort 5 doelpunten want de vijf vetgedrukte letters in Switzerland zitten ook in Tallinn. Estonia scoort 2 doelpunten omdat alleen de E en de N overeenkomen met de letters van Bern. De score na de reguliere speeltijd is dus 5–2 en Switzerland is de winnaar.

• Saudi Arabia (Riyadh) tegen Bangladesh (Dhaka). Saudi Arabia scoort 3 doelpunten want we kunnen drie overeenkomstige letters vinden in Dhaka. Vetgedrukt ziet dat er zo uit: Saudi Arabia en Dhaka. Merk dus op dat de derde en vierde A in Saudi Arabia niet meegeteld worden, omdat de letter A slechts tweemaal voorkomt in Dhaka. Ook Bangladesh scoort 3 doelpunten, want alleen de letters A, D en H komen enkelvoudig voor in Riyadh. De score na de reguliere speeltijd is dus 3–3 en er volgt extra tijd.

In de extra tijd doen alle letters die potentieel overeenkomstig zijn ook mee. Dat is het makkelijkst uit te leggen aan de hand van enkele voorbeelden:

• Saudi Arabia (Riyadh) tegen Bangladesh (Dhaka). Saudi Arabia en Dhaka hebben A en D als gemeenschappelijke letters. De letter A komt vier keer voor in Saudi Arabia en twee keer in Dhaka, waardoor de bijdrage van de letter A gelijk is aan $$4 \times 2 = 8$$. De letter D komt aan beide kanten maar één keer voor, en heeft dus een bijdrage van $$1 \times 1 = 1$$. Saudi Arabia heeft aan het einde van de extra tijd dus $$8 + 1 = 9$$ doelpunten gescoord. Bangladesh scoort een extra doelpunt vanwege de dubbele A en komt dus op een totaal van 4 doelpunten. De score na de extra speeltijd is dus 9–4 en Saudi Arabia is de winnaar.

• Australia (Canberra) tegen Grenada (Saint George's) eindigt op 5–5 na de reguliere speeltijd. De letters A, E, N en R komen zowel in Grenada als in Canberra voor. De letter A komt tweemaal voor aan beide kanten en heeft dus een bijdrage $$2 \times 2$$. De letters E en N komen elk eenmaal voor aan beide kanten en hebben dus elk een bijdrage van $$1 \times 1$$. De letter R komt eenmaal voor in Grenada en tweemaal in Canberra en draagt dus $$1 \times 2$$ bij. Dit levert dus een score op van $$2 \times 2 + 1 \times 1 + 1 \times 1 + 1 \times 2 = 8$$. Andersom scoort Australia ook 8 punten omwille van vijf gemeenschappelijk letters met Saint George's: A ($$3 \times 1$$), I ($$1 \times 1$$), R ($$1 \times 1$$), S ($$1 \times 2$$) en T ($$1 \times 1$$). Dit geeft een score van 8–8 na de extra tijd, en dus volgen er penalties.

Bij de penalties wint het land dat alfabetisch het eerst komt. In het laatste voorbeeld wint Australia dus op penalties tegen Grenada.

Opgave

Schrijf een functie letterfrequenties waaraan een string $$s$$ (str) moet doorgegeven worden. De functie moet een dictionary teruggeven die alle letters die voorkomen in $$s$$ afbeeldt op hun aantal voorkomens. Bij het tellen van het aantal voorkomens mag geen onderscheid gemaakt worden tussen hoofdletters en kleine letters, en in de dictionary moeten de letters als hoofdletter voorgesteld worden. Indien $$s$$ karakters bevat die geen letter zijn, dan moeten die genegeerd worden.

Definieer daarnaast ook nog een klasse Knockout waarmee de knockoutfase van een landentoernooi kan gesimuleerd worden op basis van het scoresysteem uit de inleiding. Bij het aanmaken van een object van de klasse Knockout moet de locatie van een CSV-bestand¹ doorgegeven worden. Elke regel van dit bestand bevat zes velden met informatie over een land, die van elkaar gescheiden worden door komma's: i) naam van het land, ii) naam van de hoofdstad, iii) breedtegraad van de hoofdstad, iv) lengtegraad van de hoofdstad, v) landcode en vi) naam van het werelddeel. De klasse Knockout moet minstens de volgende methoden ondersteunen:

• Een methode hoofdstad waaraan de naam van een land (str) moet doorgegeven worden. De methode moet de naam van hoofdstad van het gegeven land teruggeven zoals die geschreven wordt in het gegeven CSV-bestand.
  

• Een methode reguliere_tijd waaraan twee landen (str) moeten doorgegeven worden. De methode moet de score (tuple) teruggeven na de reguliere speeltijd van een wedstrijd tussen de twee gegeven landen.

• Een methode extra_tijd waaraan twee landen (str) moeten doorgegeven worden. De methode moet de score (tuple) teruggeven na de extra speeltijd van een wedstrijd tussen de twee gegeven landen.

• Een methode wedstrijd waaraan twee landen (str) moeten doorgegeven worden. De methode moet de winnaar teruggeven in een wedstrijd tussen de twee gegeven landen.

• Een methode winnaar waaraan een lijst (list) of een tuple van $$2^n$$ ($$n \in \mathbb{N}$$) landen (str) moet doorgegeven worden. De methode moet de winnaar teruggeven in een toernooi met een knockoutsysteem waarin de gegeven landen tegen elkaar strijden.

  Opmerking

  Je mag ervan uitgaan dat er een lijst (list) of een tuple met $$2^n$$ ($$n \in \mathbb{N}$$) landen wordt doorgegeven aan de methode, zonder dat dit expliciet moet gecontroleerd worden.

De methoden mogen geen onderscheid maken tussen hoofdletters en kleine letters bij het verwerken van de landen die eraan doorgegeven worden, en ook niet bij het verwerken van hun hoofdsteden. Als er aan een methode een land wordt doorgegeven dat niet voorkomt in het gegeven CSV-bestand, dan moet een AssertionError opgeworpen worden met de boodschap onbekend land.

Voorbeeld

In onderstaand voorbeeldsessie gaan we ervan uit dat het CSV-bestand landen.csv² zich in de huidige directory bevindt.

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

>>> toernooi = Knockout('landen.csv3')
>>> toernooi.hoofdstad('Switzerland')
'Bern'
>>> toernooi.hoofdstad('Estonia')
'Tallinn'
>>> toernooi.reguliere_tijd('Switzerland', 'Estonia')
(5, 2)
>>> toernooi.reguliere_tijd('Belgium', 'Denmark')
(2, 2)
>>> toernooi.reguliere_tijd('Portugal', 'Austria')
(1, 2)
>>> toernooi.reguliere_tijd('Netherlands', 'Lithuania')
(3, 3)
>>> toernooi.extra_tijd('Belgium', 'Denmark')
(3, 2)
>>> toernooi.extra_tijd('Netherlands', 'Lithuania')
(4, 5)
>>> toernooi.wedstrijd('Switzerland', 'Estonia')
'Switzerland'
>>> toernooi.wedstrijd('Belgium', 'Denmark')
'Belgium'
>>> toernooi.wedstrijd('Portugal', 'Austria')
'Austria'
>>> toernooi.wedstrijd('Netherlands', 'Lithuania')
'Lithuania'
>>> toernooi.winnaar(['Switzerland', 'Estonia', 'Belgium', 'Denmark', 'Portugal', 'Austria', 'Netherlands', 'Lithuania'])
'Switzerland'