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.

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.