Google Code Jam [ http://code.google.com/codejam/ ] se přibližuje k semifinále, které probíhá přímo v pobočkách firmy Google. Zatím je možné si ho alespoň vyzkoušet [ http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxi5sBQM ]. Úlohy jsou tentokrát velice lehké, což je možná způsobeno tím, že účastníci budou úlohy poprvé řešit v neznámém prostředí a tedy ve větším stresu.
Starý kouzelník
Zadání: Kouzelník dá do klobouku W bílých a B černých koulí a nechá vás vždy vytáhnout dvojici koulí vámi zvolených barev. Pokud vytáhnete koule stejné barvy, vrátíte do klobouku bílou (pokud jste vytáhli dvě černé, dáte do klobouku bílou z rezervní hromady). Pokud vytáhnete dvě různé barvy, vrátíte do klobouku černou. Takto postupujete tak dlouho, až v klobouku zbude jediná koule. Kouzelník samozřejmě nevidí, jaké barvy si v jednotlivých tazích vybíráte. Jeho úkolem je uhodnout, jaká koule v klobouku zbude. Řešení [ #semifinale-a ]
Řešení: Vypadá to na pěknou rekurentní rovnici, že?
f(W, B): f(W-1, B-1) -> f(W-1, B) f(W-2, B) -> f(W-1, B) f(W, B-2) -> f(W+1, B-2)
Kde se tato rekurence zastaví? Pokud už v klobouku není žádná černá koule, jistě tam nakonec zbude bílá. Pokud je naopak v klobouku jediná černá koule, tak už se jí nezbavíme. No a každý další krok buď počet černých koulí zachová nebo sníží o dva, takže výsledný kód je triviální:
function magician($white, $black) {
return ($black % 2 ? "BLACK" : "WHITE");
}Čtvercová pole
Zadání: Máme zadáno N bodů ležících v rovině. Naším úkolem je uzavřít tyto body do K čtverců a vrátit minimální možnou délku hrany těchto čtverců. Strany čtverců musí být vodorovné a svislé, čtverce se mohou libovolně překrývat. Řešení [ #semifinale-b ]
Řešení: Výsledná délka hrany čtverce bude jistě odpovídat vodorovné nebo svislé vzdálenosti mezi některými dvěma body. Proto si nejprve zjistíme všechny tyto rozestupy a následně metodou půlení intervalů zjistíme, který je ten správný:
function square_fields($k, $points) {
sort($points);
$distances = array();
foreach ($points as $p1) {
foreach ($points as $p2) {
$distances[max(abs($p1[0] - $p2[0]), abs($p1[1] - $p2[1]))] = true;
}
}
$distances = array_keys($distances);
sort($distances);
$key_min = 1;
$key_max = count($distances) - 1;
while ($key_min < $key_max) {
$key = floor(($key_max + $key_min) / 2);
if (square_check($k, $distances[$key], $points)) {
$key_max = $key;
} else {
$key_min = $key + 1;
}
}
return $distances[$key_min];
}Funkce square_check zjistí, jestli lze s danou délkou hrany a daným počtem čtverců pokrýt zadané body. Funkce pracuje rekurzivně – zleva odebírá body a klade je na levou hranu čtverce. Všechny body, které do tohoto čtverce spadnou, se rekurzivnímu volání nepředají:
function square_check($k, $distance, $points) {
$left = reset($points);
foreach ($points as $bottom) {
if ($bottom[0] <= $left[0] + $distance && $bottom[1] <= $left[1] && $bottom[1] >= $left[1] - $distance) {
$points2 = $points;
foreach ($points2 as $key => $p) {
if ($p[0] <= $left[0] + $distance && $p[1] >= $bottom[1] && $p[1] <= $bottom[1] + $distance) {
unset($points2[$key]);
}
}
if (!$points2 || ($k > 1 && square_check($k - 1, $distance, $points2))) {
return true;
}
}
}
return false;
}Funkce by se dala ještě optimalizovat, ale není to potřeba.
Hamiltonovské kružnice
Zadání: Máme daný téměř kompletní neorientovaný graf s N vrcholy, ve kterém chybí jen několik hran (které jsou zadané). Naším úkolem je zjistit, kolik je v tomto grafu hamiltonovských kružnic (což je kružnice, která každý vrchol grafu navštíví právě jednou). Řešení [ #semifinale-c ]
Řešení: Průchod grafem začneme vždy ve vrcholu č. 1. Tento vrchol odebereme a dále budeme postupovat rekurzivně. Po vyčerpání všech vrcholů zjistíme, jestli se lze vrátit zpátky na start a tím cyklus uzavřít.
function cycles($points, $forbidden, $from = 1) {
unset($points[$from]);
if (!$points) {
return (isset($forbidden[$from][1]) ? 0 : 1);
}
$return = 0;
foreach ($points as $to => $val) {
if (!isset($forbidden[$from][$to])) {
$return = ($return + cycles($points, $forbidden, $to)) % (2*9901);
}
}
return $return;
}Výsledek má být vrácen modulo 9901 a kružnice mají být neorientované (algoritmus pracuje orientovaně, proto bude výsledek funkce ještě potřeba vydělit dvěma).