Current Dekimo Embedded Challenge recordholder

Antoine Poussart= 1250ns

Current Dekimo Embedded Challenge recordholder

Dekimo Embedded Challenge

In this third edition of the Dekimo Embedded Contest, the task is again to create your own implementation on an Arduino board. However, this time the challenge is not about anagrams or about optimising an algorithm. We have chosen a task with “factorials”, the task is to solve a seemingly impossible problem.

Goal

The goal of this competition is to create a clever and fast algorithm that achieves the set result. The algorithm must be implemented on an Arduino Nano Every, which will be provided free of charge by Dekimo after registration. You can also keep the Arduino after the competition.

The winner is the one who has a correctly working algorithm and that is the fastest on different test vectors chosen by Dekimo. The record scoreboard will be kept on this page. Every time someone beats the existing record, that person will receive a nice prize and, if approved, their name will be listed as the new record holder on our website.

Currently there is no deadline for registration or for uploading results.

Description of task

The technical details of the assignment are further explained in the document that will be received after registration.

The operation “factorial” in mathematics probably does not need an introduction. The factorial of a number n is denoted by n! and is the product of all integers from 1 to n (incuding n). Thus, 5! = 1x2x3x4x5 = 120. In combinatorics, this is the number of permutations of 5 elements, or thus the number of possible anagrams of words of 5 letters. In a basic programming course, the factorial is often used to introduce recursion, since n! = n . (n-1)!. Too little is said about the fact that this kind of tail recursion is unnecessarily greedy and inefficient and is better replaced by an iterative loop, but that’s beside the point.

Anyone who has ever calculated factorials knows that the results become very large very quickly. The factorial grows faster than the exponential function. In a manual calculation, the fun stops after the first ten factorials. Microsoft Excel already gives up at 21! because the result no longer fits in a 64-bit data type. Many calculators give up at 70!, a number that is more than one hundred digits long. The built-in Google calculator stops at 171!, a number of over three hundred digits that no longer fits in a 1024-bit datatype.

We are going to start with the Arduino where Google gives up and where Microsoft has long disappeared from the rear view mirror. We are not going to calculate large factorials, as this would be boring and uninspiring. We are going to keep it fun. The Arduino will receive a number string that is already a factorial. In that number string, two consecutive digits will be masked. These digits will have been replaced by ‘xy’. An algorithm needs to be implemented on the Arduino that will calculate the two missing digits x and y.

Let’s take something small and manageable as an example, the factorial of 21, 21!= 51090942171709440000. The Arduino receives as input 510909xy171709440000 and must deduce that this can only be a factorial if xy=42. Clearly, for large numbers such as 999! the method that first calculates the factorial in full is not the ideal solution, or even impossible with the limited resources on the embedded microcontroller.

At first glance, this task may seem impossible. After all, there is no fixed pattern in the numbers of factorials. Yet, with some ingenuity, it is possible to find connections between x and y that allow the solution to be determined unambiguously, without actually having to calculate the factorial.

Dekimo will release hints periodically. This way those who find the solution themselves receive a head start. But even those who cannot find the solution without a hint can still get to the desired solution.

This competition is only for residents of Belgium and the Netherlands. Questions? Do not hesitate to contact us at the email address: studentchallenge at dekimo.com

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 to send the parcel. Your data will not be used for other purposes.

 

 

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

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

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.

Do you need some hints?

Dekimo will release hints periodically. This way those who find the solution themselves receive a head start. But even those who cannot find the solution without a hint can still get to the desired solution.

Scoreboard Embedded Challenge record holders

Name Time
Antoine Poussart 1250 ns
Arthur Deleu 1748 ns
Kobe Vanfrachem 1812 ns
Jens Timmerman 3938 ns
Sven Van Laere 178437 ns
Menno Vanfrachem 726125 ns
Dekimo medewerker 3080750 ns

This website uses cookies to ensure you get the best experience on our website.