Tuenti Contest – Problemas 5 a 8

Dado el éxito de los 4 primeros problemas, sigo con lo que envié en los problemas del 5 al 8.

Challenge 5: The Milkman Problem

Podéis consultarlo aquí

<?php
#!/usr/bin/php
$problem = file('php://stdin');
foreach($problem as $i) {	
	list($numvacas, $camion, $pesovacas, $lechevacas) = explode(' ', trim($i));
	$pesosvacas = explode(',', $pesovacas);
	$prod = explode(',', $lechevacas);
 
	echo getBestCombi($numvacas, $camion, $pesosvacas, $prod) . PHP_EOL;
}
 
function getBestCombi($numvacas, $camion, $pesosvacas, $prod) {
	$maxprod = 0;
	$limit = pow(2, $numvacas);
	for($i = 1; $i < $limit; $i++) {
		$mask = str_pad(decbin($i), $numvacas, '0');
		$test = calculaMask($mask, $camion, $pesosvacas, $prod);
		if($test > $maxprod) $maxprod = $test;
	}	
	return $maxprod;
}
 
function calculaMask($mask, $camion, $pesosvacas, $prod) {
	$maskarr = str_split($mask);	
	$total = count($maskarr);
	for($i = 0; $i < $total; $i++) {
		if($maskarr[$i] == '0') {
			unset($pesosvacas[$i]);
			unset($prod[$i]);
		}				
	}
	if(array_sum($pesosvacas) > $camion) return 0;
	else return array_sum($prod);
}
?>

Para este problema, la verdad es que no se me ocurrió otra manera que testear todos los casos posibles buscando el mejor. No sé si hay algún algoritmo que optimice estas cosas pero la verdad es que si pensamos en todas las combinaciones de vacas, camiones y leches se me antoja complicado. En cualquier caso, soy bastante malo en algoritmos y seguro que hay soluciones más elegantes.

En mi caso, planteaba el listado de vacas como una mascara binaria de 0s y 1s y probaba los casos desde 1 hasta 2^$numvacas. Y me quedaba con la mejor combinación de producción de leche siempre que no se pasara del peso máximo del camión.

Supongo que si me hubieran enviado un test super grande hubiera ido muchísimo más lento.

Challenge 6: The clock

Podéis consultarlo aquí

#!/usr/bin/php
<?php
$problem = file('php://stdin');
$ledsconfig = array(
   0 => 6,	
   1 => 2,	
   2 => 5,
   3 => 5,
   4 => 4,
   5 => 5,	
   6 => 6,	
   7 => 3,
   8 => 7,
   9 => 6,
);
 
foreach($problem as $i) {	
	$i = trim($i);
	$leds = 0;
	for($j=0; $j <= $i; $j++) {
		$mask = gmdate('His', $j);
		$tmpleds = 0;
		$maskarr = str_split($mask);
 
		for($k = 0; $k < 6; $k++) {
			$tmpleds += $ledsconfig[(int)$maskarr[$k]];
		}
		$leds += $tmpleds;
	}
	echo $leds . PHP_EOL;
}
?>

Probablemente uno de los problemas más sencillos de la prueba. En este caso, monto un array de configuración con el número de leds de cada número y para generar los valores que aparecen en el reloj, uso la función gmdate(‘His’, $contador), con eso vamos viendo la hora desde 00:00:00 hasta donde necesitemos. Quizás no muy limpio pero efectivo 😉

Challenge 7: The Tile Game

Podéis consultarlo aquí

#!/usr/bin/php
<?php
$lines = file('php://stdin');
function phplev($s1, $s2, $costadd, $costchange, $costremove) {
	$l1 = strlen($s1);    
    	$l2 = strlen($s2);    
    	$dis = range(0,$l2);  
 
	for ($i2 = 0; $i2 <= $l2; $i2++) {
		$dis[$i2] = $i2 * $costadd;
	}
 
	for ($i1 = 0; $i1 < $l1 ; $i1++) {
		$dis_new[0] = $dis[0] + $costremove;
		for ($i2 = 0; $i2 < $l2; $i2++) {
			$c0 = $dis[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $costchange);
			$c1 = $dis[$i2 + 1] + $costremove;
			if ($c1 < $c0) {
				$c0 = $c1;
			}
			$c2 = $dis_new[$i2] + $costadd;
			if ($c2 < $c0) {
				$c0 = $c2;
			}
			$dis_new[$i2 + 1] = $c0;
		}
		$tmp = $dis;
		$dis = $dis_new;
		$dis_new = $tmp;
	}		
	return $dis[$l2];
}
 
foreach($lines as $line) {
	$line = trim($line);
	list($str1, $str2, $costs) = explode(' ', $line);
	list($costadd, $costremove, $costchange) = explode(',', $costs);
 
	echo phplev($str1, $str2, $costadd, $costchange, $costremove) . PHP_EOL;
}
?>

Yo llegué algo tarde a este problema y no me pasó como a otros participantes que tenían problemas con la secuencia de caracteres. El caso es que este problema es un caso claro de la función levenshtein que nos mide la distancia entre dos strings.

PHP trae la función levenshtein hecha, y con los pesos!, y en aquel momento pensé… otro problema al saco PEROOOO la función de PHP solamente soporta hasta 255 carácteres y los tests eran de longitud 300.

Como me veía incapaz de entender la teoría detrás del algoritmo y implementar algo decente empecé a buscar en la wikipedia. Encontré muchas implementaciones pero ninguna de ellas contemplaba los pesos. Empecé a alterarlas contemplando los pesos pero no tenía TEST OK en todo.

Y entonces se me ocurrió algo espectacular. Cogí el código fuente de PHP, en el cual existe el archivo levenshtein.c donde está implementado todo con el return -1 si nos pasamos de 255. Cogí ese código, lo traduje a PHP nativo (como podéis ver) y todo TEST OK a la primera y en velocidades muy dignas. Es un poco rizar el rizo coger el código fuente de algo y quitarle las limitaciones para re-implementarlo pero funcionó.

Este problema fue un gran stopper para mucha gente, la verdad. Había que conocer el tema de levenshtein… en otros lenguajes también hay límites como en PHP o funciona tal cual?

Challenge 8: The Biologist Problem

Podéis consultarlo aquí

#!/usr/bin/php
<?php
$lines = file('php://stdin');
 
foreach($lines as $line) {
	$strs = explode(' ', trim($line));
	if(strlen($strs[0]) < strlen($strs[1])) {
		$short = $strs[0];
		$long = $strs[1];
	} else {
		$short = $strs[1];
		$long = $strs[0];
	}
	$len = strlen($short);
	for($i = $len; $i >= 0; $i--) {
		for($j = $len; $j >= $i; $j--) {
			if(strpos($long, substr($short, $j-$i, $i)) !== false) {
				break 2;
			}
		}
	}
	echo substr($short, $j-$i, $i). PHP_EOL;
}
?>

Para este problema estuve pensando que la forma más fácil de resolverlo era coger el string más corto de los dos y ir probando de quitarle caracteres por delante y por detrás, probando todas las combinaciones posibles de esto (de ahí el doble bucle de $i y $j). Cuando se cumplía el strpos del string corto recortado, estábamos en el caso más largo de repetición de ADN, y en ese momento hacía el break 2 para salir de los dos bucles con el resultado correcto.

Espero que os guste y sigáis tan participativos!

You may also like...