Samen coderen, leren en uitdagingen aangaan

Op vrijdag 31 januari hebben we een workshop georganiseerd rondom een van de puzzels van de Advent of Code van afgelopen jaar.

In december 2024 vond de 10e editie van de Advent of Code plaats. Net als voorgaande jaren heb ik geprobeerd mijn collega's aan te sporen om mee te doen.

Wat is Advent of Code?

Advent of Code is een jaarlijkse adventskalender voor programmeurs. Van 1 tot en met 25 december 2024 vond de 10e editie plaats, waaraan uiteindelijk ruim 273.000 mensen hebben meegepuzzeld.

Het idee is eenvoudig: elke dag wordt er een nieuw probleem voorgeschoteld, verpakt in een verhaal dat door alle dagen heen loopt. De moeilijkheidsgraad neemt geleidelijk toe, waardoor je kennis van algoritmes, best practices en programmeertalen steeds verder op de proef wordt gesteld.

Het doel? Een leuke uitdaging die anders is dan je dagelijkse werk, en tegelijkertijd leer je misschien ook nog iets nieuws.

Hoe wij bij th[is] meedoen

Op de website is een leaderboard te vinden, maar deze wordt gedomineerd door deelnemers die er een sport van maken om de opdrachten zo snel mogelijk op te lossen. Sommige mensen zitten elke dag om 6 uur ‘s ochtends klaar om op hoog tempo oplossingen te schrijven.

Dat is niet de manier waarop het gros van de deelnemers te werk gaat. En wij dus ook niet.

Bij th[is] deden we het op onze eigen manier:

• Op ons Slack-kanaal werd automatisch een bericht gepost als een collega een ster had gehaald.
• Iedereen deelde links naar zijn of haar Git-repository.
• Bij het koffiezetapparaat en tijdens de lunch bespraken we het verhaal en hoe we de problemen probeerden op te lossen.

Het fijne van Advent of Code is dat je je eigen tempo kunt bepalen. Is dag 6 te moeilijk, of heb je geen tijd? Dan is er morgen weer een nieuwe puzzel. Had je vorige week geen tijd en nu een moment om er meer te doen? Dan kan dat. Je kunt alle opdrachten uit alle tien edities op elk moment maken.

De workshop

Omdat veel collega's Advent of Code wel een leuk idee vonden, maar in december geen tijd hadden, besloten we een workshop te organiseren.

Het idee: samenwerken aan één van de opdrachten, kijken of we hem succesvol konden afronden, en onze oplossingen met elkaar vergelijken. Waar liep je tegenaan? Hoe heb je dat opgelost? Hoe verschillen de oplossingen van elkaar?

De uitdaging: Dag 11

Met zes collega's gingen we in kleine groepjes aan de slag om de puzzel van dag 11 op te lossen.

De opdracht

"Een rij stenen met een ingegraveerd getal verandert elke keer dat je met je ogen knippert volgens een vaste set regels. De waarde kan veranderen of de stenen splitsen zichzelf in tweeën. Hoeveel stenen heb je na 25 keer knipperen?"

We werkten in drie verschillende teams: het Go-team, het TypeScript-team en een PHP-developer.

Al snel liepen we tegen een probleem aan: out-of-memory issues. De rij met stenen vermenigvuldigde zichzelf zo snel dat het beschikbare geheugen volliep.

Het leuke van de Advent of Code-puzzels is dat als je tegen dit soort problemen aanloopt, het geen zin heeft om simpelweg meer geheugen vrij te maken. De puzzels zijn zo ontworpen dat de verkeerde aanpak een onmogelijke hoeveelheid geheugen of rekenkracht vereist.

Het TypeScript-team was als eerste klaar en begon alvast aan deel 2 van de puzzel. In dit deel veranderde de opdracht: in plaats van 25 keer knipperen, moest je nu 75 keer knipperen. Dit maakte het probleem niet alleen veel groter, maar ook veel moeilijker op te lossen zonder slimme optimalisaties.

Het Go-team liep in deel 2 tegen performanceproblemen aan. De berekening duurde te lang en leek ook niet zomaar sneller te worden. Tijdens de voorbereiding had ik al wat testjes gedraaid in Emacs-Lisp, en daar kreeg ik mijn code niet sneller dan 0,001 seconde voor 75 keer knipperen. Alles wat langer dan een paar seconden duurde, was in feite te traag.

Na een korte pauze besloot een collega uit het Go-team het probleem zelf nog eens te proberen in PHP. Binnen een paar minuten had hij met een compleet andere aanpak deel 2 opgelost.

De oplossingen

De naïeve methode

Bij de naïeve methode wordt het probleem exact aangepakt zoals het beschreven staat: Elke steen verandert tegelijkertijd bij elke knippering. Dit betekent dat je uiteindelijk 250.000.000.000.000 getallen in geheugen moet houden. Als we uitgaan van 4 bytes per getal, komt dit neer op 1000 terabyte aan data.

Recursieve methode

Bij de recursieve methode bekijken we steen voor steen hoeveel stenen eruit komen na een knippering. Als we nog niet 75 keer geknipperd hebben, passen we dezelfde methode toe op elke steen in het resultaat. Vervolgens tellen we de hoeveelheden bij elkaar op. Omdat een bepaald getal op een bepaalde diepte meerdere keren kan voorkomen, kunnen we deze code versnellen door een cache toe te voegen.

We slaan het aantal stenen na het knipperen (de waarde) op bij de steen en zijn diepte (key). Hierdoor kunnen we de berekening overslaan als we deze combinatie opnieuw tegenkomen. Zonder caching zou deze methode uren duren, maar met caching was hij in de meeste gevallen binnen een seconde klaar.

Sparse map-methode

Bij de sparse map-methode houden we bij hoe vaak een bepaalde steen voorkomt in plaats van elke steen afzonderlijk te verwerken. 

Als een steen 1000 keer voorkomt, hoeven we niet 1000 keer dezelfde berekening te doen. In plaats daarvan berekenen we het effect één keer en verhogen we de nieuwe waarde met 1000 stenen.

Dit had twee voordelen: We hielden maar ongeveer 4000 stenen in geheugen, in plaats van miljoenen. Dit bracht het geheugengebruik terug naar slechts 16 KB, waardoor het probleem goed oplosbaar werd. Omdat de sparse map-methode al was geoptimaliseerd door berekeningen te groeperen, was extra caching hier niet nodig.

Conclusie

Het bespreken van elkaars oplossingen was niet alleen interessant, maar ook leerzaam. Het was mooi om te zien hoe verschillende programmeertalen en denkwijzen leiden tot snellere en efficiëntere algoritmes.

Advent of Code is voor ons meer dan alleen een puzzel. Het is een manier om nieuwe technieken te leren, creatief te denken en samen met collega’s te zoeken naar de beste oplossingen. Bij th[is] houden we van uitdagingen, innovatie en continue ontwikkeling. De volgende editie? Daar zijn we zeker weer bij!

Jeroen

Backend Developer