Google Code Jam 2008 - cvičení
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
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 154×

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

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

Reklama
Reklama
Obrázek ke článku ICT PRO školení zaměřené nejenom na ICT

ICT PRO školení zaměřené nejenom na ICT

Dovolte, abychom se představili. Jsme zaměstnanci společnosti ICT Pro, profesionálové v oblasti poskytování komplexních ICT služeb. Neboli služeb spojených s informačními a komunikačními technologiemi, které dnes - ve 21. století - tvoří  nedílnou součást běžného provozu všech moderních firem.

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 © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý