Die Herausforderung:
Es gibt einen erstaunlich originellen Algorithmus, um zu entscheiden, ob zwei Wörter Anagramme voneinander sind oder nicht, basierend auf Primzahlen. Jedem Buchstaben des Alphabets ist eine eindeutige Primzahl zugeordnet, zum Beispiel A=2, B=3, C=5, D=7, E=11, …, Y=97 und Z=101. Von beiden Wörtern werden die zugehörigen Primzahlen der einzelnen Buchstaben miteinander multipliziert. Die beiden Wörter sind dann und nur dann Anagramme voneinander, wenn beide Multiplikationen das gleiche Produkt ergeben.

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

Dass dieser Algorithmus immer funktioniert, ist sehr einfach zu beweisen. Eine Richtung (“Anagramme ergeben das gleiche Produkt”) ist aufgrund der Kommutativität der Multiplikation offensichtlich. Die andere Richtung (“wenn das Produkt gleich ist, dann sind sie Anagramme”) folgt aus dem Hauptsatz der Arithmetik, dass jede natürliche Zahl eine eindeutige Zerlegung in Primfaktoren hat.

Bei längeren Wörtern stößt dieser Algorithmus jedoch schnell auf Probleme. Die Multiplikationen führen zu großen Zahlen, die in einer Softwareimplementierung nicht mehr in Integer-Datentypen passen. Sie können die Probleme ein wenig hinauszögern, indem Sie häufige Buchstaben mit den kleineren Primzahlen verbinden. Oder Sie nehmen den Logarithmus, der Multiplikationen in Additionen und große Produkte in handlichere Summen verwandelt. Allerdings führt keine dieser Varianten zu einer wirklich effizienten Implementierung.

Das Ziel dieses Wettbewerbs ist es, besser zu sein als das, was oben skizziert wurde, und einen schnellen und skalierbaren Algorithmus zu entwerfen, der bestimmt, ob zwei lange Buchstabenketten Anagramme voneinander sind oder nicht. Dieser Algorithmus sollte auf dem Arduino implementiert werden, der von Dekimo kostenlos zur Verfügung gestellt wird.