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í

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í

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í

Jakub Vrána, Výuka, 14.10.2015, diskuse: 0 (nové: 0)

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.