Advent of Code 2018 en de grote winnaars

Maar niet alleen voor ons, ook voor anderen een bijzonder spektakel waarbij je andere developers kan zien zwoegen door bloed, zweet en tranen, vooral wanneer ze tegen een extra lastige puzzel aanlopen. Infi is al jaren sponsor van Advent of Code. In 2017 hebben we zelfs een eigen puzzel online gezet, met veel positieve reacties. Dit jaar wilden we niet minder zijn, dus hebben we weer een puzzel ontworpen. Benieuwd? Lees dan de blogpost over hoe de puzzel tot stand is gekomen.

Net als vorig jaar was er een unieke prijs voor de winnaars. De auteurs van de vijf beste oplossingen hebben van ons een zeldzaam “Keiharde Nerd”-shirt gekregen, normaal alleen voor Infi’ers. Enkele van de winnaars hebben hun code op verzoek van ons toegelicht voor deze blog!

De winnende oplossingen

Diederik Perdok

Hij ging voor een breadth-first-search algoritme in Python:

“Wat een eer om nu een officieel erkende nerd te zijn!

Het eerste deel van de puzzel was goed te doen: door het doolhof als een graaf te representeren kun je het kortste pad vinden met de bekende methodes. Omdat deze graaf ongewogen is (de afstand van een tegel tot een bereikbare tegel is altijd 1 stap) heb ik gekozen voor het breadth-first-search (BFS) algoritme, dat efficiënt is en makkelijk is te implementeren. Ik denk dat nog snellere oplossingen wel mogelijk zijn, bijvoorbeeld door gebruik te maken van de eigenschap dat het kortste pad tussen twee tegels nooit korter kan zijn dan de Manhattan distance, maar voor het oplossen van een enkel doolhof van 20×20 heb je eigenlijk geen hele efficiënte oplossing nodig.

Het tweede deel was een leuke hersenkraker. In een statisch doolhof kun je ervan uitgaan dat als een kortste pad van A naar B via C loopt, dat het begint met een kortste pad van A naar C, maar in het schuivende doolhof is dit niet langer het geval. Het is gelukkig wel waar dat het doolhof er na n stappen altijd hetzelfde uitziet, ongeacht hoe je in die n stappen bent gelopen. Van deze eigenschap maak ik gebruik in een aangepaste versie van BFS, die wel werkt in een schuivend doolhof maar sneller is dan brute-force alle mogelijke paden uitproberen.”

Jiri Bakker

Hij besloot om met Kotlin te gaan experimenteren.

“Dit jaar had ik besloten om met Kotlin te gaan experimenteren. Altijd leuk om met een nieuwe taal de uitdagingen die Advent of Code te bieden heeft te proberen op te lossen. De puzzel van Infi was al direct een stevige uitdaging. De eerste helft van de puzzel was vrij gemakkelijk te visualiseren en daardoor ook met niet al te veel moeite op te lossen door gebruik te maken van een Dijkstra algoritme.

Het veranderende doolhof bij de tweede helft van de puzzel maakte het echter aanzienlijk lastiger, en heeft me dan ook veel trial-and-error (en off-by-one fouten) gekost voordat ik eindelijk een logische aanpak had gevonden. Mijn uiteindelijke oplossing heb ik vervolgens nog een beetje opgeschoond voordat het toonbaar was voor het wijde publiek, maar uiteindelijk ben ik er best wel tevreden mee. Ik kijk alweer uit naar de AoC challenge van Infi in 2019!”

Maurits van der Schee

Hij doorzocht het doolhof met Ruby.

“Na even spelen met het JavaScript doolhof in de opgave werd al snel duidelijk dat het een ‘zoek’ probleem was. Mijn favoriete aanpak is om een lus te maken en een lijst met bij te houden met actuele (grens)posities. Deze lijst bevat aan het begin van het algorithme alleen de startpositie. Elke iteratie van de lus maak ik een nieuwe lijst met actuele posities. Elke positie levert een aantal nieuwe posities op afhankelijk van de (bidirectionele) verbindingen met naastliggende posities. Door een lijst bij te houden met reeds bezochte posities worden veel takken in de zoekboom afgekapt. Zodra de lijst met actuele posities de doelpositie bevat zijn we klaar. Het aantal iteraties dat deze lus nodig heeft om te termineren komt overeen met het minimale aantal stappen in het doolhoof van start naar doel (het antwoord).

In deel 2 moesten het veld en de grensposities opschuiven volgens een beschreven patroon. Hierbij was het belangrijkste dat je de verbindingen met de naastliggende posities zo laat mogelijk evalueerde, want deze verbindingen veranderden continu. Al met al een erg leuke puzzel, knap gemaakt!”

Tot volgend jaar!

Onze dank gaat uit naar Advent of Code voor het organiseren van de puzzels, en natuurlijk aan alle deelnemers die ook onze puzzel hebben opgelost.
We kijken erg uit naar de puzzels van volgend jaar, en hopen dan natuurlijk weer onze eigen puzzel te maken.

[Wilco is developer bij Infi]

Wil je op de hoogte blijven van updates over hippe tech, een kijkje achter de schermen, of upcoming events? Schrijf je in voor onze nieuwsbrief!