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

10 Responses

  1. Agustin says:

    Yo estuve exactamente en tu misma situación en el problema 7, todo exactamente igual, incluso cogí unas cuantas implementaciones que hay por internet modificándoles el tema de los pesos y me pasaba lo mismo que a ti, validaban unas pruebas y otras no. Incluso un amigo (David) me propuso coger el código nativo de la función de Levenshtein de PHP, pasarlo a PHP quitándole la limitación de los 255 caracteres, pero ya era el sábado a la noche y no me veía con fuerzas después de todo el tiempo que le dediqué. En fin…

  2. Pere says:

    Me fascinan estos concursos… y ver la creatividad de los participantes aun más! lo malo es que nunca me entero de ninguno a tiempo!
    ¿Hay algun blog/web donde informen de estas movidas?

    P.D: Pusiste mal el link de la pregunta 8 :)!

  3. Ricard Clau says:

    Gràcies Pere! Fixed! 😀

    En mi caso me enteré en el trabajo, que alguien lo comentó!

    @Agustin veo que no soy el único loco que se planteó coger el código fuente de PHP :mrgreen:

  4. Hola de nuevo Ricard. Sigo divagando por internet revisando las soluciones de los demás para comparar 😳

    En el problema 5 veo que confías mucho en los recursos de tu máquina y en los casos de test de Tuenti. Hay una mejor manera que acepta cien vacas si hace falta 😉 Sin embargo, apegados a tu estrategia, la implementación ha sido bastante limpia. Me gusta.

    Sobre el 6 veo que esa ha sido la solución tomada por la mayoría, es mucho menos propensa a errores que la que elegí yo (que de hecho me equivoqué), aunque 6 veces más lenta. Hay una aún más rápida pero no he visto a nadie que la haya hecho. Es tediosa de sacar. A mi me dio pereza. Mucho lápiz y papel.

    En el problema 7 debo aplaudir a los casos de prueba (ya lo haré en mi blog) porque eran tales como para tener el algoritmo malo y que algunos casos dieran buenos. Excelente porque así nos despistó a muchos, quienes llegamos a dudar de nuestra lectura por la “dificultad del UTF-8” cuando en realidad el algoritmo lo teníamos malo. Bastante me tardé en revisar que tenía el peso de agregar en el de remover y listo.

    El 8 es un problema de libro en este tipo de competencias. En inglés se llama longest common substring que de hecho es el hermano menor de otro más general. Tú implementación es correcta pero hay una forma más rápida. Usas tres ciclos (se esconde uno en el strpos) y solo hacen falta dos. En el enlace está explicada y ya la comentaré yo cuando llegue a mi 8ª solución.

    Un saludo.

  5. Chefwww says:

    Como he dicho no me presenté al concurso pero tengo curiosidad en hacer alguno de estos ejemplos. Creo que voy a probar con el de la calculadora. Según mi punto de vista hay una solución más rápida (no se si 6 veces como comenta Carlos). Voy a probar a ver si me sale.

    • Hola Chefwww.

      En realidad me equivoqué al asegurar que la mía es seis veces más rápida. Me daba la impresión que sí pero en verdad es bastante similar en velocidad pues ese factor de 6 es una constante que en mi algoritmo está ocultado pero está.

      Lo que sí es cierto es que hay una solución más rápida (yo no la hice) que responde en tiempo constante, habiendo precalculado ciertas cosas. Te invito a pasarte por mi blog para que veas algunas de mis soluciones.

      No me llegan correos cuando alguien comenta entonces no me enteré sino hasta hoy que habías escrito.

      Saludos.

  1. 23/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 5 […]

  2. 23/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 5 […]

  3. 23/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 5 al 8 […]

  4. 23/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 5 al 8 […]

Leave a Reply

Your email address will not be published. Required fields are marked *