Distributed Code Jam
Školení, která pořádám 
Baví mě řešit programátorské úlohy, a proto jsem se účastnil i několika ročníků Google Code Jam. V roce 2008 jsem dokonce vydal seriál s řešením všech úloh. Letos jsem se do řešení zase pustil, tentokrát interně v Google – před veřejnými koly se konají ta stejná kola se stejnými příklady pro zaměstnance Google, aby se vychytaly případné mouchy. Letos nás čekala novinka – v jednom kole se úlohy spouštěly na propojených počítačích Googlu. Obvykle si řešení můžete naprogramovat v čem chcete a spouštíte ho na svém počítači (nebo ho klidně můžete udělat i na papíře). V Distributed Code Jamu řešení běží na předem daném počtu počítačů a můžete použít jen programovací jazyky, které podporuje běhové prostředí Googlu. Letos to bylo C, C++, Java, Python a Pascal. Z moderních jazyků chybí snad už jen Fortran.
Řešení Distributed Code Jamu bylo pro mě dost utrpení – běhové prostředí často nefungovalo; nástroj pro testování z příkazové řádky nepodporoval všechny jazyky; co fungovalo lokálně, nefungovalo distribuovaně (i když to běželo také jen na jednom počítači); informace o problémech s řešením byly extrémně skoupé (po dvou minutách testování programu jste se dozvěděli např. jen „RTE“). Ale proto ostatně existuje tohle interní kolo – víc problémů pocítí dobrovolníci Googlu a ne skuteční soutěžící. Do veřejného kola se doufám alespoň část těchto problémů podařilo vyřešit.
Když se ale na obrazovce objevilo zelené Correct, zažil jsem podobně opojný pocit, jako když jsem s programováním začínal. Tehdy mě totiž fascinovalo, že můžu počítači něco říct a on to pro mě udělá – třeba nakreslí kružnici nebo reaguje na klávesnici. V Distributed Code Jamu říkám počítači, co má říct dalším počítačům, aby pro něj udělaly. S propojenými počítači se samozřejmě běžně setkávám – replikace databáze, sharding, rozkládání zátěže. Přesto byl tohle výjimečný zážitek – počítače jsem totiž musel naučit, jak se spolu mají domluvit, což běžně není potřeba.
Při řešení úlohy se váš kód spustí paralelně na daném počtu strojů – třeba na 100. Na všech se spustí najednou ten stejný kód, který ale může zjistit své číslo stroje (např. od 0 do 99) a podle toho přizpůsobit své chování. Počítače si mezi sebou můžou posílat zprávy identifikované číslem stroje, na který se má zpráva poslat. Do daného časového limitu (např. 3 sekundy) musí všechny programy skončit a jeden z nich musí vypsat výsledek. Kromě toho je u každé úlohy omezena i paměť strojů, např. na 128 MB. Vstup nedostanete v textovém souboru, jak je běžně zvykem, ale v podobě API – sadě funkcí, které o problému vrací informace.
Shhhh
Zadání: Sedíte u obřího kulatého stolu a svému kamarádovi chcete poslat zprávu. Vaším úkolem je zjistit, zda bude kratší, když zprávu pošlete doleva nebo když ji pošlete doprava. Problém je, že znáte jen počet hostů a u každého hosta víte, kdo sedí bezprostředně vlevo vedle něj a vpravo vedle něj. Řešení
Řešení: Napadlo mě rozdělit hosty na jednotlivé stroje takhle – stroj 0 začne u hosta 0 a půjde doprava tak dlouho, dokud nenarazí na hosta s číslem dělitelným N / nodes, kde N je počet hostů a nodes je počet strojů. Stroj 1 začne u hosta s číslem N / nodes a udělá totéž. Stroj 2 u hosta 2 * N / nodes a tak dále. Každý stroj zjistí, jakým hostem končí jeho posloupnost, jak je dlouhá a zda v ní sedím já nebo můj kamarád. Všechny tyto informace pošle na master (např. stroj 0), který už z nich snadno poskládá, jak daleko zpráva půjde mému kamarádovi pravem. Pokud to je míň než půlka hostů, je odpověď „doprava“, jinak je odpověď „doleva“.
Problém s tímhle řešením je, že vstup může vypadat tak, že všichni hosti s číslem dělitelným N / nodes sedí vedle sebe. Všechny stroje tak zjistí informace o posloupnosti délky jedna a na poslední stroj tak zbude prakticky všechna práce. Jak bude vypadat vstup, dopředu nevíte, a zda ho váš algoritmus správně zpracoval, se dozvíte až na konci soutěže. Nemůžete tedy doufat, že snad vstup takhle vypadat nebude – když bych testovací vstupy pro úlohu dělal já, tak bych tam takovýto vstup určitě dal.
S tímto problémem jsem si dlouho lámal hlavu, až jsem nakonec použil náhodná čísla. Vygeneruji si posloupnost náhodných čísel dlouhou N a každý stroj začne hostem rands[id] (kde id je číslo mého stroje) a skončí, pokud bude u hosta, který v náhodné posloupnosti taky je. Sice to teoreticky může dopadnou stejně špatně jako u původního řešení, ale šance je nepatrná.
Všechny stroje musí pracovat se stejnou náhodnou posloupností. Tu si buď můžeme vygenerovat na jednom stroji a na ostatní ji poslat, nebo musíme generátor pseudonáhodných čísel nastavit všude stejně. Já jsem použil prosté srand(12345) doufaje, že testovací vstup nebude připraven na míru mému řešení…
Sandwich
Zadání: Máte bagetu, která má různé části po své délce různě dobré nebo špatné. Např. začíná šunkou, pak je špenát, pak sýr, pak zvratky a končí slaninou. Vaším cílem je sníst co nejvíc dobrého s tím, že můžete jíst jenom z obou konců – nemůžete začít uprostřed nebo něco přeskočit. Každá část je obodovaná (např. 4, -1, 3, -9, 2) a vaším cílem je maximalizovat počet bodů – v našem případě by to bylo tedy (4 + -1 + 3 ujedeno zleva + 2 ujedeno zprava). Řešení
Řešení: Nejrpve je dobré si uvědomit, že vlastně hledáme nejhorší část bagety a sníme všechno kromě této nejhorší části. To je mnohem jednodušší, než hledat dvě nejlepší části z obou stran.
Rozdělení na jednotlivé stroje je přímočaré – každý stroj dostane zpracovat N / nodes částí bagety (N je délka bagety, nodes je počet strojů). U této části zjistí: celkový součet, součet nejhorší části, součet nejhorší části při jedení zleva a součet nejhorší části při jedení zprava. Tyto údaje pošle na master (např. stroj s číslem 0), který z nich už snadno zjistí celkový součet a celkové minimum, což bude minimum z lokálních minim a přechodů mezi částmi (levá část zprava plus pravá část zleva).
Majority
Zadání: Probíhají volby a máme opravdu hodně kandidátů i voličů. U každého voliče vím, pro kterého kandidáta hlasoval. Cílem je zjistit, jestli některý z kandidátů dostal nadpoloviční většinu hlasů. Řešení
Řešení: Každému stroji dáme zpracovat N / nodes voličů (N je počet voličů, nodes je počet strojů). Každý stroj – budeme mu říkat okrsek – zjistí počty hlasů kandidátů, pro které hlasoval některý z jeho voličů. Teď by se nabízelo tyto počty prostě poslat na master (např. stroj 0) a sečíst tyto mezisoučty tam. To ale naráží na dva problémy – jednak by velikost zpráv byla větší než povolený limit a jednak by se všechna data na masteru nevešla do paměti.
Uděláme proto tohle: každý okrsek zjistí, jestli v něm některý kandidát získal nadpoloviční většinu hlasů. Vítěz s celkovou nadpoloviční většinou hlasů totiž musel získat nadpoloviční většinu hlasů aspoň v jednom okrsku – kdyby ji nezískal, tak bude mít maximálně nodes * N / nodes / 2 hlasů, což je jen polovina. Tohoto adepta na vítěze pošle každý okrsek na master. Takovýchto adeptů bude málo – maximálně nodes. Master tyto adepty pošle do všech okrsků, které mu pro všechny adepty vrátí počet hlasů v daném okrsku. To už se do paměti vejde pohodlně a povolenou velikost zpráv to také nepřekročí. Tadá! Když mi toto řešení prošlo, tak mě naplno zalil ten opojný pocit, že počítač dělá to, co chci – že jsem jeho pánem.
Diskuse je zrušena z důvodu spamu.
© 2005-2024 