Advent of code 2021

1. prosince nastává čas adventních kalendářů. A já jsem tentokrát otevírala okénka takového, o němž jsem ještě na podzim vůbec netušila - až poslední listopadový den jsem sebrala kuráž a přidala se mezi účastníky akce s názvem Advent of code 2021. Už posedmé pogramátoři všech úrovní měli možnost otestovat své schopnosti řešitvrůznorodé úlohy.

Každý den se totiž účastníkům odemyká jedna hádanka (puzzle) bez ohledu na to, zda se jim tu předchozí podařilo vyřešit. Bez správného výsledku  první části úkolu se však nedostanete k jeho druhé polovině - celkem tak na řešitele čeká 50 puzzles, za jejichž rozřešení sbíráte hvězdičky a pokud jste dostatečně rychlí, tak i body do žebříčku (nicméně v našem časovém pásmu je to fakt úkol pro nadšence). Úkoly volně spojuje vánoční příběh, letos se odehrával pod mořskou hladinou, takže se řešila různá čidla ponorky, hrálo bingo s chobotnicí, protínaly proudy nebo zaměřovala štěrbina mořského příkopu.

Zadání puzzles je vždy stejné pro všechny účastníky a musím říct, že je výborně zpracované. Podstatu úkolu vždy autor pečlivě vysvětlil a názorně ukázal na jednoduchých datech, která posloužila i jako testovací. Řešitel však musí sám vymyslet postup, kterým úkol vyřeší, a patřičný program v libovolném jazyce napsat. Jako odpověď totiž slouží pouze výsledek. Kdyby někdo vstupní data zpracovával ručně, nikdo to neodhalí. Akorát kdo by se tak dřel, když ostrá data (jedinečná pro každého řešitele) čítala stovky položek. :-) Skupinka kolem PyLadies se několikrát virtuálně sešla a bylo super poslechnout si, kolika různými způsoby a algoritmy lze k úkolu přistoupit. Většinou jsem si jen zapsala názvy různých vychytávek, protože ostatní se pohybovali na diametrálně odlišné úrovni a přestože jsem vcelku chápala, na jakém principu jejich program funguje, sama bych ho rozhodně takto napsat nedokázala.

Úkoly byly velmi různorodé. Z těch 2*25 puzzles měl snad každý něco do sebe, každý mi dodal určitou sebejistotu nebo podněty, co nového bych se mohla (a potřebovala :-)) naučit. Nebudu zacházet do detailů řešení, ale chtěla bych i programováním nepolíbeným ukázat, jak takové hádanky mohou vypadat, protože před začátkem jsem si to moc neuměla představit. Zde je můj výběr těch, které mě zaujaly nejvíce...

Den šestý - Lanternfish

Na první pohled jednoduchý úkol, kde každý dostal zadanou populaci rybiček (ve formátu 3, 4, 3, 1, 2) a měl spočítat, na kolik kousků se namnoží za 80 dní. Každé číslo označovalo jednu rybičku a kolik dní zbývá do jejího rozmnožení. V každém kroku se tak všechna čísla zmenšovala a když dosáhla jejich hodnota nuly, vrátila se zpátky na nejvyšší možnou hodnotu plus se vytvořila nová rybička, která ale na první množení musela jako mládě čekat o něco déle.

S tím jsem si dala rady snadno, prostě jsem nechala svou populaci v seznamu a nastavila, jak se mají čísla chovat.

Překvapilo mě, když druhý úkol zněl naprosto stejně, jen se počítala populace po 256 dnech. Dosud totiž druhá část úkolu vždy sledovala něco jiného nebo měnila, jak se s daty pracuje. V čem vězí háček jsem zjistila hned. Počáteční hejno totiž čítalo 300 rybiček, spousta se množila hned v dalším kroku... takže nevyhnutelně zabraly celou paměť počítače. :-) Musela jsem tedy program přepsat a místo seznamu napsat slovník, který obsahoval vždy fázi vývoje a počet ryb, které se v ní aktuálně nacházejí, přičemž hodnoty pak mezi fázemi posouval. To bylo mé první intenzivnější setkání s jakousi primitivní optimalizací - přirozeně zabere méně místa doslova pár čísel, než seznam stovek, tisíců, milionů čísel, znovu a znovu procházený po každém virtuálním dni.... Mimochodem, výsledek byl třinácticiferný. :-)

Podobným způsobem jsem pak vyřešila i den čtrnáctý, který místo ze seznamu vycházel z řetězce.

Co mě úkol naučil: Některé formáty dat jsou pro zpracování vhodnější než jiné a někdy stačí znát jen počty, ne každého jednotlivce.

Den osmý - Seven Segment Search

Jakýsi přístroj na palubě ponorky se porouchal -  drátky v jeho klasickém digitálním sedmidílném displeji se pozpřeházely.

Výchozí data tvořila 200 řádků v tomto formátu: 

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf

Každé písmeno představovalo jednu svítící čárku na displeji, jenže v každém řádku jinou. Jednička mohla být zapsána jako ab, ba, ec, gb... ale vždy šlo o dvoupísmennou kombinaci, protože na displeji svítí dvě čárky. Část před svislou čarou obsahovala vech 10 možných číslic v náhodném pořadí, část za čarou pak čtyřčíslí, s nímž se dále pracovalo.

První úkol mi vůbec nečinil potíže. Měli jsme spočítat, kolik celkem obsahují naše vstupní data čísel 1, 4, 7 a 8, což šlo snadno - nechala jsem program spočítat, kolik "slov" za čarou má délku rovnou dvěma písmenkům (jednička), čtyřem (čtyřka) a tak dále. Tyto číslice totiž tvoří jedinečný počet svítících čárek na displeji a je šumafuk, jaká kombinace písmen je reprezentuje.

Jenže u druhého úkolu byl zapotřebí rozluštit i zbylých šest číslic, protože se po nás vyžadovalo zjistit součet všech čtyřčíslí za svislou čarou. A tam jsem na dloooooouho ztroskotala. Tento úkol jsem rozlouskla až kolem Silvestra. Od začátku jsem tušila, že musím programu nějak říct "hele, když to má pět písmen, a z toho tohle je společné s jedničkou a tohle a tohle se čtyřkou, tak je to dvojka", ale netušila jsem, jak přesně na to, protože jsem sice dokázala zjistit, že jednička je to dvoupísmenné, ale už jsem nedokázala zjistit, které písmeno je ta horní/dolní čárka na displeji. O složitějších číslech nemluvě.

Až po třech týdnech, kdy jsem se k úkolu vrátila, mi došlo, že přece nemusím řešit, která čárka je která, stačí jen porovnat, kolik písmen mají různé číslice společné. "Tohle je jednička, tohle je čtyřka, a když má tohle číslo s jedničkoku společný jeden znak a se čtyřkou dva, tak je to dvojka!". Malá změna v kurzu myšlení přinesla sice dlouhý kód, který by zkušenější programátor zhurta zkrátil, ale projevil se jako zcela funkční, takže volejte sláva. :-)

Co mě úkol naučil: Někdy je dobré dát si čas na promyšlení strategie a i když to trvá dlouho, není to beznadějné.

Den desátý - Syntax Scoring

Po všem tom přiřazování čísel a písmenek jsem uvítala úkol, kde se pracovalo pouze se závorkami. Vstupní data představovalo 90 takovýchto řádků:

<[<(<{<[([[[{[()[]][<>{}]}[{(){}}{<><>}]]{<([]{}){()<>}>[({}<>)<<>[]>]}][<[({}[]){()[]}][<<>{}><()<>

Cílem bylo napsat program, který z řádků postupně vyškrtá uzavřené dvojice závorek, a zbylé torzo zařadí mezi corrupted (obsahuje zavírací závorku, ale neodpovídajícího druhu) nebo incomplete (zbyly jen otevírací závorky). Pochopit rozdíl mezi těmito dvěma kategoriemi pro mě předtsavovalo nejtěžší část úkolu, nechápala jsem totiž, jak to škrtání funguje. Musela jsem si opsat testovací data na papír a barevně si značit, kolik je jakých závorek, jak se škrtáním ostatních dostávají k sobě a jestli moje teorie odpovídá výsledkům testovacích dat. Když jsem věděla, podle čeho řádky roztřídit, samotné třízení a spočítání výsledku (každý typ neškrtnuté závorky byl ohodnocen určitým počtem bodů) už mě příliš nepotrápilo.

Co mě úkol naučit: Něco z terminologie a fakt, že i v programování se najde využití pro papír, tužku a barvičky <3 :-)

Den třináctý - Transparent Origami

Jedna z nejoriginálnějších úloh! Dostali jsme papír s pomyslným souřadnicovým systémem a instrukce. Instrukce se skládaly ze dvou částí: souřadnic, kde bylo něco napsáno (#), a seznam os (horizontálních i vertikálních), podle nichž se měl papír přeložit.

První úkol zněl spočítat, kolik hashtagů bude viditelných po prvním přeložení, protože pokud se přeložením na sebe dostaly dva křížky, splynuly v jeden. Druhý úkol velel přeložit papír podél všech os, z křížků pak mělo vzniknout osmipísmenné heslo. I když jsem trochu zápolila se zapsáním do kódu, má myšlenka, jak se k výsledku dostat, se ukázala jako správná, což mě hodně potěšilo, protože já a prostorová orientace, to se taaaaakhle míjí. :-) Mých původních 815 bodů se pak zformulovalo v tento výsledek:

Co mě úkol naučil: Nepanikařit, protože ne každá 3D úloha vyžaduje 3D řešení.

Zajímalo mě, kolik zvládnu vyřešit, když úkoly neodpovídají zrovna porbíraným tématům v kurzu.

Den sedmnáctý - Trick Shot

Velmi povzbuzující puzzle - předchozí dva dny jsem nevyřešila doteď, ale tady jsem uspěla v obou částech.

Z malého kanónu se souřadnicemi [0, 0] jsme se měli strefit do vymezené obdélníkové oblasti. Na naši střelu přitom působila gravitace a odpor vzduchu, což ovlivňovalo trajektorii. Měnili jsme výšku a sílu rány a sledovli, kam nejvýše můžeme dostřelit a kolika různými způsoby můžeme vystřelit, abychom zároveň zasáhli cíl. Hravý, pochopitelný, snadno představitelný úkol.

Co mě úkol naučil: I když máš pocit, že už ti v náročnosti úkolů ujel vlak, v dalším se můžeš znovu chytit.

Den dvácátý - Trench Map

Mapa se skládala z tmavých (.) a světlých (#) bodů, v každém kroku se přetvářela. Tmavé body odpovídaly nule, světlé jedničce, a v každém kroku měl program prohlédnout sousední body přetvářeného bodu, vytvořit z nich číslo v binárním formátu (třeba 001011101), toto číslo převést na "klasický" formát a v dešifrovačním řetězci se na pozici s tímto pořadovým číslem nacházel výsledný znak (opět buď tečka, nebo křížek). Kolik křížků bude na mapě po dvou přetvořeních?

Háček nespočíval v tom, co jsem shrnula výše, nýbrž v tom, že mapa byla nekonečná - tím, že jsme vždy museli zohlednit sousedy každého bodu, rozrůstala se v každém kroku o jedno políčko do všech směrů. Myslela jsem si tedy, že když si přidám do všech stran rezervní vrstvu prázdných bodů, bude vymalováno. Testovací data moou hypotézu potvrdila, s ostrými jsem nepochodila. Až v naší skupince řešitelů jsem narazila na nápovědu pořádně si prohlédnout dešifrační řetězec. Ta mrcha v ostrých datech začínala opačným znakem, takže to nekonečné pozadí, které jsem si reprezentovala "prázdnými, tmavými" tečkami nebylo vždy prázdné - blikalo! Světlé se překlopilo do tmavého, to pak zase do světlého, a tak pořád dokola. To proto, že z bodu a jeho okolí nevznikla znovu tečka, ale křížek (samé tečky -> 000000000 -> "naše běžná" 0 -> první pozice v řetězci (v programování se počítá od nuly) -> výsledný znak # -> příště je nekonečný prostor ne ze samých teček, ale ze samých křížků, tedy 111111111...

Natěstí stačilo ještě trochu navýšit prázdný prostor a říct programu, aby pro nekonečno počítal se stejným znakem, jako má na své první souřadnici. Ale nebýt popostrčení z diskusního fóra, nevím, nevím, jak dlouho bych hledala, proč mi program pro ostrá data nefugnuje správně. :-) Velkou radost mi přineslo zjištění, že jsem program napsala tak, že utáhl i druhou polovinu hádanky, kde se obrázek přeměňoval 50x.

Co mě úkol naučil: Testovací data jsou skvělý sluha, ale neříkej hop, dokud nepřeskočíš.

Celkové shrnutí:

Advent of Code mi překvapivě zpříjemnil předvánoční čas. Hádanky mě bavily a vždy, když už se zdálo, že se mi náročnost úkolů vymyká, poslal nám autor úlohu, která mi dovolila doáhnout aspoň na jednu hvězdičku. AoC mi poskytl spoustu materiálů na procvičení, takže dokážu mnohem jistěji sestavit cykly, upravit si formát dat a podobně, zkrátka jsem si na něm odbyla nezbytný dril, aby mi základní věci vešly do krve. Troufám si říct, že mi i procvičil mozek, přiměl mě hledat řešení z pro mě ne zcela obvyklých úhlů. Ohromně mě potěšilo, že jsem velmi často hned nebo brzy pochopila, jaký zvolit postup, byť jeho zapsání do programu mnohdy trvalo hooodně dlouho.

Protože se chci programování věnovat i dále, mám v plánu si projít i starší ročníky Adventu a procvičovat si nové dovednosti. Na našem fóru a videokonferencích jsem pochytila názvy spousty vychytávek, které bych se chtěla naučit aktivně používat. Věřím tedy, že až se bude otevírat první okénko příštího kalendáře, budu schopná napsat programy mnohem čitelnější a efektivnější.

A moje úspěšnost? Na začátku jsem netušila, co čekat, když úkoly nezohledňují, co jsme brali a nebrali v kurzu. :-) Odhadovala jsem, že při troše štěstí bych mohla uspět tak ve třetině, čtvrtině případů. S určitou mírou hrdosti jsem však při svém debutu dosáhla skóre 33/50 hvězdiček, takže 66 %. Po tříměsíčním kurzu? Podle mě solidní! Kladu si za cíl ještě dvě hvězdičky někde urvat, abych byla na 70 %, tak uvidíme, jestli se zadaří. Protože jak jsem se naučila nejen na digitálních displejích - na správné řešení není nikdy pozdě. :-)

A co vy? Máte rádi podobné hádanky? Otevíráte políčka nějakého adventního kalendáře?