Google Code Jam 2008 - cvičení
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Google Code Jam 2008 - cvičeníGoogle Code Jam 2008 - cvičení

 

Google Code Jam 2008 - cvičení

Google       Google       10. 8. 2008       19 610×

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.

Reklama
Reklama

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řazný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í

Řešení je jednoduché – nejprve zjistíme hodnotu zapsaného čísla a potom toto číslo převedeme do druhé číselné soustavy:

function alien_numbers($number, $input, $output) {
	$value = 0;
	for ($i=0; $i < strlen($number); $i++) {
		$value = strlen($input) * $value + strpos($input, $number{$i});
	}
	$return = "";
	while ($value) {
		$return = $output{$value % strlen($output)} . $return;
		$value = floor($value / strlen($output));
	}
	return $return;
}

Vždy zahni doleva

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í

řešení budeme udržovat proměnné $x, $y a $o zachycující informaci o aktuální pozici a orientaci ($o = 0 bude jih, dále proti směru hodinových ručiček). V poli $maze budeme udržovat informaci o stěnách v jednotlivých místnostech – místnost bez stěn bude uložena jako prázdné pole, místnost se stěnou na jihu bude mít prvek v klíči 0 a tak dále (podle orientace).

function turn_left($forward, $backward) {
	$maze = array(); // walls: $y => $x => $o => false
	$y = 0; // increases to south
	$x = 0; // increases to east
	$o = 0; // 0 south, 1 east, 2 north, 3 west
	turn_left_move($forward, $y, $x, $o, $maze);
	$o = ($o + 2) % 4;
	turn_left_move($backward, $y, $x, $o, $maze);
	return $maze;
}

Funkce turn_left_move projde celou posloupnost, provede jednotlivé pohyby a označí známé stěny:

function turn_left_move($path, &$y, &$x, &$o, &$maze) {
	for ($i=0; $i < strlen($path); $i++) {
		$m = $path{$i};
		if ($m == "W") {
			if ($i && $path{$i-1} != "L") {
				$maze[$y][$x][($o + 1) % 4] = false;
			}
			switch ($o) {
				case 0: $y++; break;
				case 1: $x++; break;
				case 2: $y--; break;
				case 3: $x--; break;
			}
			if ($i < strlen($path) - 1 && !isset($maze[$y][$x])) {
				$maze[$y][$x] = array();
			}
		} elseif ($m == "L") {
			$o = ($o + 1) % 4;
		} elseif ($m == "R") {
			$maze[$y][$x][($o + 1) % 4] = false;
			$maze[$y][$x][$o] = false;
			$o = ($o + 3) % 4;
		}
	}
}

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í

Řešení: Vymyslet postup, jak vejce házet, abychom pokryli co nejvíc pater, není úplně jednoduché, ale pro řešení úlohy to vlastně ani nepotřebujeme. Stačí si uvědomit, že řešení úlohy se skrývá v jednoduché rekurentní rovnici f(D, B) = 1 + f(D-1, B-1) + f(D-1, B), kde D je celkový počet vajec a B počet vajec, které můžeme rozbít. Jednička je patro, které jsme zrovna vyzkoušeli, první rekurze pokrývá případ, kdy se vejce rozbije, druhá potom případ, kdy se nerozbije. Výchozím bodem této rekurence je f(D, 1) = D, což znamená, že když už můžeme rozbít jenom jedno vejce, tak musíme jít zespodu a jistě zvládneme vyzkoušet tolik pater, kolik máme pokusů.

function floors($drops, $breaks) {
	static $floors = array();
	if ($breaks == 1) {
		return $drops;
	}
	if (!isset($floors[$drops][$breaks])) {
		$floors[$drops][$breaks] = 1 + floors($drops-1, $breaks-1) + floors($drops-1, min($drops-1, $breaks));
	}
	return $floors[$drops][$breaks];
}

Abychom nepočítali výsledek funkce pořád dokola, tak si ho uložíme do keše (odborně se tomu říká dynamické programování). Samozřejmě musíme brát v potaz i to, že vajec nemůžeme rozbít víc, než kolik jich máme (to řeší funkce min).

Plán nákupu

xyzbožícena
02cookies360
02cereal110
40cereal90
40milk150
-3-3milk200
-3-3cookies200
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í

Řešení: Myšlenka řešení této úlohy je jednoduchá, technické zpracování poměrně náročné. Jde o to vyzkoušet všechny (i neúplné) permutace návštěvy obchodů a vybrat tu s nejnižším součtem cen zboží a benzínu. Kromě toho je potřeba brát v potaz rychle se kazící zboží, což vyřešíme vyzkoušením návratu se všemi kombinacemi zboží, které daný obchod prodává.

/** Výpočet minimálních nákladů nákupu zboží
* @param int $gas_price cena benzínu
* @param array $stores pole obchodů array("x" => $x, "y" => $y, "prices" => array($item => $price))
* @param array $items pole zboží $item => $perishable
* @return float minimální náklady, za které se dá zboží koupit
*/
function shopping_plan($gas_price, $stores, $items, $x = 0, $y = 0, $prices = array(), $cost = 0) {
	$min_cost = null;
	if (count($prices) == count($items)) {
		$min_cost = $cost + array_sum($prices) + $gas_price * sqrt($x * $x + $y * $y);
	}
	
	foreach ($stores as $i => $store) {
		$prices2 = $prices;
		$take_backs = array();
		$visit = false;
		foreach ($store["prices"] as $item => $price) {
			if ($items[$item]) { // perishable
				foreach ($take_backs as $take_back) {
					$take_backs[] = array_merge($take_back, array($item));
				}
				$take_backs[] = array($item);
			} elseif (isset($items[$item]) && (!isset($prices2[$item]) || $prices2[$item] > $price)) {
				$prices2[$item] = $price;
				$visit = true;
			}
		}
		
		if ($take_backs || $visit) {
			$gas_cost = $gas_price * sqrt(($x - $store["x"]) * ($x - $store["x"]) + ($y - $store["y"]) * ($y - $store["y"]));
			$stores2 = $stores;
			unset($stores2[$i]);
		}
		
		foreach ($take_backs as $take_back) {
			$cost2 = $cost + $gas_cost + $gas_price * sqrt($store["x"] * $store["x"] + $store["y"] * $store["y"]);
			$items2 = $items;
			foreach ($take_back as $item2) {
				unset($items2[$item2]);
				$cost2 += $store["prices"][$item2];
			}
			min_isset($min_cost, shopping_plan($gas_price, $stores2, $items2, 0, 0, $prices2, $cost2));
		}
		
		if ($visit) {
			min_isset($min_cost, shopping_plan($gas_price, $stores2, $items, $store["x"], $store["y"], $prices2, $cost + $gas_cost));
		}
	}
	
	return $min_cost;
}

Kód používá hned několik důležitých obratů:

  • Hned na začátku se kontroluje, jestli už jsme sehnali všechno zboží z našeho seznamu – pokud ano, tak si zapamatujeme aktuální cenu této (neúplné) permutace.
  • Kombinace rychle se kazícího zboží se ukládají do pole $take_backs tak, že se pro každou položku toto pole projde a přidají se již existující kombinace spolu s novou položkou.
  • Je aplikováno základní ořezávání – pokud v obchodě nemají nic levnějšího, než co už máme z dosud navštívených obchodů, tak v permutaci nepokračujeme. Dále by bylo vhodné udělat i zpětné ořezávání – pokud bychom zjistili, že jsme některý obchod navštívili zbytečně (protože v dalších obchodech je zboží levnější), nemuseli bychom v permutaci také pokračovat.

Pro uložení minimální ceny se používá funkce min_isset, která do prvního parametru uloží minimum z předaných parametrů s tím, že hodnota null se chápe jako nekonečno:

/** Minimální hodnota se zohledněním neinicializovaných proměnných
* @param mixed &$min proměnná, do které se nastaví minimální hodnota
* @param mixed $value porovnávaná hodnota
* @return null nastaví proměnnou $min
* @copyright Jakub Vrána, http://php.vrana.cz
*/
function min_isset(&$min, $value) {
	if (isset($value) && (!isset($min) || $min > $value)) {
		$min = $value;
	}
}

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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Jakub VránaAutorův profesní život se točí převážně kolem PHP. Živí se programováním v tomto jazyce, podílí se na oficiální dokumentaci, vyučuje ho na MFF UK a vede odborná školení. Poznámky si zapisuje na weblog PHP triky.
Web    

Nové články

Reklama
Reklama
Obrázek ke článku Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

Obrázek ke článku České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace (CRA) pořádají druhý ročník CRA IoT Hackathonů. Zájemci z řad vývojářů a fanoušků moderních technologií mohou změřit své síly a během jediného dne sestrojit co nejzajímavější funkční prototyp zařízení, které bude komunikovat prostřednictvím sítě LoRa. CRA IoT Hackathony se letos uskuteční ve dvou fázích, na jaře a na podzim, v různých městech České republiky. Jarní běh se odstartuje 31. března v Brně a 7. dubna v Praze.

Obrázek ke článku Cloud computing je využíván stále intenzivněji

Cloud computing je využíván stále intenzivněji

Využívání cloud computingu nabývá na intenzitě. Jen v letošním roce vzroste podle analytiků trh se službami veřejného cloudu o 18 %, přičemž o téměř 37 % vzrostou služby typu IaaS. Růst o více než pětinu pak čeká služby poskytování softwaru formou služby, tedy SaaS. Aktuálním trendům v oblasti využívání cloudu se bude věnovat konference Cloud computing v praxi, která se koná 23. března. 2017 v pražském Kongresovém centru Vavruška na Karlově náměstí 5.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý