De bedoeling van dit blog was, onder andere, om te gaan schrijven over project euler. Op dat moment was ik vol enthousiasme bezig om problemen zo snel mogelijk op te lossen. Soms duurde het uitrekenen van een oplossing iets te lang, vaak was de code slordig. Het enthousiasme kwam voornamelijk doordat project euler een andere tak van wiskunde gebruikt. Tijdens een opleiding natuurkunde word er weinig gebruik gemaakt van discrete wiskunde.

Ergens voorbij probleem 100 liep ik vast, wat was er mis gegaan. Een van de oorzaken was dat ik te weinig geleerd had door telkens de snelste en makkelijkste oplossing te kiezen. Een andere oorzaak was dat de code niet herbruikbaar was voor volgende problemen.Hierdoor lukte het ook niet meer om binnen een half uur iets af te krijgen.

Tijd voor een nieuwe aanpak. Ditmaal wil ik alle code verzamelen in een bibliotheek. Geen briljant idee, maar het vergt wat tijd om dit op te zetten. Tijd die ik hiervoor er nooit in gestoken had. Aan de hand van probleem 15 wil ik opschrijven wat hier zo leuk aan is.

Als we het voorbeeld bekijken, dan zien we dat er twee keer naar links gegaan moet worden en twee keer naar beneden. Dit is een combinatorisch probleem. Hiervoor grijp ik altijd terug naar mijn middelbare school. Stel we hebben een bak met twee rode en twee blauwe ballen. Op hoeveel verschillende manieren kunnen we deze ballen uit de bak trekken. Vier ballen kunnen op 4! = 4x3x2x1 = 24 verschillende volgordes gerangschikt worden. Maar de volgorde van de twee rode ballen maakt niet uit. De twee rode ballen kunnen op 2! = 2x1 = 2 manieren gerangschikt worden. Hetzelfde geld voor de blauwe ballen. Het totale aantal unieke volgordes is dus 4! / (2! x 2!) = 6. Normaal wordt dit 4 boven 2 genoemd.

De oplossing is gevonden, er moet alleen nog een programma geschreven worden dat 40 boven 20 uit rekent. Gelukkig herinner ik me dat ik de driehoek van Pascal al geïmplementeerd heb voor een eerder probleem. De oplossing in code is dus

return pascalTriangle.getValue(40, 20);

Dankzij het hergebruik van een voorgaande oplossing is de oplossing voor dit probleem bijna triviaal geworden.

Tot zover het enorme succesverhaal van mijn nieuwe bibliotheek.

Ter controle vergelijk ik dit antwoord met het antwoord wat ik hiervoor berekend heb. Het goede nieuws is dat het antwoord hetzelfde is, het slechte nieuws dat ik de oplossing niet meteen snap. Het probleem was dat ik de driehoek van Pascal nooit geïmplementeerd heb. In plaats daarvan probeer ik rechtstreeks de formule uit te rekenen: 40! / (20! x 20!). Het eerste getal 40! is veel te groot voor een 64 bits integer. Iets handiger is het om rechtstreeks 40! / 20! uit te rekenen, maar dit is nog steeds te groot voor een 64 bits integer. Dit was het probleem waar ik een oplossing voor moest verzinnen.

De oplossing die ik gevonden had was helaas niet de driehoek van Pascal. In plaats daarvan kan het probleem ook in 2 stukken verdeeld worden. Stel de eerste 20 ballen zijn allemaal rood, dan zijn de laatste 20 ballen allemaal blauw.  Dit kan op (20 boven 0) x (20 boven 20) = 1x1 = 1 manier gerangschikt worden. De eerste bal kan ook 1 blauwe bal hebben, dan is een van de laatste twintig ballen rood. Dit kan op (20 boven 1) x (20 boven 19) = 20x20 = 400 manieren gerangschikt worden. Door al deze manieren weer bij elkaar op te tellen kan het antwoord uitgerekend worden zonder een speciale grote getallen bibliotheek te gebruiken.

Dit is typisch een kunstige oplossing die achteraf behoorlijk klungelig blijkt te zijn. Wat het nog een beetje erger maakt is de volgende tekening.

Euler probleem 15 is niets meer of minder dan een stukje geknipt uit de driehoek van Pascal. Dat ik dit eerst helemaal niet gezien heb en vervolgens alleen via een omweg van rode en blauwe ballen ontdekt heb is toch wel spijtig.