Je landt op een luchthaven die omgeven is door dichte bossen. Terwijl je naar de hogesnelheidstrein wandelt, nemen de Elfen van het Mythical Information Bureau weer contact met je op. Ze denken dat hun satelliet een waarneming van een zeemonster gedaan heeft! Helaas is er een slechte verbinding met de satelliet, waardoor veel berichten die de satelliet uitgestuurde beschadigd geraakt zijn.

Ze hebben je een lijst doorgestuurd van de regels waaraan geldige berichten moeten voldoen en een lijst van de ontvangen berichten die ze tot nu toe verzameld hebben (de invoer van deze opgave).

De regels voor geldige berichten (bovenste deel van de invoer) zijn genummerd en bouwen op elkaar voort. Bijvoorbeeld:

0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b"

Sommige regels, zoals 3: "b", komen gewoon overeen met één enkel teken (in dit geval b).

De overige regels vermelden de deelregels die moeten gevolgd worden. De regel 0: 1 2 betekent bijvoorbeeld dat om regel 0 te matchen, de te controleren tekst moet matchen met regel 1, en dat de tekst na het deel matcht met regel 1 moet matchen met regel 2.

Sommige regels hebben meerdere lijsten met deelregels, gescheiden door een verticale streep (|). Dit betekent dat er minimaal één lijst met deelregels moet matchen. (Het element van de lijst dat matcht kan elke keer dat de regel gebruikt wordt anders zijn.) Bijvoorbeeld, de regel 2: 1 3 | 3 1 betekent dat om regel 2 te matchen, de te controleren tekst moet matchen met regel 1 gevolgd door 3 of dat de tekst moet matchen met regel 3 gevolgd door 1.

Gelukkig zitten er geen lussen in de regels, waardoor de lijst met mogelijke matches eindig is. Aangezien regel 1 matcht met a en regel 3 matcht met b, matcht regel 2 ofwel met ab of met ba. Daarom matcht regel 0 met aab of aba.

Dit is een interessanter voorbeeld:

0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

Omdat regel 4 hier matcht met a en regel 5 met b, matcht regel 2 met twee letters die hetzelfde zijn (aa of bb) en regel 3 met twee letters die verschillend zijn (ab of ba).

Omdat regel 1 één keer matcht met regels 2 en 3 in elke mogelijke volgorde, moet het matchen met twee paar letters, waarvan één paar letters die hetzelfde zijn en één paar die verschillend zijn. Dit geeft acht mogelijkheden: aaab, aaba, bbab, bbba, abaa, abbb, baaa of babb.

Regel 0 matcht daarom met a (regel 4), dan met één van de acht mogelijkheden uit regel 1, en dan met b (regel 5): aaaabb, aaabab, abbabb, abbbab, aabaab, aabbbb, abaaab of ababbb.

De ontvangen berichten (het onderste deel van de invoer) moeten gecontroleerd worden met de regels, zodat je kunt bepalen welke berichten geldig en welke er beschadigd zijn. De regels en de berichten kunnen er dan samen bijvoorbeeld als volgt uit zien:

0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

ababbb
bababa
abbbab
aaabbb
aaaabbb

Jouw doel is om te bepalen hoeveel berichten er volledig matchen met regel 0. In het bovenstaand voorbeeld matchen ababbb en abbbab wel, maar bababa, aaabbben aaaabbb niet. In dit geval is het antwoord dus 2. Het volledige bericht moet overeenkomen met alles in regel 0. Er mogen geen extra tekens in het bericht staan die niet matchen. (Zo kan het bijvoorbeeld lijken dat aaaabbb matcht met regel 0 van hierboven, maar er staat een extra b op het einde die niet matcht.)

Opgave

Hoeveel berichten matchen er volledig met regel 0? Hiervoor ga je als volgt te werk:

• Schrijf een functie match waaraan twee argumenten moeten doorgegeven worden: i) een bericht (str) en ii) de padnaam (str) van een tekstbestand met de regels waaraan geldige berichten moeten voldoen. De functie moet een Booleaanse waarde (bool) teruggeven die aangeeft of het bericht volledig matcht met regel 0.
• Schrijf een functie matches waaraan twee argumenten moeten doorgegeven worden: i) de padnaam (str) van een tekstbestand met een lijst van de ontvangen berichten die tot nu toe verzameld werden en ii) de padnaam (str) van een tekstbestand met de regels waaraan geldige berichten moeten voldoen. De functie moet teruggeven hoeveel (int) berichten er volledig matchen met regel 0.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden messages.txt¹ en rules.txt² zich in de huidige directory bevinden.

>>> match('ababbb', 'rules.txt')
True
>>> match('abbbab', 'rules.txt')
True
>>> match('bababa', 'rules.txt')
False
>>> match('aaabbb', 'rules.txt')
False
>>> match('aaaabbb', 'rules.txt')
False

>>> matches('messages.txt', 'rules.txt')
2