× Aktuálně z oboru

SHIELD Experience Upgrade 7 – méně hledání a více zábavy [ clanek/2018052902-shield-experience-upgrade-7-mene-hledani-a-vice-zabavy/ ]
Celá zprávička [ clanek/2018052902-shield-experience-upgrade-7-mene-hledani-a-vice-zabavy/ ]

Google Code Jam 2008 - cvičení

[ http://programujte.com/profil/13839-jakub-vrana/ ]Google [ ?rel=author ]       [ http://programujte.com/profil/118-zdenek-lehocky/ ]Google [ ?rel=author ]       10. 8. 2008       24 092×

V soutěži Google Code Jam [ http://code.google.com/codejam/ ] 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 [ http://code.google.com/codejam/contest ], 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í [ #cviceni-a ]

Ř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í [ #cviceni-b ]

ř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í [ #cviceni-c ]

Ř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í [ #cviceni-d ]

Ř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 [ http://php.vrana.cz/permutace.php ] 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.


Článek stažen z webu Programujte.com [ http://programujte.com/clanek/2008080700-google-code-jam-2008-cviceni/ ].