Advent of Code 2019: winnende hulp voor de kerstman

Al jaren is Infi sponsor van Advent of Code en onze developers zien dan ook uit naar de puzzels die ze in de decembermaand mogen oplossen. Intern was er een flinke competitiestrijd om de hoogste positie op het leaderboard te behalen, want wie kan 25 dagen lang iedere dag weer zo snel mogelijk die puzzel oplossen? Het bleek dat de man van de langste adem onze meesterpuzzelaar Wilco was, niet geheel ontoevallig ook de designer van onze eigen puzzel in 2018.

Ook dit jaar hebben we weer een puzzel met een actueel thema gemaakt: vanwege de klimaatverandering smelt het ijs op de Noordpool hard en hebben alle rendieren natte voeten gekregen. Daardoor zijn ze verkouden geworden en moet de Kerstman dit jaar zonder rendieren op pad. Aan de deelnemers de taak om de Kerstman te helpen de cadeaus op de meeste efficiënte manier op het Infi kantoor te krijgen.

Deelnemers aan de Infi puzzel konden hun oplossing inzenden. Onder de inzenders hebben we aantal Infi “Keiharde Nerd” t-shirts verloot. Uit de inzendingen viel op dat Python de meest gebruikte taal is, maar ook C++ kwam een paar keer terug. Er waren een aantal optimalisaties mogelijk om het algoritme sneller te laten performen en niet alle paden uit te rekenen. De Breadth-First Search was de meest gebruikte.

Alhoewel de puzzel in het Nederlands was hebben we ook een aantal oplossingen gekregen vanuit het buitenland; Jonas Vander Vennet uit Gent, België schreef:

Het eerste deel van de opgave was eerder een kennismaking met de notatie en het concept, wat wel welkom was achteraf bekeken. Een zeer leuk idee om de kerstman zo van dak tot dak te laten springen! In het tweede deel, de eigenlijke puzzel, werd de zoekruimte van mogelijke oplossingen zeer snel zeer groot. Dat is waarom ik ervoor gekozen heb zo snel mogelijk onbruikbare takken in de zoekboom te elimineren. De redenering “als je minder ver geraakt ben met meer verbruikte energie, zal je nooit optimaal worden” bleek voldoende te zijn om het hele zoekproces nagenoeg direct uit te voeren. Het was een aangename uitdaging, en ik kijk ernaar uit mij er volgend jaar weer een avondje aan te zetten!

Naast inzendingen uit Vlaanderen, was er ook iemand in de Verenigde Staten die met de Infi puzzel aan de slag ging. Voor Bill Rockenbeck uit Redmond, Washington is het genoeg wat Duits te kennen om ook Nederlands te kunnen lezen:

I can read Dutch pretty well, thanks to knowing some German!

…

If I recall correctly, the puzzle solution was just a textbook-standard application of Dynamic Programming. I’m a little embarrassed to have it held up as any kind of example. I’m a noob at Python and haven’t really settled on any kind of naming convention. That one ended up with a weird mishmash of Dutch and English words. I enjoyed playing your game, and it kept me entertained between Advent of Code puzzles. It was especially fun for me to decipher the Dutch as an additional layer of complication. I hope you do another next year!

We vonden dit jaar wel dat er een “winnaar” moest zijn. Uit alle inzendingen hebben wij een “leukste/origineelste/beste” oplossing gekozen. Die eer gaat naar Splinter Suidman uit Utrecht. Splinter schreef over zijn oplossing:

Het eerste deel van de puzzel was vrij simpel: ik representeer de flats als een map, zodat snel gevonden kan worden of er een flat staat bij een bepaalde x-coördinaat, en zo ja, hoe hoog die flat is. Dan loop ik de lijst van sprongen door als de kerstman een sprong heeft gedaan komt hij aan bij bepaalde coördinaten (x, y). Als er bij die x geen flat staat, dan valt de kerstman; als er wél een flat staat, maar als die flat hoger is dan de y-coördinaat van de kerstman, dan botst hij tegen de flat aan; in het andere geval kan de kerstman veilig landen, en vervolgt hij zijn weg vanaf de coördinaten (x, hoogte van de flat). Deel twee was een stuk lastiger, en heb ik op een algebraïsche manier benaderd. Eerst heb ik gekeken of we een oplossing kunnen bedenken door steeds naar twee afzonderlijke opeenvolgende flats te kijken. Als de tweede flat te bereiken is met één sprong, dan is een (maar niet de beste) oplossing om een sprong te doen naar elke flat, zonder er één over te slaan. Ik vond echter een tegenvoorbeeld met drie flats, bijvoorbeeld: [(0, 3), (2, 1), (4, 3)]. De ‘naïeve’ oplossing geeft de sprongen [(1, 0), (1, 2)] (totale energie: 4), terwijl een betere oplossing [(3, 0)] (totale energie: 3) is. Als de middelste van de drie flats lager is dan de eerste en tweede, dan is het in sommige gevallen voordeliger om de tweede flat over te slaan. (In de andere gevallen blijkt dat we de tweede flat nooit over moeten slaan.) In mijn oplossing bekijk ik dus steeds de komende drie flats; als de middelste flat lager is dan de eerste en derde, gebruik ik wat rekenwerk om te bekijken of we de tweede flat moeten overslaan. In de andere gevallen laat ik de kerstman eerst van de eerste naar de tweede flat springen, en vervolgens vind ik een oplossing voor de overige flats (recursief, dus). Nu ik terugkijk op mijn oplossing, denk ik dat deze niet in het algemeen de beste oplossing geeft, omdat er nooit twee flats in één sprong overgeslagen worden, terwijl dat soms waarschijnlijk wel een betere oplossing kan geven… Maar, hij werkte in ieder geval voor de invoer!

Wij vonden dat Splinter de prijs verdiend had om 2 redenen:

1. Zijn oplossing was als enige geschreven in Haskell (en veel mensen bij Infi hebben een softspot voor functionele programmeertalen

oplossingDeel1 :: Int -> (Int, Int) -> [(Int, Int)] -> Int
-- De kerstman bereikt het laatste flatgebouw.
oplossingDeel1 stappen _ [] = 0
-- De kerstman doet de sprong (dx, dy) en daarna de sprongen in 'sprongen'.
oplossingDeel1 stappen (x, y) ((dx, dy):sprongen) =
  -- De kerstman beweegt, naast de sprong, met dx = +1.
  let (x', y') = (x + dx + 1, y + dy) in
    -- Kijk of er een flat staat bij y-coördinaat y'.
    case Map.lookup x' flatsMap of
      -- Als er een flat staat en de kerstman botst niet tegen de flat aan:
      Just yFlat | yFlat <= y' ->
        -- Vervolg de weg vanaf de flat.
        oplossingDeel1 (stappen + 1) (x', yFlat) sprongen
      -- Er staat geen flat, dus de kerstman valt, of de flat is te hoog en de
      -- kerstman botst er tegenaan.
      b -> stappen

deel1 :: IO ()
deel1 = print $ oplossingDeel1 1 (head flats) sprongen

2. Daarnaast had Splinter zijn code uitvoerig gedocumenteerd, zowel met inline commentaar zoals hierboven te zien, alsook met een commentaar blok waarin hij zijn oplossingstrategie uiteen zet.

Een eervolle vermelding is er voor Jonas Vander Vennet voor de volgende regel code:

class SantaDiedException(Exception):

Gelukkig is het maar een spelletje en is volgende jaar de kerstman gewoon weer van de partij ;-). Evenals de advent of code en de Infi puzzel!