Google Code Jam 2008 – cvičení

Školení, která pořádám

Článek vyšel na serveru Programujte.com.

V soutěži Google Code Jam se řeší přesně ten typ úloh, které jsme dostávali za domácí úkol na Matfyzu a nad kterými jsem přemýšlel třeba při cestě metrem. Nejsou příliš složité, takže se jejich řešením nezabere moc času, ale ani příliš jednoduché, takže člověk přece jenom musí zapojit mozek.

V tomto článku přináším zjednodušené zadání cvičných úloh a jejich řešení v PHP. Pro zájemce o vlastní řešení úloh doporučuji přečtení úplného znění úloh, kde je zadání popsáno mnohem pečlivěji. Také je v nich uveden formát vstupu a výstupu, čímž se tento článek nezabývá. Pro každou úlohu jsou vždy připraveny dva vstupy – pro vyřešení „malého“ vstupu obvykle stačí úlohu vyřešit jakýmkoliv způsobem, „velký“ vstup vyžaduje návrh efektivního řešení.

Mimozemská čísla

Zadání: Číselná soustava mimozemšťanů je definovaná posloupností znaků seřazených podle hodnoty čísla, které znak reprezentuje. Např. v soustavě oF8 vyjadřuje o nulu, F jedničku a např. 8o šestku. Úkolem je převést číslo zapsané v jedné soustavě do druhé soustavy. Řešení

Vždy zahni doleva

ukázka bludištěZadání: Perfektním bludištěm se dá projít tak, že se třeba levou rukou chytneme jedné stěny a jdeme tak dlouho, dokud nepřijdeme na konec. „Perfektní“ je takové bludiště, které je pravoúhlé, má jeden vchod na severní straně a východ na kterékoliv straně a mezi každými dvěma místnostmi vede právě jedna cesta (bez vracení). Průchod bludištěm se dá popsat jako posloupnost sestavená z pohybů L (otoč se vlevo), R (otoč se vpravo) a W (jdi rovně). Úkolem této úlohy je zrekonstruovat tvar bludiště z dvou těchto posloupností – jedné při průchodem tam a druhé při průchodem zpátky (začínáme vždy vstupem do bludiště a končíme výstupem z něj). U bludiště na obrázku by se jednalo o posloupnost WRWWLWWLWWLWLWRRWRWWWRWWRWLW pro cestu tam a WWRRWLWLWWLWWLWWRWWRWWLW pro cestu zpátky. Řešení

Pouštění vajíček

Zadání: Máme k dispozici daný počet stejných vajec, ze kterých jich můžeme daný počet rozbít. Pokud hodíme vejce z některého patra budovy a ono se rozbije, tak máme jistotu, že se vejce rozbije i ze všech vyšších pater. Pokud se naopak nerozbije, tak se nerozbije ani po hození z kteréhokoliv nižšího patra. Naším úkolem je zjistit, kolik může mít budova pater, abychom s danými počty vajec zjistili nejvyšší patro, ze kterého se vejce ještě nerozbije. Řešení

Plán nákupu

Obchody
xyzbožícena
02cookies360
cereal110
40cereal90
milk150
-3-3milk200
cookies200
Seznam zboží
cookies
milk!
cereal

Zadání: V okolních obchodech potřebujeme nakoupit zadaný seznam zboží tak, abychom co nejvíc ušetřili. U každého obchodu známe ceny veškerého zboží, které prodává. Kromě toho je zadaná i cena benzínu, který potřebujeme, abychom obchody objeli. Aby situace nebyla tak jednoduchá, podléhá některé zboží rychlé zkáze – to znamená, že jakmile ho nakoupíme, musíme ho doma vyložit dřív, než navštívíme další obchod. Naším úkolem je zjistit, za jakou nejmenší cenu se dá zboží z našeho seznamu v okolních obchodech sehnat (neboli které obchody a v jakém pořadí musíme navštívit a co v nich musíme koupit). Řešení

Závěr

Dlužno podotknout, že algoritmy pro třetí a čtvrtou úlohu nestačí na běžných počítačích na řešení při velkých vstupních datech. Pokud by vás napadlo jejich vylepšení nebo přímo jiný algoritmus, podělte se o nápad v diskusi.

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

Diskuse

Juraj H.:

Ten plán nákupu je teda super vec ... sedím si teraz ráno pri PC v práci a riešim tú úlohu, kolegovia si posedávajú tiež a bezcieľne surfujú po nete a vtom prichádza šéf, letmo pozrie po monitoroch a pýta sa ma: "Ty čo zas kódiš!?" A zo mňa vyletelo: "...ale, riešim ako čo najviac ušetriť peniaze pri nákupoch..." (firma, kde pracujem sa nákupom zaoberá) A šéf nato hovorí: "Do paroma, ty si tu fakt jediný, čo tu pracuje..." :-DDD

Aké z toho plynie ponaučenie!? V práci sa treba vedieť hrať! :o)

Jakube, skvelý príspevok, ďakujem, ale už idem fakt pracovať. :)

ikona Jakub Vrána OpenID:

To jsem rád, že se tím alespoň někdo zabývá. Podle malého ohlasu jsem měl pocit, že jsem nestrefil cílovou skupinu. Mám totiž připravený celý seriál (zatím pětidílný), tohle je jenom jeho první díl.

pmg:

V tom teple se asi nikomu nechce moc přemýšlet. Mně se ty úlohy ale moc líbí, těším se na další!

Jan Kodera:

Jakube to jste mi neměl dělat. Hned jsem začal dumat nad poslední úlohou. Je to sice klasická úloha ve stylu obchodní cestující s tím že jsou tam jiné podmínky. Jelikož to vyžaduje exaktní řešení nelze použít nějakou heuristiku.

Já jsem to neprogramoval ale přistoupil bych k tomu,tak že bych ty permutace nejdříve vygeneroval a pak spočítal. Má to jednu výhodu a to že by se to dalo lehce paralelizovat. Jinak rychlejší to určitě nebude.

Pavel Kral:

Super clanek na super blogu...az na jeden detail zjistil jsem ze jsem lama vyresil jen jeden priklad:)

Jinak vsechna cest jakube..nebej tvyho blogu tak nevym co bych po ranu krome rootu cetl....

Juraj H.:

Ja som tiež taká lamka, poradil som zatiaľ len s dvoma (nákup a bludisko) - takéto teoretické hry majú čosi do seba. Určite lepšie ako čítať Blesk a pod. :-DDD

RATMex B:

Riešenie vajíčok:
Uvedené riešenie je v podstate úplne správne, má iba drobný nedostatok, že sa mnohé rovnaké hodnoty počítajú zbytočne veľakrát. Síce sa nerátajú vždy znova, ale pristupuje sa k nim, čo vyžaduje konštantý čas.
Stačí si iba zrátať, koľkokrát sa ktorá hodnota vo výsledku nasčíta a potom už ju iba daným číslom raz vynásobiť.
Je zrejmé, že pri vstupe D=B je výsledok (2^B-1). Pri zvyšovaní D sa tento člen vždy zachováva a nie je nikdy navýšený. Pri zvýšení B o 1 sa preto tento člen pripočíta práve raz, plus je celkový výsledok navýšený ešte o konštantu 1, ktorú môžeme s kľudným svedomím "spojiť" s ním a vznikne člen (2^(B-1)).
Z toho vyplýva, že celkový výsledok je polynóm (a(i)2^i, i < B) + 2^B - 1. Ostáva už iba vyčísliť členy a(i). Je zrejmé, že člen 2^(B-1) sa pripočítal iba zo všetkých výsledkov, kde  (D' < D, B' = B-1), a to práve raz, t.j. celkovo D-B-1 krát. Ďalej člen 2^(B-2) sa vyskytoval v každom výsledku pre (D' < D-1, B' = B-2) práve a v každom výsledku (D' < D, B' = B-1) toľkokrát, koľko existuje príslušných výsledkov pre (D'' < D', B'' = B'-1). Celkovo sa člen 2^(B-2) napočíta toľkokrát, koľko existuje dvojíc výsledkov (D', B') a k nim príslušných (D'', B''), čo jest (D-B-2 nad B-2), atď.

Pre prehľadnosť zapísu sa výskyt prvého spomínaného člena zapíše ako (D-B-1 nad 1) a člen mimo polynóm sa môže začleniť ako (D-B nad 0) a od výsledku sa odpočíta 1. Výsled ok pre D!=B je teda: http://img218.imageshack.us/img218/93/summs8.png

Fakt, že pri znalosti jedného kombinatorického čísla dokážeme lubovoľného suseda v Pascalovom trojuholníku vypočítať v konštantnom čase poskytuje možnosť, ako riešenie implementovať v čase O(b):
<?php
function floors($drops, $breaks)
{
    if ($drops == $breaks)
        return (1 << $breaks) - 1;

    $result = 0; $comb = 1; $factor = 1 << $breaks;
    for ($i = 0; $i <= $breaks; $i++)
    {
        $result += $comb * $factor;
        $comb = ($comb * ($drops - $breaks + $i)) / ($i + 1);
        $factor >>= 1;
    }

    return $result - 1;
}
?>

ikona Jakub Vrána OpenID:

Paráda, krásné řešení.

Shadow:

Vajíčka:
Doufám, že mne nebudete kamenovat, ale vždycky jsem byl tak trochu lenoch a snažím se nacházet jednoduchá řešení. Pokud máme algoritmus, který z posloupnosti výsledků hodů dokáže určit patro a to jednoznačně (tento algoritmus není těžké vytvořit, naopak, bylo by plýtvání mít algoritmus, který by nevyužil všechny hody), je tedy celkem možné mít "2 na n-tou" různých sekvencí výsledků jednoznačně určujících nějaké patro.  Protože pro přízemí, tj. nulté patro, potřebujeme také jednu sekvenci ("rozbilo-rozbilo-rozbilo-..."), je maximální počet pater roven (2 na n) - 1, což bychom napsali nějak takhle:

function floors($eggs){
    return (pow(2,$eggs) - 1);
}

Kdo nevěří, může otestovat, dává stejné výsledky a pravděpodobně by se i dalo nějak formálně dokázat že jde o totéž.. Nechť si to čtenáři doplní za domácí cvičení, já jdu radši řešit další úlohy :)

ikona Jakub Vrána OpenID:

Nepochopil jsi zadání. Stejné výsledky to nedává ani náhodou, bohužel sis to neotestoval ani sám. Nepřijde ti divné alespoň to, že tvoje funkce používá jen jednu proměnnou, i když se výsledky v závislosti na hodnotě druhé proměnné zásadně liší?

Shadow:

Ovšem že jsem to otestoval. Pouze mi nedošlo přesné zadání, takže jsem bral jen počet možných k rozbití a tam si to s (2 na N) - 1 odpovídá.

Na druhou stranu, pokud můžete nerozbité vejce sebrat a použít znovu (a v zadání není nic o tom že nemůžete - je tam jen že jich nesmíte rozbít určitý počet), stačí jedno co můžete rozbít (bez minimálně jednoho k rozbití úloha nemá smysl) a házíte ho pořád dokola vždy z N+1 patra dokud se nerozbije.

Vojťas:

Ad - Vždy zahni doleva:
implicitně by byla celá mřížka a při průchodu (W) bych ji vždy zrušil... (L, R je pouze točení namístě)

Pak pole snadno vygeneruju treba tabulku s odpovídajícím css (border-left, border-right, ...) - kazdý prvek pole $maze odpovídá jedné buňce tabulky...

Děkuju za skvělý blog, super články...

<?php
// ....

for ($i = 0; $i < strlen($path); $i++)
{
  if (!isset($maze[$y]))
    $maze[$y] = array();

  if (!isset($maze[$y][$x]))
    $maze[$y][$x] = array(true, true, true, true);

  switch ($path[$i])
  {
    case 'W':
      $maze[$y][$x][$o] = false;
      // move
      if ($o == 0)
        $y++;
      elseif ($o == 1)
        $x++;
      elseif ($o == 2)
        $y--;
      else
        $x--;
      // delete the same border for the neighbour block
      $maze[$y][$x][($o+2)%4] = false;
      break;
    case 'R':
      $o = ($o-1) % 4;
      break;
    case 'L':
      $o = ($o+1) % 4;
      break;
  }
}
?>

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.