Advent of Code 2020 a mé dojmy z Go

Letošní Advent of Code jsem využil k bližšímu seznámení s jazykem Go. V příspěvku popisuji, co to Advent of Code je, které úkoly se mi líbily, které mi daly nejvíce zabrat a sumarizuji mé dojmy z Go.

Co je to Advent of Code?

Pro ty, kteří o Advent of Code slyší prvně, bych jej chtěl krátce představit. Pokud víte, o co jde, tak tuto sekci klidně přeskočte.

Stručně řečeno, jedná se o verzi adventního kalendáře pro programátory :-). Jen místo mlsání sladkostí každý den plníte zadaný úkol, za jehož vyřešení získáváte zlaté hvězdy. Advent of Code je tvořen 25 úkoly, z nich každý je rozdělen na dvě části. Za splnění každé části dostanete zlatou hvězdu. Cílem celého snažení je získat těchto hvězd 50 (25 krát 2). Před zahájením práce na druhé části každého z úkolů je nejdřív potřeba splnit první část. Až po jejím splnění se vám odtajní zadání druhé části. Druhá část většinou nějakým způsobem navazuje na první část. Např. se jedná o rozšíření zadání, bližší dospecifikování některé části zadání (čti oprava), či navýšení výpočetní náročnosti. Zadání každého úkolu je pro každého společné. Co se liší, tak jsou vstupní data, která má každý unikátní. Cílem úkolů je vstupní data načíst, zpracovat podle zadání a vypsat výsledek. Po splnění každé části vyplníte vaše řešení do formuláře a dozvíte se, zda bylo vaše řešení správné. Pokud nebylo, tak máte samozřejmě možnost po určité krátké době učinit další pokus. K vypracování můžete využít jakéhokoliv programovacího jazyka či nástrojů.

Podoba a náročnost úkolů je značně variabilní. Zadání jsou ve své podstatě algoritmická, ale rámcově zapadají do Santových slastí a strastí. Např. v letošním Advent of Code se Santa vydal na zaslouženou dovolenou, a cílem bylo řešit překážky, na které narazil. Jednou z dovedností, kterou při řešení úkolů využijete, je schopnost odlišení, co je podstatné z hlediska zadání úkolu a co je jen omáčka. Úkoly jsou opravdu různorodé, a tak si např. vyzkoušíte louskání hesel, simulaci aplikačně-specifických procesorů, tvorbu syntaktických analyzátorů (kalkulačka s neobvyklými prioritami operátorů), řešení soustav rovnic, simulaci celulárních automatů, hraní her či řešení puzzles a rozpoznávání vzorů v obraze. Obtížnost jednotlivých úkolů se také velmi liší a závisí nejen na vašich znalostech a zkušenostech, ale i na tom, jak moc si s úkolem vyhrajete (zda vám jde o vymazlené řešení, či jedete na rychlost a čitelnost kódu a testy hážete za hlavu). Za sebe mohu říct, že zatímco některé úkoly mi zabraly 1-2 hodiny, tak u některých jsem strávil klidně 10-20 hodin. A troufám si tvrdit, že pokud člověk netuší, jak některý z úkolů principiálně řešit (např. neznáte matematický vzorec či informatický koncept), tak musí jistý čas věnovat i studiu. Alespoň se tak člověk něco nového naučí :-).

Advent of Code je v neposlední řadě také rychlostní soutěž. Ke zveřejnění každého úkolu dochází v určitý stanovený čas (letos tomu bylo v 06:00 CET), a čím dříve úkol vyřešíte, tím víc dostanete bodů (první získá 100 bodů, druhý 99 atd.). Pokud vás zajímá kompetitivní programování, tak určitě neváhejte. Za sebe mohu říct, že za ty časy, za které to ti nejlepší lidé řešili, jsem někdy nebyl ani schopen pochopit zadání :-D.

Proč zrovna Go?

S jazykem Go jsem měl jen omezené zkušenosti, které mi umožnily čtení a rozumné pochopení existujícího kódu, ale již určitě ne napsání vlastního kódu. Říkal jsem si, že letošní Advent of Code bych mohl využít právě na bližší seznámení s tímto jazykem, a tak jsem se do toho vrhnul střemhlav :-). Ze začátku jsem si sice vše musel dohledávat, ale později se to zlepšilo, protože úkoly v Advent of Code jsou algoritmické, takže není potřeba znát pokročilé koncepty z daného jazyka. Typicky stačí umět načíst vstupní data, naparsovat je do rozumných struktur, a zapsat algoritmus řešení. Co se týče datových struktur, tak obecně jako základ stačí umět práci s řetězci, poli (seznamy) a hashovacími tabulkami (asociativní pole, slovník).

Kromě řešení Advent of Code jsem během prosince prošel A Tour of Go, přečetl Go in Action a absolvoval část Ultimate Go Programming školení.

Co říkám na Advent of Code 2020?

Pozor: Tato sekce obsahuje brojlery. Pokud plánujete Advent of Code 2020 řešit, tak zvažte text níže přesočit a pokračovat sekcí o Go.

Kdybych to měl shrnout, tak celkově mě letošní úkoly bavily, a většina z nich se dala vyřešit během pár hodin. Bylo tam však pár úkolů, u kterých jsem strávil větší množství času (viz dále). Velmi oceňuji, že zadání úkolů bývají velmi přehledně specifikovaná, zasazená do Santova kontextu a doplněná o různé vtipné reference. Taktéž je skvělé, že u každého úkolu je uveden i příklad vstupu a výstupu, což lze s výhodou využít při testování. Jen v jednom případě se mi stalo, že jsem i přes procházející testy napsal řešení, které na osobním vstupu nezafungovalo korektně (den č. 19).

Co se týče vad na kráse, tak bych asi jen zopakoval to, co jsem již psal: Pokud nevíte, jak úkol řešit, tak se může stát, že vám zabere mnoho hodin, či klidně i několik dní, než dáte dohromady řešení. Některé úlohy tak bývají časově dost náročné, a pokud k tomu ještě člověk chodí do práce, tak účast na Advent of Code může být energeticky dosti náročná. Někdy taky člověk zjistí, že vytvořil sice funkční řešení, ale na osobním vstupu by běželo několik dní, a tak je potřeba zapracovat na optimalizaci :-). Je to sice mnohdy sranda, ale taky to jistý čas zabere. Každopádně, úkoly naštěstí není potřeba vyřešit hned během daného dne a můžete je splnit kdykoliv, i v jiném pořadí.

Které úkoly mě nejvíce bavily?

• Den č. 14. Simulace bitových instrukcí na 36 bitových hodnotách v 36 bitovém paměťovém prostoru.
• Den č. 17. Simulace Hry života (celulární automaty) v nekonečném trojrozměrném (a v druhé části čtyřrozměrném) prostoru :-).
• Den č. 18. Vytvoření kalkulačky pro operace, ve kterých mají operátory zvláštní priority (např. násobení má stejnou prioritu, jako sčítání, či pak ve druhé části naopak). Nejdřív jsem to chtěl řešit ad-hoc algoritmem, ale nakonec jsem sáhl po osvědčené precedenční syntaktické analýze zdola nahoru, pro studenty FITu známé z předmětu IFJ.
• Den č. 20. Algoritmické řešení skládačky a následné vyhledávání Lochnessek v obraze :-). Dalo mi to hodně zabrat, ale byla to zábava.

Které úkoly mi daly nejvíce zabrat?

• Den č. 10, část 2. První část byla v pohodě, ale druhá část již nešla upočítat obyčejným enumerováním všech variant. Bylo potřeba zapojit i tzv. memoizaci.
• Den č. 13, část 2. Druhá část opět nešla vyřešit hrubou silou, protože by to trvalo neskutečně dlouho. Bylo potřeba zjistit, jak efektivně řešit soustavy rovnic s modulem. Takovéto rovnice jsem nikdy neřešil, takže mi nějaký čas zabralo, než jsem přišel, jak na to.
• Den č. 20, obě části. Tato úloha mě hodně bavila (viz výše), ale byla zároveň jedna z časově nejsložitějších. Než jsem naprogramoval všechna možná prohození a rotace jednotlivých částí puzzle (obrázků) a dal dohromady funkční backtrackovací řešení, tak jsem nad tím strávil odhadem 15 hodin.
• Den č. 23, část 2. Musel jsem mé řešení optimalizovat, aby rozumně zvládlo spočítat 10 miliónů iterací, a i tak jsem zůstal na řešení, které na osobním vstupu běželo 4,5 hodiny. Víc už jsem se optimalizací nezabýval, protože tento úkol mě až tak moc nebavil. Mám ještě nápad na urychlení, tak jej pak možná někdy vyzkouším.

Adventní kalendář

Vypadá letos takto:

Pořadí úkolů bylo v kalendáři promíchané, což je důvod, proč je např. úkol 17 za úkolem 8.

Co říkám na Go?

Jak jsem již zmiňoval, řešení úkolů z Advent of Code si nevyžaduje využití všech výdobytků jazyků (stačí vám zvládat práci se soubory, řetězci, poli, mapami a základní řídicí konstrukce), takže ne vše jsem si z Go vyzkoušel. Např. na konkurentní a paralelní zpracování jsem se nedostal. Mé postřehy níže tedy prosím berte s rezervou ;-).

Co se mi líbilo?

• Nejedná se o složitý jazyk a základy se lze naučit během víkendu.
• Pokud znáte Céčko či jemu podobný jazyk, budete z hlediska syntaxe jako doma.
• Svižný překlad (oproti např. optimalizovanému C++).
• Vyprodukované binárky lze spustit bez nutnosti mít v systému nainstalované závislosti. Go totiž používá ve výchozím režimu statické linkování. Usnadňuje to spuštění binárek na jiných systémech, což se hodí např. při deploymentu.
• Automatický paměťový garbage collector, včetně escape analysis pro automatické určení, zda se má lokální proměnná vytvořit na zásobníku, nebo na haldě (angl. heap).
• Využívání návratových hodnot místo výjimek pro signalizaci chyb. Člověk tak na první pohled vidí, které funkce mohou selhat, a může se zařídit.
• Automatické formátování zdrojového kódu přes gofmt.
• Zobrazení dokumentace v terminálu přes go doc $WHAT.

Co se mi nelíbilo?

• Jazyk mi připadal, jako kdyby někdo předělával Céčko do kabátu 21. století, ale záměrně ignoroval vymoženosti známé z jiných jazyků a snažil se jazyk udělat co nejjednodušší, i za cenu toho, že jazyk bude působit předpotopně. Např. když jej srovnám s Rustem, který se objevil jen rok po Go, tak je to jako srovnávat nebe a dudy. U Rustu mi přijde, že si s ním tvůrci vyhráli a obsahuje spoustu pokročilých konceptů a možností, a Go oproti němu působí dost zastarale.
• Viditelnost identifikátorů (názvy typů, funkcí, proměnných) závisí na jejich pojmenování. Pokud chcete mít identifikátor veřejně viditelný, musí začínat velkým písmenem. Interní identifikátory začínají malým písmenem. Toto opravdu nemám rád (ani v Pythonu). Zbytečně to podle mě znepřehledňuje kód (názvy typů a proměnných mohou mít stejnou velikost písmen), při změně viditelnosti identifikátoru je potřeba změnit veškerý kód, který jej používá, a např. vytvoření typu nazvaného password s malým p vás nutí přemýšlet, jak pojmenovat proměnnou...
• Nemožnost vytvářet vlastní typově bezpečné generické typy a funkce (ve smyslu šablon v C++ či generických typů a funkcí v Rustu). Jediná možnost je použít generické vestavěné typy slice (dynamické pole) a map (hashovací tabulka). Chcete vlastní generický typ, např. reprezentující množinu? Máte smůlu. Dále, nepřítomnost podpory pro generické typy a funkce vede na to, že ve standardní knihovně je např. sort.Ints(), sort.Float64s() a sort.Strings() místo jedné generické sort() funkce, či nepřítomnost Abs() pro celočíselné typy (je pouze pro typy v plovoucí řadové čárce).
• S bodem výše souvisí i to, že když jsem potřeboval množinu obsahující hodnoty typu X, tak jsem měl smolíka a musel jsem použít map[X]bool. Vede to na zbytečně nepřehledný kód a otázky typu "K čemu je tam bool, když v kódu se false nikde nevyužije?".
• Neexistující typově bezpečné výčtové typy (angl. enum), včetně neexistence tzv. sum types (variant, discriminated union). Nelze si tak vytvořit typ pro hodnoty, které mohou být pouze X, Y, nebo Z.
• S bodem výše souvisí i to, že v jazyce a standardní knihovně není nic jako std::optional v C++ či std::option::Option v Rustu a s tím související podpora pro pattern matching. Ano, lze místo toho použít ukazatele a místo None vrátit nil (či vrátit nulu v případě číselných typů a prázdný řetězec v případě řetězců), ale zbytečně to znepřehledňuje kód.
• V případě funkce, která vrací buď hodnotu, nebo chybu, je potřeba vrátit obojí, i když žádná rozumná hodnota nemusí existovat. Nebylo by lepší mít něco jako std::result::Result a pattern matching v Rustu?
• Pro testování jsem používal standardní testing modul. Bohužel neobsahuje žádné aserce typu AssertEqual(), a tak jsem si veškeré kontroly a výpisy musel psát ručně. A pro porovnání dvou slices jsem si musel napsat funkci, protože pro ně nebylo == podporováno.
• Jazyk se tváří, že je v něm podpora pro n-tice (např. lze vytvořit funkci vracející dvojici int a error). Ovšem záhy zjistíte, že tato syntax funguje pouze pro návrat hodnot z funkcí, a pokud chce člověk využít n-tice na jiných místech, musí si k tomu vytvořit strukturu.
• Jazyk sice obsahuje tzv. foreach cyklus v podobě for index, element := range array {}, ale pokud index nepotřebujete, tak je potřeba psát for _, element := range array {}. Když totiž člověk napíše for x := range array {}, tak v x budou indexy, nikoliv hodnoty. Nemohlo to být naopak? V drtivé většině případů mi stačilo iterovat přes hodnoty a index jsem nepotřeboval. Např. jako je tomu v Pythonu a v jeho enumerate() funkci, kterou využijete, pokud kromě hodnot potřebujete i indexy. Podtržítka taktéž moc nepřidají na přehlednosti kódu.
• Jazyk sice obsahuje automatickou správu paměti ve formě garbage collectoru, ale když chcete např. otevřít soubor a ujistit se, že při skončení funkce bude vždy zavřen, tak nesmíte zapomenout použít explicitní konstrukci defer. Mnohem víc se mi líbí přístup RAII v C++ či Rustu, nebo context manager v Pythonu (když už chceme pro porovnání zvolit jazyk, jehož implementace mají taktéž garbage collector).

Zdrojové kódy

Zdrojáky k mým řešením všech cvičení jsou u mě na GitHubu.