Een anagram is een woord dat of een zin die bestaat uit alle letters van een ander woord of een andere zin. Anagrammen worden vaak gebruikt als pseudoniem (Leonardo da Vinci: o draconian devil; The Mona Lisa: oh lame saint).
Een eenvoudige manier om te bepalen of woorden anagrammen zijn, bestaat erin om een hashwaarde te berekenen waarvoor geldt dat enkel anagrammen identieke hashwaarden hebben. Voor de berekening van een hashwaarde kan je bijvoorbeeld aan elke letter van het alfabet een priemgetal toekennen (a=2, b=3, …, z=101), en de waarden die corresponderen met elke letter van het originele woord met elkaar vermenigvuldigen. Communtativiteit van de vermenigvuldiging en uniciteit van de ontbinding in priemfactoren garanderen dat anagrammen een unieke hashwaarde hebben. Bij de berekening van de hashwaarde moeten enkel de letters uit het alfabet in rekening gebracht worden (geen leestekens, cijfers, etc.), en moeten deze niet-hoofdlettergevoelig behandeld worden. Zo resulteren de woorden callers, cellars en RECALLS allemaal in de hashwaarde 615461330, waardoor het dus anagrammen zijn.
Hint: In de context van deze opgave moet je zeker ook eens de Monty Python sketch "The man who speaks in anagrams1" bekijken. Daar valt nauwelijks iets van te begrijpen, tenzij je er de uitgeschreven tekst2 bijneemt.
Schrijf een functie nPriem, waaraan optioneel een argument $$n$$ kan meegegeven worden. De functie moet een lijst met de eerste $$n$$ priemgetallen teruggeven. Indien geen argument aan de functie wordt meegegeven, moet een lijst met de eerste 10 priemgetallen teruggegeven worden.
nPriem([n])
Schrijf een functie anagramHash waaraan exact twee argumenten moeten meegegeven worden. Het eerste argument is een zin waarvan de hashwaarde door de functie moet teruggegeven worden. Het tweede getal is een lijst van 26 (of meer) getallen die moeten gebruikt worden om de hashwaarde te berekenen: de letter a correspondeert met het eerste getal uit de lijst, de letter b met het tweede getal, enzoverder. De hashwaarde wordt berekend als het product van alle getallen die corresponderen met de letters uit de zin. Bij de berekening van de hashwaarde moeten enkel de letters uit het alfabet in rekening gebracht worden (geen leestekens, cijfers, etc.), en moeten deze niet-hoofdlettergevoelig behandeld worden.
anagramHash(zin, getallenlijst)
Gebruik de functies nPriem
en anagramHash om een
functie zijnAnagrammen te
schrijven. Aan deze
functie moeten twee zinnen doorgegeven worden, waarvan de functie moet
bepalen of het anagrammen zijn (waarde True
teruggegeven) of niet (waarde False
teruggegeven). Om de vaststelling te maken of het anagrammen zijn, moet
de functie de hashwaarde van de twee zinnen berekenen. Standaard wordt
deze hashwaarde bepaald aan de hand van een mapping naar de lijst van de
eerste 26 priemgetallen. Indien er echter een lijst van getallen als
derde argument aan de functie doorgegeven wordt, dan worden deze
getallen gebruikt om de hashwaarde van de zinnen te berekenen.
zijnAnagrammen(zin1, zin2[, getallenlijst])
>>> nPriem()
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
>>> nPriem(5)
[2, 3, 5, 7, 11]
>>> nPriem(8)
[2, 3, 5, 7, 11, 13, 17, 19]
>>> anagramHash('Leonardo Da Vinci', nPriem(26))
4153036139030192260
>>> anagramHash('Leonardo Da Vinci', range(1, 27))
4073908608000
>>> anagramHash('Leonardo Da Vinci', nPriem(52)[-26:])
280080025163413341541861091223919
>>> anagramHash('O Draconian Devil', nPriem(26))
4153036139030192260
>>> zijnAnagrammen('Leonardo Da Vinci', 'O Draconian Devil')
True
>>> zijnAnagrammen('The Mona Lisa', 'Oh Lame Saint')
True
>>> zijnAnagrammen('The Mona Lisa', 'Oh Lame Saint', range(1, 27))
True
>>> zijnAnagrammen('The Mona Lisa', 'Oh Lame Saint', nPriem(52)[-26:])
True