In 1795 stortte een meteoriet1 van 25 kilogram neer in Yorkshire (Engeland), een paar kilometer buiten het dorpje Wold Newton2. Ondanks het feit dat verschillende mensen vlak in de buurt stonden, raakte gelukkig niemand gewond. De meteoriet was nog steeds warm en aan het roken toen de eerste nieuwsgierige getuigen opdoken.

Wold Newton meteoriet
De meteoriet van Wold Newton is te bezichtigen in het Natural History Museum in Londen.

Dit voorval zette Philip José Farmer3 aan het denken. In zijn boek Tarzan Alive4 uit 1972 onthulde de sciencefictionschrijver dat zeven koppels en hun koetsiers langs het dorp waren gereden toen de meteoriet slechts twintig meter verderop insloeg.

De passagiers, koetsiers en paarden werden verblind en opgeschrikt door het heldere licht, de hitte en het donderende gebrul van de meteoriet. … Omdat ze geen benul hadden van ionisatie, konden ze niet vermoeden dat de gevallen ster hen en hun ongeboren kinderen had aangetast.

Onder de passagiers van de koetsen bevonden zich:

Onder de koetsiers bevonden zich:

De straling veroorzaakte een genetische mutatie in al deze personen, waardoor ze een extreem hoge intelligentie en kracht kregen. Ze brachten een stamboom van 92 personen voort wiens daden neergeschreven werden door Sir Arthur Conan Doyle29, Edgar Rice Burroughs30, Sax Rohmer31, Dorothy L. Sayers32, Jules Verne33 en anderen.

Wold Newton familie
De Wold Newton familie (1795-1901).

Farmer overleed in 2009, maar aan hem wordt het blootleggen toegeschreven van

De grondslag van deze nova aan genetische pracht, deze uitbarsting van grote detectives, wetenschappers en ontdekkingsreizigers van exotische werelden, deze laatste uitbarsting van ware helden in een tijdperk dat verder alleen maar ontaard bleek.

Het onderzoek naar de verbanden tussen deze opmerkelijke personen wordt verdergezet door een enthousiaste gemeenschap van onderzoekers34.

Opgave

De HBO reeks Game of Thrones35 is gebaseerd op de fantasy-reeks Het lied van vuur en ijs36 (A Song of Ice and Fire) van de Amerikaanse auteur George R.R. Martin37. Iedereen die de reeks gelezen of bekeken heeft, weet dat — hoewel de episodes over het algemeen uitstekend zijn — er veel personages in voorkomen. Een duizelingwekkend aantal zelfs, waardoor het moeilijk kan zijn om te volgen wie wie is, wie verwant is aan wie, en wie een incestueuze relatie had met welke broer of zus. Daar moeten de personen van de Wold Newton familie en hun onderlinge relaties niet veel voor onderdoen. Om het bos door de bomen te blijven zien, zorgen we er in deze opgave voor dat we in Python stambomen kunnen opstellen en bevragen. Hiervoor gaan we als volgt te werk.

Definieer een klasse Persoon waarmee personen kunnen voorgesteld worden. Bij het aanmaken van een persoon (Persoon) moeten drie eigenschappen van de persoon doorgegeven worden: i) een code (str), ii) een naam (str), en iii) een geslacht (str): M (man) of V (vrouw).

Als een persoon $$p$$ (Persoon) wordt doorgegeven aan de ingebouwde functie str, dan moet de naam van  $$p$$ (str) teruggegeven worden. Als een persoon $$p$$ (Persoon) wordt doorgegeven aan de ingebouwde functie repr dan moet een stringvoorstelling (str) teruggegeven worden die leest als een Python expressie waarmee een persoon (Persoon) aangemaakt wordt met dezelfde code, naam en geslacht als $$p$$.

Definieer ook nog een klasse Stamboom waarmee stambomen kunnen voorgesteld worden. Bij het aanmaken van een stamboom (Stamboom) moeten twee locaties (str) van tekstbestanden doorgegeven worden: i) een bestand met alle personen in de stamboom, en ii) een bestand met alle ouder-kind relaties van personen in de stamboom.

Elke regel van het eerste bestand beschrijft de eigenschappen van één persoon uit de stamboom en bestaat uit de code van de persoon, een gelijkteken (=), de naam van de persoon en het geslacht van de persoon (M of V) tussen ronde haakjes. De code en de naam van een persoon bevatten geen gelijktekens of ronde haakjes. Er komen ook geen komma's (,) of voorkomens van de combinatie -> voor in de code van een persoon. Bijkomende spaties vooraan en achteraan de code en de naam van een persoon maken geen deel uit van de code en de naam. Zo'n bestand ziet er dan bijvoorbeeld als volgt uit (personen.wnf.txt38):

1 = Mr. Karoly (M)
2 = 3rd Duke of Greystoke (M)
3 = Alicia Rutherford (V)
4 = Elizabeth Bennet (V)
5 = Fitzwilliam Darcy (M)
6 = Sir Percy Blakeney (M)
…

Alle personen uit het bestand hebben een unieke code. Merk op dat ondanks het feit dat de codes in bovenstaand voorbeeldbestand allemaal uit cijfers bestaan, een code ook letters (ABC) en leestekens (f?!k) mag bevatten.

Het tweede bestand bevat een reeks "$$A$$ is de ouder van $$B$$"-relaties tussen twee personen $$A$$ en $$B$$ in de stamboom. Een dergelijke relatie wordt beschreven als de code van $$A$$, de combinatie -> en de code van $$B$$. Bijkomende spaties tussen de codes en de combinatie -> maken geen deel uit van de codes. Opeenvolgende relaties worden van elkaar gescheiden door een komma (,). Bijkomende witruimte (spaties, tabs, newlines, …) tussen de relaties en de komma's moet genegeerd worden. Zo'n bestand ziet er dan bijvoorbeeld als volgt uit (relaties.wnf.txt39):

1 -> 19, 2 -> 20, 3 -> 20, 6 -> 21, 7 -> 21, 1 -> 22, 1 -> 23, 4 -> 24, 5 -> 24,
6 -> 25, 7 -> 25, 6 -> 27, 7 -> 27, 8 -> 28, 9 -> 28, 8 -> 29, 9 -> 29, 6 -> 30,
7 -> 30, 10 -> 32, 11 -> 32, 12 -> 33, 13 -> 33, 14 -> 35, 15 -> 35, 6 -> 36,
…
59 -> 79, 54 -> 80, 55 -> 80, 59 -> 81, 60 -> 81, 62 -> 82, 63 -> 82, 65 -> 83,
66 -> 83, 67 -> 84, 68 -> 85, 75 -> 85, 72 -> 86, 73 -> 87, 74 -> 88, 74 -> 89,
77 -> 90, 78 -> 90, 79 -> 91, 80 -> 92, 81 -> 92

Van elke persoon uit de stamboom worden 0, 1 of 2 ouders geïdentificeerd in het bestand, nooit meer. Als een persoon twee ouders heeft, dan zijn die bovendien van een verschillend geslacht. Stambomen (Stamboom) moeten minstens de volgende methoden ondersteunen:

Als een methode wordt aangeroepen op een persoon $$p$$ (Persoon) en een verzameling (set) van personen (Persoon) teruggeeft, zorg er dan voor dat die verzameling de persoon $$p$$ zelf niet bevat. Dat zou wel eens kunnen bij incestueuze relaties.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden personen.wnf.txt40 en relaties.wnf.txt41 zich in de huidige directory bevinden.

>>> wnf = Stamboom('personen.wnf.txt42', 'relaties.wnf.txt43')
>>> sherlock = wnf.persoon('73')
>>> sherlock
Persoon('73', 'Sherlock Holmes', 'M')
>>> print(sherlock)
Sherlock Holmes
>>> wnf.ouders(sherlock)
{Persoon('52', 'Siger Holmes', 'M'), Persoon('51', 'Violet Rutherford', 'V')}
>>> wnf.vader(sherlock)
Persoon('52', 'Siger Holmes', 'M')
>>> violet = wnf.moeder(sherlock)
>>> violet
Persoon('51', 'Violet Rutherford', 'V')
>>> wnf.kinderen(violet)
{Persoon('73', 'Sherlock Holmes', 'M'), Persoon('72', 'Sigrina Holmes', 'V')}
>>> wnf.zonen(violet)
{Persoon('73', 'Sherlock Holmes', 'M')}
>>> wnf.dochters(violet)
{Persoon('72', 'Sigrina Holmes', 'V')}
>>> wnf.broers(violet)
{Persoon('49', 'George T-', 'M'), Persoon('47', 'John Rutherford', 'M'), Persoon('46', '13th Baron Tennington', 'M')}
>>> wnf.zussen(violet)
{Persoon('54', 'Lucasta Rutherford', 'V'), Persoon('48', 'Venetia Rutherford', 'V')}
>>> wnf.nonkels(violet)
{Persoon('29', 'Scott Rutherford', 'M'), Persoon('25', 'Percy Armand Blakeney', 'M')}
>>> wnf.tantes(violet)
{Persoon('36', 'Marguerite Blakeney', 'V'), Persoon('21', 'Mavice Blakeney', 'V'), Persoon('30', 'Suzanne Blakeney', 'V')}
>>> wnf.voorouders(violet)
{Persoon('27', 'Serena Blakeney', 'V'), Persoon('8', '11th Baron Tennington', 'M'), Persoon('28', '12th Baron Tennington', 'M'), Persoon('7', 'Alice Clarke Raffles', 'V'), Persoon('6', 'Sir Percy Blakeney', 'M'), Persoon('9', 'Elizabeth Cavendish', 'V')}
>>> wnf.nakomelingen(violet)
{Persoon('86', 'Denis Nayland Smith', 'M'), Persoon('87', 'Nero Wolfe', 'M'), Persoon('73', 'Sherlock Holmes', 'M'), Persoon('72', 'Sigrina Holmes', 'V')}