Google Code Jam 2008 - cvič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 ř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;
		}
	}
}

Ř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).

Ř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;
	}
}