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.
Definieer een klasse Raad waarmee studentenraden kunnen voorgesteld worden met studenten die onderling wel of niet met elkaar spreken. Bij het aanmaken van een nieuwe studentenraad (Raad) moeten twee argumenten doorgegeven worden: i) het aantal studenten $$n$$ (Number; $$2 \leq n \leq 26$$) in de raad en ii) een string (String) met $$\frac{(n-1)n}{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 studenten van de raad worden aangeduid met de eerste $$n$$ hoofdletters (String) van het alfabet, overeenkomstig de rijen en de kolommen van tabel.
Op een studentenraad $$R$$ (Raad) moet je minstens de volgende methoden kunnen aanroepen:
Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een stringvoorstelling (String) van raad $$R$$ teruggeven, in het formaat dat we ook in de inleiding gebruikt hebben. Dus met rijen en kolommen die gelabeld zijn met de hoofdletters 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.
Een methode spreektMet waaraan de hoofdletter $$s$$ (String) van een student in raad $$R$$ moet doorgegeven worden. De methode moet een verzameling (Set) teruggeven met de hoofdletters (String) van alle andere studenten in raad $$R$$ waarmee student $$s$$ spreekt.
Een methode sprekenMetElkaar waaraan de hoofdletters $$s$$ (String) en $$t$$ (String) van twee studenten in raad $$R$$ moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of studenten $$s$$ en $$t$$ met elkaar spreken.
Een methode isKetting waaraan een string $$k$$ (String) met hoofdletters moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of $$k$$ een ketting vormt. Dat is het geval als
$$k$$ een permutatie is van de hoofdletters van alle studenten in raad $$R$$ (met andere woorden, $$k$$ bevat $$n$$ hoofdletters en de hoofdletter van elke student komt juist één keer voor)
elke twee opeenvolgende hoofdletters in $$k$$ corresponderen met studenten die met elkaar spreken
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.
Een methode kettingen waaraan de hoofdletters $$s$$ (String) en $$t$$ (String) van twee studenten in raad $$R$$ moeten doorgegeven worden. De methode moet een verzameling (Set) teruggeven met alle kettingen (String) voor raad $$R$$ die starten bij student $$s$$ en eindigen bij student $$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. Je mag zelf een implementatie maken
die alle permutaties genereert, maar je mag die ook online zoeken.
In dat laatste geval ben je zelf verantwoordelijk om de kwaliteit
van het algoritme en de implementatie te beoordelen, en vergeet ook
niet om (in commentaar) aan te geven waar je je implementatie
gehaald hebt.
Je mag ervan uitgaan dat er aan deze methoden enkel argumenten doorgegeven worden die voldoen aan de beschrijving uit de opgave, zonder dat dit expliciet moet gecontroleerd worden.
Deze interactieve sessie werkt met de tabel uit de inleiding van deze opgave.
> const raad = new Raad(9, "001001001111111000110101010100001000")
> console.log(raad.toString())
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 -
> raad.spreektMet("A")
Set(["D", "G"])
> raad.spreektMet("B")
Set(["C", "D", "E", "F", "G", "H", "I"])
> raad.sprekenMetElkaar("A", "B")
false
> raad.sprekenMetElkaar("G", "A")
true
> raad.isKetting("AGCHBFIDE")
true
> raad.isKetting("ADIFBHCGE")
true
> raad.kettingen("A", "E")
Set(["ADIFBHCGE", "AGCHBFIDE"])
> raad.kettingen("H", "F")
Set(["HCBEGADIF", "HCGADEBIF"])
> raad.kettingen("I", "A")
Set(["IFBHCGEDA"])
> raad.kettingen("B", "D")
Set()