Advent of Code 2025

Az AoC egy egyedülálló utazás, amiben idén első alkalommal vettem részt. Az első napok könnyed ujjgyakorlataitól indulva hamar eljutunk oda, ahol már nem elég az alapok ismerete - algoritmuselméletre, adatszerkezetek mélyebb megértésére és optimalizációra van szükség. Ez egy kiváló fejlődési lehetőség.

1. nap: A titkos bejárat

A kaland egy klasszikus szimulációval indult, ahol egy széf zárját kellett tekergetni különféle utasítások alapján. A legnagyobb kihívást a tárcsa körkörössége jelentette, hiszen 359 fok után újra a 0 következik. Bár sok kezdő programozó ilyenkor bonyolult elágazásokkal próbálja figyelni a határértékeket, a repository megoldása sokkal elegánsabb utat választott: a modulo aritmetikát. A maradékos osztás operátora (%) segítségével a kód automatikusan, egyetlen matematikai képlettel kezelte a túlcsordulást, így a forgatás lekövetése lineáris és hibabiztos maradt felesleges if-else szerkezetek nélkül.

2. nap: Az ajándékbolt

A második napon egy adatbázis-tisztítási feladat várt ránk, ahol speciális karakterismétlődési szabályok alapján kellett kiszűrni az érvénytelen azonosítókat. Itt mutatkozott meg először a Python szövegkezelési ereje. Ahelyett, hogy a szerző manuálisan, ciklusokkal iterált volna végig a karaktereken – ami lassú és sok kódolást igényel –, a re modult, azaz a reguláris kifejezéseket hívta segítségül. A visszautaló csoportok használatával egyetlen tömör mintával detektálhatók voltak a duplázódó karakterek, ami a deklaratív programozás szép példája: nem azt írjuk le, hogyan keressen a gép, hanem azt, hogy mit.

3. nap: Elemcsere

Az elemek párosítása a maximális feszültség eléréséhez egy tipikus kombinatorikai probléma volt. A naiv megközelítés ilyenkor általában két egymásba ágyazott ciklust jelent, ami azonban könnyen átláthatatlanná válhat. A megoldás itt az itertools könyvtár combinations függvényére támaszkodott. Ez az eszköz generátorként működik, vagyis memóriahatékonyan, "röptében" állítja elő a lehetséges párokat, garantálva, hogy minden variációt pontosan egyszer vizsgálunk meg, mindezt pedig rendkívül olvasható formában.

4. nap: A nyomda

Ahogy a történet a nyomda részlegre kanyarodott, egy rács alapú logisztikai problémával szembesültünk. A feladat rávilágított a memóriakezelés fontosságára: mivel a rács ritka volt és potenciálisan hatalmas, a hagyományos kétdimenziós tömbök használata pazarló lett volna. A Pythonos megoldás ehelyett koordináta-alapú szótárakat (dict) vagy halmazokat alkalmazott. Ebben a megközelítésben csak a létező objektumok koordinátáit tároljuk el, így a térkép mérete nem a terület nagyságától, hanem csak az elemek számától függ, a lekérdezés pedig villámgyors marad.

5. nap: A büfé

A büfében felmerülő leltározási feladat a hatalmas számok világába kalauzolt, ahol milliárdos nagyságrendű azonosító-tartományokat kellett kezelni. Egyértelmű volt, hogy minden egyes számot lehetetlen eltárolni, ezért az intervallum-aritmetika volt a célravezető. A megoldás kulcsa a tartományok kezdőpont szerinti rendezése volt. Miután a listát a sort() metódussal rendezték, egyetlen lineáris átfutással összefésülhetők voltak az átfedő szakaszok, így a brute-force módszerrel megoldhatatlan feladat másodpercek alatt futtathatóvá vált.

6. nap: Szemétprés

A hatodik napon egy furcsa matematikai szintaxis kiértékelése volt a cél, ahol a műveleti sorrend eltért a megszokottól. Ez a probléma a verem (stack) adatszerkezet használatát igényelte. A megoldás során a nyitó zárójeleket és a számokat a verembe gyűjtötték, majd zárójel bezárásakor visszamenőlegesen értékelték ki a műveleteket. A Python listák append és pop műveletei természetes módon támogatják ezt a LIFO (Last-In, First-Out) működést, így a "Shunting-yard" algoritmus logikája könnyedén implementálható volt.

7. nap: Laboratórium

A tachyon-sugarak útjának követése a laboratóriumban egy klasszikus gráfbejárási feladat volt. Mivel a sugarak szétválhattak és pattoghattak, a rendszer állapotait egy sorban kellett nyilvántartani. Itt a collections.deque használata volt a technikai finomság: ez a kétvégű sor nagyságrendekkel gyorsabb a lista elejéről való törlésben, mint a hagyományos listák. Ez a sebességkülönbség kritikus fontosságú volt a Szélességi Keresés (BFS) hatékony futtatásához, elkerülve, hogy a program a memóriaműveletek miatt lassuljon be.

8. nap: Áramkörök

A csatlakozódobozok összekötése a gráfelmélet "összefüggő komponensek" problémakörébe tartozott. A feladat lényege az volt, hogy megtaláljuk, mely dobozok alkotnak már egy hálózatot. Erre a legprofibb eszköz a Union-Find (Disjoint Set Union) algoritmus, amely szinte azonnal képes eldönteni két elemről, hogy egy csoportban vannak-e. Bár rekurzív mélységi bejárással (DFS) is megoldható a feladat, a Union-Find használata mutatja igazán a versenyprogramozói rutint.

9. nap: Mozi

A moziterem csempézési feladata visszavezetett minket a geometriához és a gyors kereséshez. A legnagyobb téglalap megtalálása piros csempék között könnyen lassú, négyzetes futásidejű kódhoz vezethetett volna. A megoldás itt is a megfelelő adatszerkezet választásán múlt: a koordináták halmazban (set) való tárolása lehetővé tette, hogy amikor két pontot vizsgáltunk, a téglalap hiányzó sarkainak létezését O(1) időben, azaz azonnal ellenőrizni tudjuk, drasztikusan felgyorsítva a keresést.

10. nap: A gyár

A gyári gépek inicializálása tipikus "szimulációs csapda" volt. A gépek különböző periódusidővel működtek, és a feladat azt kérte, mikor állnak majd újra szinkronban. Aki megpróbálta ezt másodpercenként leszimulálni, annak a programja valószínűleg sosem futott le. A helyes megközelítés tisztán matematikai volt: a Legkisebb Közös Többszörös (LCM) kiszámítása. A Python math.lcm függvénye segítségével a megoldás a ciklusok hosszából azonnal számolható volt, szimuláció nélkül hidalva át a milliárdos lépésszámot.

11. nap: Reaktor

A reaktorban a legrövidebb út megtalálása volt a cél, de a csavar az volt, hogy az egyes lépések költsége eltérő volt. Ilyen súlyozott gráfokon a sima BFS nem garantálja az optimális eredményt, ezért a Dijkstra-algoritmusra volt szükség. A Pythonban ezt a heapq modul segítségével valósítják meg: a prioritási sor mindig a legkisebb költségű, még felderítetlen csomópontot kínálja fel feldolgozásra. Ez a "mohó" stratégia biztosította, hogy a lehető legkevesebb felesleges lépéssel jussunk el a célig.

12. nap: Fenyőfa farm

A tizenkettedik napon a fenyőfák elhelyezése egy komplex csomagolási és optimalizációs problémát jelentett. Az ilyen rekurzív feladatoknál a lehetséges variációk száma exponenciálisan nő, ami gyorsan lefagyasztja a gépet. A megoldás kulcsa a dinamikus programozás, pontosabban a "memoization" technika volt. A Python @functools.cache dekorátorának használatával a függvények "emlékeztek" a korábban már kiszámolt részeredményekre (pl. mekkora terület fedhető le a maradék fákkal), így a kódnak sosem kellett kétszer ugyanazt a szituációt megoldania, így gyorssá téve a futást.

Mi a tanulság? Matematika > Nyers erő: Mielőtt ciklust írnál 1 milliárdig, gondold végig: nincs rá formula vagy képlet (LCM, modulo, Gauss)?!