Current Student Challenge 2021 recordholder

Laurens Scheldeman = 1688 ns

What is the Dekimo Student Challenge 2021?

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.

The challenge:
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.

For example:
– 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
Deadline to upload your result: 05/09/21
Afterwards, we organize another competition, subscribe here to our mailing list to make sure you don’t miss anything.

Whoever breaks the record, for at least 6 hours, may choose from one of the prizes below:

  • Arduino Uno Rev3 starter kit
  • Extended Arduino Starter Kit R3
  • Bluetooth speaker JBL Flip 5
  • Headset HyperX Cloud II
  • Tello Drone (DJI)
  • Google Nest Hub 2
  • Google Chromecast 3 + Google Nest mini
  • Game of your choice for PC, PS, Xbox or Switch at Coolblue

 

Tip: According to legends, an execution time <1,000 ns is possible

Dekimo Student Challenge prizes

You can participate by filling in the form below.

 

Get your Arduino here with detailed instructions and join the challenge!

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.

 

Challenge completed? Upload your result here.

We expect a .ino file or a .zip as source code for Arduino firmware.
Note: We accept only one entry per participant.

Scoreboard Student Challenge record holders

Name Time
Laurens Scheldeman 1688 nanoseconds
Cedric Den Haese 7000 nanoseconds
Matis De Schutter 16312 nanoseconds
Maarten C. (Dekimo employee) 18125 nanoseconds