Cedric Den Haese = 7000 ns
Current Student Challenge 2021 recordholder
Cedric Den Haese = 7000 ns
The Student Challenge 2021 is a competition organised by Dekimo to program on an embedded platform. The challenge is to create your own implementation on an Arduino board that quickly recognizes whether 2 different character strings are anagrams or not. The character strings are transmitted via USB. The fastest record of the execution time is kept and must be surpassed. Your entry will be checked and approved by an expert jury. Whoever breaks the existing record wins a prize. The Arduino board will be provided by Dekimo free of charge, and you can also keep it afterwards.
There is a surprisingly original algorithm for deciding whether two words are anagrams of each other or not, based on prime numbers. Each letter of the alphabet is assigned to a unique prime number, for example A=2, B=3, C=5, D=7, E=11, …, Y=97 and Z=101. The associated prime numbers of each letter are multiplied by each other, from both words. If and only if both multiplications yield the same result, the words are anagrams.
– DEKIMO = 7x11x31x23x41x47 = 105794227
– MEDIKO = 41x11x7x23x31x47 = 105794227
– MEDEME = 11³x41²x7 = 15661877
It is very easy to prove that this algorithm always works. One direction (“anagrams give the same product”) is obvious because of the commutativity of multiplication. The other direction (“if result is equal means they are anagrams”) follows from the fundamental theorem of arithmetic that every natural number has a unique decomposition into prime factors.
However, for longer words, this algorithm quickly runs into problems. The multiplications lead to large numbers that don’t fit into integer data types in a software implementation. You can delay the problems by associating frequent letters with the smaller prime numbers. Or you can take the logarithm, which turns multiplications into additions and large products into more manageable sums. However, none of these variations leads to a really efficient implementation.
The goal of this contest is to do better than the above, and to design a fast and scalable algorithm to determine whether two long strings of letters are anagrams of each other or not. This algorithm should be implemented on the Arduino that is provided for free by Dekimo.
This competition is exclusively for students from Belgium, the Netherlands and the Aachen region.
Any questions? Do not hesitate to contact us via the e-mail address: studentchallenge at dekimo.com
Whoever breaks the record, for at least 6 hours, may choose from one of the prizes below:
You can participate by filling in the form below.
To participate, it is necessary to fill in the form. We need the address and phone number to send the parcel. Your data will not be used for other purposes.
We expect a .ino file or a .zip as source code for Arduino firmware.
Note: We accept only one entry per participant.
|Cedric Den Haese||7000 nanoseconds|
|Matis De Schutter||16312 nanoseconds|
|Maarten C. (Dekimo employee)||18125 nanoseconds|