Een studentenraad telt negen leden. Om privacyredenen zullen we de studenten aanduiden met de letters A, B, …, I. Door een onderlinge vete spreken niet alle studenten met elkaar. Onderstaande tabel toont welke studenten met elkaar spreken — 1 betekent dat de twee studenten met elkaar spreken en 0 betekent dat de twee studenten niet met elkaar spreken.
A B C D E F G H I A - 0 0 1 0 0 1 0 0 B 0 - 1 1 1 1 1 1 1 C 0 1 - 0 0 0 1 1 0 D 1 1 0 - 1 0 1 0 1 E 0 1 0 1 - 0 1 0 0 F 0 1 0 0 0 - 0 0 1 G 1 1 1 1 1 0 - 0 0 H 0 1 1 0 0 0 0 - 0 I 0 1 0 1 0 1 0 0 -
Merk op dat wie met wie spreekt een symmetrische relatie is: als student $$x$$ spreekt met student $$y$$, dan spreekt student $$y$$ ook met student $$x$$. Daardoor is ook de tabel symmetrisch: de twee delen aan elke kant van de hoofddiagonaal zijn elkaars spiegelbeeld. We kennen dus de volledige relatie als we de waarden boven de hoofddiagonaal kennen (aangeduid in het blauw).
Onlangs stuurde student A een gerucht de wereld in, dat door elke andere student juist één keer werd opgevangen. Elke student ving het gerucht juist één keer op van een student waarmee hij sprak, en gaf het ook door aan juist één andere student waarmee hij sprak. Tellen we student A als nul, dan was student E de achtste en laatste student die het gerucht opving. Wie was de vierde student die het gerucht opving?
We weten dat A aan het begin van de ketting staat en E aan het einde. Van de anderen spreken F en H elk met slechts twee andere studenten. Dus moet F het gerucht doorgeven tussen B en I (in de ene of de andere richting, dus BFI of IFB), en moet H het gerucht doorgeven tussen B en C (dus BHC of CHB). Als we deze fragmenten samenvoegen, dan moeten we dus CHBFI of IFBHC hebben. We kunnen dit grotere fragment niet rechtstreeks verbinden met de eindpunten A of E, omdat noch C noch I met een van beide spreekt. Dat betekent dat de overige studenten, D en G, aan beide uiteinden van de grotere fragmenten moeten staan, voordat we de eindpunten kunnen bevestigen. Het verlengde fragment is dus GCHBFID of DIFBHCG, en met de eindpunten A en E toegevoegd krijgen we de volledige ketting AGCHBFIDE of ADIFBHCGE. In beide gevallen geldt dat als we A als nul tellen, de vierde student B is.
Voor een studentenraad met $$n$$ studenten ($$2 \leq n \leq 26$$) duiden we de studenten aan met de eerste $$n$$ hoofdletters (str) van het alfabet. Gevraagd wordt:
Schrijf een functie vul_tabel waaraan twee argumenten moeten doorgegeven worden: i) het aantal studenten $$n$$ (int) van een studentenraad en ii) een string (str) met $$\frac{n(n-1)}{2}$$ nullen (0) en enen (1) die boven de hoofddiagonaal staan in de tabel die aangeeft welke studenten met elkaar spreken (1) of niet (0), uitgelezen van links naar rechts en van boven naar onder. De functie moet de volledige tabel teruggeven, voorgesteld als een lijst (list) met de $$n$$ rijen (opgelijst van boven naar onder). Elke rij wordt zelf voorgesteld als een lijst (list) met de $$n$$ waarden op de rij, opgelijst van links naar rechts: True (bool) als de twee studenten met elkaar spreken, False (bool) als de twee studenten niet met elkaar spreken en None op de diagonaal. We noemen dit de spreektabel van de studentenraad.
Schrijf een functie print_tabel waaraan de spreektabel $$\mathcal{S}$$ van een studentenraad moet doorgegeven worden. De functie moet een voorstelling van spreektabel $$\mathcal{S}$$ uitschrijven volgens het formaat dat we ook in de inleiding gebruikt hebben. Dus met rijen en kolommen die gelabeld zijn met de hoofletters van de studenten (in alfabetische volgorde), een spatie tussen twee kolommen, en als waarde het cijfer 1 voor twee studenten die met elkaar spreken, het cijfer 0 voor twee studenten die niet met elkaar spreken en een koppelteken (-) op de diagonaal.
Schrijf een functie spreekt_met waaraan twee argumenten moeten doorgegeven worden: i) de hoofdletter $$s$$ van een student en ii) de spreektabel $$\mathcal{S}$$ van een studentenraad. De functie moet een verzameling (set) teruggeven met de hoofdletters van alle andere studenten waarmee student $$s$$ spreekt volgens spreektabel $$\mathcal{S}$$.
Schrijf een functie spreken_met_elkaar waaraan drie argumenten moeten doorgegeven worden: i) de hoofdletter $$s$$ van een student, ii) de hoofdletter $$t$$ van een andere student en iii) de spreektabel $$\mathcal{S}$$ van een studentenraad. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of studenten $$s$$ en $$t$$ met elkaar spreken volgens spreektabel $$\mathcal{S}$$.
Schrijf een functie is_ketting waaraan twee argumenten moeten doorgegeven worden: i) een string $$k$$ (str) met hoofdletters en ii) de spreektabel $$\mathcal{S}$$ van een studentenraad. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of $$k$$ een ketting vormt. Dat is het geval als
$$k$$ een permutatie is van de hoofdletters van de studenten uit de studentenraad (met andere woorden, $$k$$ bevat $$n$$ letters en de hoofdletter van elke student komt juist één keer voor)
elke twee opeenvolgende hoofdletters in $$k$$ corresponderen met studenten die met elkaar spreken volgens spreektabel $$\mathcal{S}$$
Een ketting geeft dus aan hoe een gerucht zou kunnen verspreid geraakt zijn onder alle studenten, die het bericht elk aan één andere student hebben doorgezegd waarmee ze spreken. Zo geeft de ketting AGCHBFIDE aan dat student A het gerucht de wereld heeft ingestuurd door het te zeggen aan student G, die het op zijn beurt heeft doorgezegd aan student C, enzoverder, tot het uiteindelijk door student D werd doorgezegd aan student E.
Schrijf een functie kettingen waaraan drie argumenten moeten doorgegeven worden: i) de hoofdletter $$s$$ van een student, ii) de hoofdletter $$t$$ van een andere student en iii) de spreektabel $$\mathcal{S}$$ van een studentenraad. De functie moet een verzameling (set) teruggeven van alle kettingen voor spreektabel $$\mathcal{S}$$ die starten met $$s$$ en eindigen met $$t$$.
Om alle kettingen te vinden, kan je alle mogelijke permutaties van
de hoofdletters overlopen die beginnen met de letter $$s$$ en
eindigen met de letter $$t$$, en voor elke permutatie controleren of
het wel degelijk een ketting is. De Python Standard Library1 bevat een module itertools2 met een functie permutations3 die je daarbij zal
kunnen gebruiken.
Je mag ervan uitgaan dat er enkel argumenten worden doorgegeven aan deze functies die voldoen aan de beschrijving uit de opgave, zonder dat dit expliciet moet gecontroleerd worden.
Deze interactieve sessie werkt met de spreektabel uit de inleiding van deze opgave.
>>> tabel = vul_tabel(9, '001001001111111000110101010100001000')
>>> tabel
[[None, False, False, True, False, False, True, False, False], [False, None, True, True, True, True, True, True, True], [False, True, None, False, False, False, True, True, False], [True, True, False, None, True, False, True, False, True], [False, True, False, True, None, False, True, False, False], [False, True, False, False, False, None, False, False, True], [True, True, True, True, True, False, None, False, False], [False, True, True, False, False, False, False, None, False], [False, True, False, True, False, True, False, False, None]]
>>> print_tabel(tabel)
A B C D E F G H I
A - 0 0 1 0 0 1 0 0
B 0 - 1 1 1 1 1 1 1
C 0 1 - 0 0 0 1 1 0
D 1 1 0 - 1 0 1 0 1
E 0 1 0 1 - 0 1 0 0
F 0 1 0 0 0 - 0 0 1
G 1 1 1 1 1 0 - 0 0
H 0 1 1 0 0 0 0 - 0
I 0 1 0 1 0 1 0 0 -
>>> spreekt_met('A', tabel)
{'D', 'G'}
>>> spreekt_met('B', tabel)
{'C', 'D', 'E', 'F', 'G', 'H', 'I'}
>>> spreken_met_elkaar('A', 'B', tabel)
False
>>> spreken_met_elkaar('G', 'A', tabel)
True
>>> is_ketting('AGCHBFIDE', tabel)
True
>>> is_ketting('ADIFBHCGE', tabel)
True
>>> kettingen('A', 'E', tabel)
{'ADIFBHCGE', 'AGCHBFIDE'}
>>> kettingen('H', 'F', tabel)
{'HCBEGADIF', 'HCGADEBIF'}
>>> kettingen('I', 'A', tabel)
{'IFBHCGEDA'}
>>> kettingen('B', 'D', tabel)
set()