Le défi :
Il existe un algorithme étonnamment original pour décider si deux mots sont des anagrammes l’un de l’autre ou non, basé sur des nombres premiers. Chaque lettre de l’alphabet est associée à un nombre premier unique, par exemple A=2, B=3, C=5, D=7, E=11, …, Y=97 et Z=101. A partir des deux mots, les nombres premiers associés à chaque lettre sont multipliés entre eux. Les deux mots sont des anagrammes l’un de l’autre si et seulement si les deux multiplications donnent le même produit.

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

Il est très facile de prouver que cet algorithme fonctionne toujours. Une direction (“les anagrammes donnent le même produit”) est évidente en raison de la commutativité de la multiplication. L’autre sens (“si le produit est le même, alors ce sont des anagrammes”) découle du théorème principal de l’arithmétique selon lequel chaque nombre naturel a une décomposition unique en facteurs premiers.

Cependant, pour les mots plus longs, cet algorithme rencontre rapidement des problèmes. Les multiplications conduisent à de grands nombres qui ne correspondent plus aux types de données entiers dans une implémentation logicielle. Vous pouvez retarder un peu les problèmes en associant les lettres fréquentes aux petits nombres premiers. Vous pouvez aussi utiliser le logarithme, qui transforme les multiplications en additions et les grands produits en sommes plus faciles à gérer. Cependant, aucune de ces variations ne conduit à une mise en œuvre réellement efficace.

Le but de ce concours est de faire mieux que ce qui est décrit ci-dessus, et de concevoir un algorithme rapide et évolutif pour déterminer si deux longues chaînes de lettres sont des anagrammes l’une de l’autre ou non. Cet algorithme doit être implémenté sur l’Arduino qui est fourni gratuitement par Dekimo.