Tuenti Contest – Problemas 9 a 12

Y seguimos para Bingo, pasando el ecuador del Tuenti Contest 🙂

Challenge 9: The Christmas lights

Podéis consultarlo aquí

#!/usr/bin/php
<?php
 
$lines = file('php://stdin');
 
$numcases = $lines[0];
for($i = 0; $i < $numcases; $i++) {
    $cases[] = array($lines[2*$i + 1],$lines[2*$i+2]);
}
 
foreach($cases as $case) {
    $lights = $case[0];
    $time = $case[1];
    $time = $time % $lights;
 
    if($time == 0) {
        echo 'All lights are off :('. PHP_EOL;
        continue;
    }    
    $out = '';
    for($i = (int)($time % 2 == 0); $i < $time; $i= $i+2) {
       $out .= $i .' ';
    }
    echo trim($out) . PHP_EOL;    
}
?>

Para este problema, básicamente lo que hago es considerar que el tiempo vuelve a ser 0 cuando se ha recorrido todas las luces, entonces el número de luces es desde 0 o 1 (de ahí ese hasta ese bucle que empieza en $i = (int)($time % 2 == 0)) y va subiendo de 2 en 2. Caso especial el 0 con el mensaje de ‘All lights are off’. Bastante sencillo una vez tienes la idea feliz 🙂

Challenge 10: Key Combos

Podéis consultarlo aquí

#!/usr/bin/php
<?php
 
$lines = file('php://stdin');
$lines = array_map('trim', $lines);
 
$numcombis = $lines[0];
for($i = 0; $i < $numcombis; $i++) {
    $comb = explode(' ', $lines[2*$i + 1]);
    sort($comb);
    $combis[$lines[2*$i+2]] = implode(' ', $comb);
}
 
$numtests = $lines[2*$numcombis + 1];
 
for($i = 2*$numcombis + 2; $i < count($lines); $i++) {
    $tests[] = $lines[$i];
}
 
foreach($tests as $test) {
    $seq = explode(' ', $test);
    sort($seq);
    echo array_search(implode(' ', $seq), $combis) . PHP_EOL;
}
?>

Otro de los problemas facilitos. Lo único a tener en cuenta es hacer un sort de la secuencia de teclas ya que podían venir desordenadas y significar lo mismo. La función array_search de PHP nos facilita un montón el trabajo :D.

Challenge 11: Gas stations

Podéis consultarlo aquí

#!/usr/bin/php
<?php
$lines = file('php://stdin');
$lines = array_map('trim', $lines);
 
$testcases = $lines[0];
for($i = 0; $i < $testcases; $i++) {
	$tests[] = array(
		'max' => $lines[4*$i + 1],
		'total' => $lines[4*$i + 2],
		'stations' => $lines[4*$i + 3],
		'dists' => $lines[4*$i + 4],
		);
}
 
foreach($tests as $test) {
	echo getStops($test) . PHP_EOL;
}
 
function getStops($test) {
	$max = $test['max'];
	$total = $test['total'];
	$stations = $test['stations'];
	$dists = explode(' ', $test['dists']);
 
	if($max >= $total) return 'No stops';
	$out = '';
	$distalready = 0;
	for($i = 0; $i < $stations - 1; $i++) {
		if($dists[$i + 1] - $distalready > $max) {
			$out .= $dists[$i]. ' ';
			$distalready = $dists[$i];
		}
	}
	return trim($out);
}
?>

Este problema no sé si lo tengo bien. Los casos de test me daban bien pero tengo mis dudas si el algoritmo cubre todos los casos posibles. Básicamente lo que hacía era ir mirando cuántas gasolineras me podía saltar en función de la capacidad del depósito pero no sé si hay que hacerlo en plan grafo para ver el mínimo número de paradas. Seguramente así sea y mi solución no sea la correcta!

Challenge 12: The Stargate Problem

Podéis consultarlo aquí

#!/usr/bin/php
<?php
 
function BELLMAN_FORD($edges, $edgecount, $nodecount, $source)
{
    // Initialize distances
    $distances = array();
 
    // This is the INITIALIZE-SINGLE-SOURCE function.
    for($i = 0; $i < $nodecount; ++$i)
        $distances[$i] = INF; // All distances should be set to INFINITY
 
    $distances[$source] = 0; // The source distance should be set to 0.
 
    // Do what we are suppose to do, This is the BELLMAN-FORD function
    for($i = 0; $i < $nodecount; ++$i)
    {
        $somethingChanged = false; // If nothing has changed after one pass, it will not change after two.
        for($j = 0; $j < $edgecount; ++$j)
        {
            if($distances[$edges[$j][0]] != INF) // Check so we are not doing something stupid
            {
                $newDist = $distances[$edges[$j][0]] + $edges[$j][2]; // Just create a temporary variable containing the calculated distance
                if($newDist < $distances[$edges[$j][1]]) // If the new distance is shorter than the old one, we've found a new shortest path
                {
                    $distances[$edges[$j][1]] = $newDist;
                    $somethingChanged = true; // SOMETHING CHANGED, YEY!
                }
            }
        }
        // If $somethingChanged == FALSE, then nothing has changed and we can go on with the next step.
        if(!$somethingChanged) break;
    }
 
    // Check the graph for negative weight cycles
    for($i = 0; $i < $edgecount; ++$i)
    {
        if($distances[$edges[$i][1]] > $distances[$edges[$i][0]] + $edges[$i][2])
        {
            //echo "Negative edge weight cycle detected!";
            return NULL;
        }
    }
 
    // Print out the shortest distance
    for($i = 0; $i < $nodecount; ++$i)
    {
        // echo "Shortest distance between nodes " . $source . " and " . $i . " is " . $distances[$i] . "<br/>";
    }
 
    return $distances;
}
 
 
$lines = file('php://stdin');
 
$lines = array_map('trim', $lines);
 
foreach($lines as $numline => $line) {
    $data = preg_split('/\s/', $line);
    $numplanets = array_shift($data);
    $earth = array_shift($data); 
    $atlantis = array_shift($data);
    $neighbors = array();
    foreach($data as $coord) {
        $points = explode(',', $coord);
        if(count($points) != 3) { continue;}
 
        $neighbors[] = $points; 
    }
 
 
    $paths = BELLMAN_FORD($neighbors, count($neighbors), $numplanets, $earth);
 
    if(!isset($paths[$atlantis]) || $paths[$atlantis] === INF) echo 'BAZINGA'. PHP_EOL;
    else echo (25000 + $paths[$atlantis]) . PHP_EOL;
 
}
?>

Y para el final del cuarteto, uno de los problemas que peor me lo hizo pasar. Estuve intentando resolverlo con el algoritmo de Dijkstra pero aparentemente los valores negativos hacen estropear este conocido algoritmo. Y en ese momento es cuando mi nuevo CTO de mi nueva empresa Ulabox, Sergi de Pablos, me comentó que existía el algoritmo de Bellman-Ford para este tipo de problemas y que contemplaba correctamente los valores negativos y los ciclos extraños que pueden provocar un BAZINGA como era el primer caso de TEST. El código de BELLMAN_FORD fue fusilado vilmente de Internet, vi que funcionaba y no me planteé nada más.

Debo reconocer que conforme avanzaba el concurso y el final del plazo se acercaba fui más sucio en mis soluciones, pero el tiempo apremiaba y mi vida social requiere ser cuidada también ;).

Y en mi caso solamente llegué al 16 así que el próximo post será el último, estoy esperando a que la gente publique las soluciones a los últimos problemas para aplaudirles estrunduosamente 🙂

You may also like...

6 Responses

  1. Hola Ricard.
    Vuelve tu comentarista fiel para estos artículos.

    En el 9 yo asumí que el tiempo nunca volvía a ser cero. El problema menciona que las luces empiezan desenchufadas y apagadas y luego comienza el encendido intercalado y no me dio a entender que volvieran a apagarse todas. Capaz e interpreté mal. De todas formas no hay mucho que decir en este problema.

    En el 10 igual, no hay mucho que decir. Curiosa la forma que juegas con el índice del arreglo para leer la línea de las teclas y la de la aplicación.

    ¿Verdad que el 11 es demasiado sospechoso? Yo también pensé que había alguna complejidad oculta pero, si la hay, aún no la he visto. A manejar hasta que no demos más y entonces llenamos el tanque. Justo como el tuyo, aunque veo que te falta un caso. ¿Qué haces si la parada está luego de la última estación y debes parar en la última?

    Sobre el 12, nada que decir. Es así. Dijkstra no admite aristas negativas (esa era el detalle que había que saber) y había que cambiar a Bellman-Ford o Floyd-Warshall. Yo elegí el último, ya te enterarás 🙂

  2. Ricard Clau says:

    Hola de nuevo Carlos 🙂

    Espero que pasada la fiebre del Contest me sigas visitando de vez en cuando 😉

    El 11 no lo tengo del todo claro que esté bien así, pero juraría que el caso que comentas de la última gasolinera lo tengo contemplado con mirar la gasolinera $i+1 y su distancia acumulada, no? De hecho creo recordar que alguno de los tests básicos ya contemplaba el caso.

    El resto, es lo que dices, no tienen mucho más. Desconocía también el algoritmo de Floyd-Warshall, otra cosa más aprendida.

    Saludos y esperando tus soluciones mucho más académicas que las mías (ya se sabe PHP vs Java/C++) 😆

  1. 24/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 9 al 12 […]

  2. 24/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 9 al 12 […]

  3. 24/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 9 al 12 […]

  4. 25/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 9 al 12 […]