We hebben de twee partners van een bekend duo vermomd door hun namen van elkaar af te trekken. Als het verschil van David en Goliath gelijk is aan -C -N J * C -T -H, welke duo's zijn dit dan?

1. A -T I B F

2. -P -N R D -M N

3. D * C N -T L

4. -J Q -O G E -C -H -Y

5. -A C -K J D E

Opgave

We geven elke letter (str; hoofdletters en kleine letters) een waarde (int) die overeenkomt met zijn positie in het alfabet (A=1, B=2, C=3, …, Z=26). De asterisk (*) beschouwen we als een extra letter met waarde nul (0).

Het verschil van twee letters is een string (str) die bepaald wordt door eerst de waarden van die twee letters van elkaar af te trekken. Dit levert een waarde tussen -26 en 26 op, die we voorstellen als:

• positieve waarden (1…26): de letter op de overeenkomstige positie in het alfabet (1=A, 2=B, 3=C, ... 26=Z)

• waarde nul (0): een asterisk (*)

• negatieve waarden (-26…-1): een koppelteken (-) gevolgd door de letter die de absolute waarde voorstelt

Een woord is een string (str) die bestaat uit één of meer letters (hoofdletters of kleine letters; geen asterisks). Om het verschil van twee woorden te bepalen, vullen we eerst het kortste woord achteraan aan met asterisken (*) tot beide woorden even lang zijn. Het verschil is dan een tuple (tuple) met de verschillen van de twee letters op overeenkomstige posities in de twee woorden. De lengte van dit tuple is dus gelijk aan de lengte van het langste woord.

Gevraagd wordt:

• Schrijf een functie verschil2waarde waaraan het verschil van twee letters (str) moet doorgegeven worden (dus een asterisk of een letter die eventueel voorafgegaan wordt door een koppelteken). De functie moet de corresponderende waarde (int) teruggeven. Daarbij mag de functie geen onderscheid maken tussen hoofdletters en kleine letters.

• Schrijf een functie waarde2verschil waaraan een waarde (int) tussen -26 en 26 moet doorgegeven worden. De functie moet de voorstelling van die waarde teruggeven als het verschil van twee letters (str; in hoofdletters).

• Schrijf een functie vermomming waaraan twee woorden $$w_1$$ en $$w_2$$ (str) moeten doorgegeven worden. De functie moet het verschil van $$w_1$$ en $$w_2$$ teruggeven (in hoofdletters).

• Schrijf een functie partner waaraan twee argumenten moeten doorgegeven worden: i) een woord $$w_1$$ (str) en ii) het verschil $$v$$ van twee woorden. De functie moet het woord $$w_2$$ (str; in hoofdletters) teruggeven waarvoor $$v$$ het verschil is van $$w_1$$ en $$w_2$$ (cfr. functie vermomming). Als zo'n woord niet bestaat, dan moet de waarde None teruggegeven worden. Hou daarbij volgende zaken in het achterhoofd:

  • bij het bepalen van het verschil van twee woorden wordt mogelijks één van de woorden achteraan aangevuld met asterisks; die asterisks maken geen deel uit van dat woord

  • woorden bestaan enkel uit hoofdletters en kleine letters; strings waarin karakters voorkomen die geen letter zijn (ook asterisks mogen niet) zijn geen geldige woorden

  • minstens één van de woorden $$w_1$$ en $$w_2$$ moeten even lang zijn als het verschil; het andere woord mag korter zijn

• Schrijf een functie opsporen waaraan twee argumenten moeten doorgegeven worden: i) het verschil van twee woorden en ii) de locatie (str) van een tekstbestand met een collectie woorden (één woord per regel; in hoofdletters). De functie moet een verzameling (set) teruggeven met alle paren woorden uit de collectie wiens verschil gelijk is aan het gegeven verschil. Daarbij wordt een paar woorden voorgesteld als een tuple (tuple) met de twee woorden.

  Tip

  Het zal te lang duren als je het verschil bepaalt van elk paar woorden uit de collectie om te kijken of dat verschil gelijk is aan het gegeven verschil. Je krijgt een sneller algoritme als je voor elk woord uit de collectie de partner bepaalt die hoort bij het gegeven verschil, en dan nagaat of die partner ook in de collectie voorkomt (daarvoor gebruik je als collectie best een verzameling (set) om snel te kunnen opzoeken). Je kunt ook gebruikmaken van het feit dat de lengte van het verschil gelijk is aan de lengte van het langste van de twee woorden die afgetrokken worden.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand woorden.txt¹ zich in de huidige directory bevindt.

>>> verschil2waarde('*')
0
>>> verschil2waarde('A')
1
>>> verschil2waarde('-t')
-20

>>> waarde2verschil(0)
'*'
>>> waarde2verschil(1)
'A'
>>> waarde2verschil(-20)
'-T'

>>> vermomming('Mario', 'Luigi')
('A', '-T', 'I', 'B', 'F')
>>> vermomming('Batman', 'Robin')
('-P', '-N', 'R', 'D', '-M', 'N')
>>> vermomming('David', 'Goliath')
('-C', '-N', 'J', '*', 'C', '-T', '-H')

>>> partner('Mario', ('A', '-T', 'I', 'B', 'F'))
'LUIGI'
>>> partner('Batman', ('-P', '-N', 'R', 'D', '-M', 'N'))
'ROBIN'
>>> partner('David', ('-C', '-N', 'J', '*', 'C', '-T', '-H'))
'GOLIATH'

>>> opsporen(('A', '-T', 'I', 'B', 'F'), 'woorden.txt2')
{('MARIO', 'LUIGI')}
>>> opsporen(('-P', '-N', 'R', 'D', '-M', 'N'), 'woorden.txt3')
{('BATMAN', 'ROBIN')}
>>> opsporen(('-C', '-N', 'J', '*', 'C', '-T', '-H'), 'woorden.txt4')
{('DAVID', 'GOLIATH')}
>>> opsporen(('A', '-Q', 'I', '-A', '*', '*'), 'woorden.txt5')
{('BARREN', 'ARISEN'), ('CARSON', 'BRITON'), ('HANSEL', 'GRETEL')}

Epiloog

De titel van deze opgave verwijst naar de film Hidden Figures⁶ (2016) die het waargebeurde verhaal vertelt van de wetenschapsters Katherine Johnson⁷ en haar twee collega's Dorothy Vaughan⁸ en Mary Jackson⁹. Deze drie vrouwen werkten in de West Area Computing Unit van het NASA Langley Research Center¹⁰ — een team dat uitsluitend uit vrouwelijke Afro-Amerikaanse wetenschappers bestond en dat een belangrijk aandeel had in de ruimtewedloop. Dankzij hun berekeningen slaagde de Amerikaanse ruimtevaarder John Glenn¹¹ er in 1962 in om als eerste Amerikaan in een baan om de aarde te vliegen.