Huidige Dekimo Embedded Challenge recordhouder

Bram Demedts= 50 ns

Huidige Dekimo Embedded Challenge recordhouder

Bram Demedts= 50 ns

Dekimo Embedded Challenge

In deze derde editie van de Dekimo Embedded Challenge is het opnieuw de opdracht om een eigen implementatie op een Arduino bord te maken. Echter gaat de uitdaging deze keer niet over anagrammen of over het optimaliseren van een algoritme. We hebben deze keer gekozen voor een opdracht met “faculteiten”, de opgave is om een schijnbaar onmogelijk probleem op te lossen.

Opzet

Het doel van deze wedstrijd is om een slim en snel algoritme te maken dat het gestelde resultaat bereikt. Het algoritme moet geïmplementeerd worden op een Arduino Nano Every, die na inschrijving gratis ter beschikking gesteld wordt door Dekimo.

De winnaar is degene die een correct werkend algoritme heeft, dat het snelste is op verschillende testvectoren die gekozen worden door Dekimo. Het record zal hieronder bijgehouden worden. Telkens wanneer iemand het bestaande record verbreekt, ontvangt die persoon een leuke prijs en wordt, mits toestemming, de naam vermeld als nieuwe recordhouder op onze website.

Momenteel is er geen deadline voor inschrijving of het opladen van resultaten.

Opdrachtomschrijving

De technische details van de opdracht worden verder uitgelegd in de opdrachtbeschrijving die men ontvangt na inschrijving.

De bewerking “faculteit” uit de wiskunde heeft wellicht geen introductie nodig. De faculteit van een getal n wordt genoteerd als n! en is het product van alle natuurlijke getallen van 1 tot en met n. Zo is 5! = 1x2x3x4x5 = 120. In de combinatoriek is dit het aantal permutaties van 5 elementen, of dus het aantal mogelijke anagrammen van woorden van 5 letters. In een basiscursus programmeren wordt de faculteit vaak gebruikt bij het introduceren van recursie, vermits n! = n . (n-1)!. Te weinig wordt daar trouwens bij verteld dat dit soort staartrecursie nodeloos gulzig en inefficiënt is en beter vervangen wordt door een iteratieve lus, maar dit terzijde.

Wie ooit faculteiten berekend heeft, weet dat de resultaten heel snel heel groot worden. De faculteit groeit sneller dan de exponentiële functie. Bij een handmatige berekening is na de eerste tien faculteiten de lol er al van af. Microsoft Excel gaat reeds de mist in bij 21! omdat het resultaat dan niet meer in een 64-bits datatype past. Veel rekenmachines geven het op vanaf 70!, een getal van meer dan honderd cijfers. De ingebouwde Google calculator stopt bij 171!, een getal van ruim driehonderd cijfers dat niet meer in een 1024-bits datatype past.

Wij gaan met de Arduino starten waar Google het opgeeft en waar Microsoft al lang uit de achteruitkijkspiegel verdwenen is. We gaan zelf geen grote faculteiten berekenen, dat zou saai en inspiratieloos zijn. We gaan het leuk houden. De Arduino zal een cijferreeks ontvangen die al een faculteit is. In die cijferreeks zullen twee opeenvolgende cijfers gemaskeerd zijn. Deze cijfers zullen vervangen zijn door ‘xy’. Er moet een algoritme geïmplementeerd worden dat de twee ontbrekende cijfers x en y berekent.

Nemen we als voorbeeld iets klein en handelbaar, namelijk de faculteit van 21. Er geldt dat 21! = 51090942171709440000. De Arduino krijgt als input 510909xy171709440000 en moet daaruit afleiden dat dit enkel een faculteit kan zijn als xy=42. Het zal duidelijk zijn dat voor grote getallen zoals 999! de methode die de faculteit eerst volledig uitrekent niet de ideale oplossing is, of dat die berekening zelfs onmogelijk is met de beperkte resources op een embedded microcontroller.

Deze opdracht lijkt op het eerste zicht misschien onmogelijk. Er zit immers geen vast patroon in de cijfers van een faculteit. Toch is het mogelijk om met enig vernuft verbanden te vinden tussen x en y die samen toelaten om de oplossing ondubbelzinnig te bepalen, dit zonder de faculteit daadwerkelijk te moeten uitrekenen.

Dekimo zal periodiek hints vrijgeven. Wie de oplossing zelf vindt, krijgt op die manier een voorsprong. Maar ook wie er zonder hint niet geraakt, kan uiteindelijk wel tot de gewenste oplossing komen.

Deze wedstrijd is uitsluitend voor inwoners van België en Nederland. Vragen? Aarzel niet om ons te contacteren via het e-mailadres: studentchallenge at dekimo.com

Vraag hier je Arduino aan met de gedetailleerde instructies en doe mee aan de wedstrijd!

Om deel te nemen is het noodzakelijk om het formulier volledig in te vullen. De adresgegevens hebben we nodig om het pakketje te verzenden. Jouw gegevens zullen niet voor andere doeleinden gebruikt worden.

 

 

Wie het record breekt, voor minstens 6 uur, mag kiezen uit één van onderstaande prijzen:

  • 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 naar keuze voor PC, PS, Xbox of Switch bij Coolblue

Wie het record breekt, voor minstens 6 uur, mag kiezen uit één van onderstaande prijzen:

  • 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 naar keuze voor PC, PS, Xbox of Switch bij Coolblue

Challenge gelukt? Upload hier jouw resultaat.

We verwachten een .ino-bestand of een .zip als source-code voor de Arduino-firmware.
Opmerking:
Er wordt slechts één inzending per deelnemer aanvaard.

Heb je een graag een hint?

Dekimo zal periodiek hints vrijgeven. Wie de oplossing zelf vindt, krijgt op die manier een voorsprong. Maar ook wie er zonder hint niet geraakt, kan uiteindelijk wel tot de gewenste oplossing komen.

Scorebord Embedded Challenge recordhouders

Naam Tijd
Bram Demedts 50 ns
Michiel Van den Berghe 63 ns
Lowiek Van den Stockt 100 ns
Team Zeus WPI 100 ns
Toon Baeyens 125 ns
Zander Daninck 125 ns
Katrien D. 187 ns
Jan Dumon 250 ns
Johannes Taelman 250 ns
Hans Polders 310 ns
Noa Pauwels 437 ns
Tom Boschman 437 ns
Jelle De Vleeschouwer 937 ns
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.