De uitdaging:
Er bestaat een verrassend origineel algoritme om te beslissen of twee woorden anagrammen zijn van mekaar of niet, gebaseerd op priemgetallen. Aan elke letter van het alfabet wordt een uniek priemgetal toegekend, bijvoorbeeld A=2, B=3, C=5, D=7, E=11, …, Y=97 en Z=101. Van beide woorden worden nu de geassocieerde priemgetallen van elke letter met mekaar vermenigvuldigd. De twee woorden zijn anagrammen van mekaar als en slechts als beide vermenigvuldigingen hetzelfde product opleveren.

Bijvoorbeeld:
– DEKIMO = 7x11x31x23x41x47 = 105794227
– MEDIKO = 41x11x7x23x31x47 = 105794227
– MEDEME = 11³x41²x7 = 15661877

Dat dit algoritme altijd werkt is heel makkelijk te bewijzen. De ene richting (“anagrammen geven hetzelfde product”) is evident door de commutativiteit van de vermenigvuldiging. De andere richting (“als product hetzelfde is, dan zijn het anagrammen”) volgt uit de hoofdstelling van de rekenkunde dat elk natuurlijk getal een unieke ontbinding in priemfactoren heeft.

Echter, voor langere woorden loopt dit algoritme al snel in de problemen. De vermenigvuldigingen leiden tot grote getallen die niet meer in integer datatypes passen bij een software-implementatie. Je kan de problemen wat uitstellen door frequent voorkomende letters met de kleinere priemgetallen te associëren. Of je kan de logaritme nemen, waardoor de vermenigvuldigingen optellingen worden en de grote producten meer behapbare sommen worden. Geen van deze variaties leidt echter tot een echt efficiënte implementatie.

Het doel van deze wedstrijd is om beter te doen dan wat hierboven geschetst wordt, en om zelf een snel en schaalbaar algoritme te ontwerpen om te bepalen of twee lange letterreeksen anagrammen van mekaar zijn of niet. Dit algoritme moet geïmplementeerd worden op de Arduino die door Dekimo gratis ter beschikking gesteld wordt.