Tuenti Contest – Problemas 13 a 15 y opinión final

Tras este fin de semana algo más largo de la cuenta debido a la verbena de San Juan termino con esta serie de artículos sobre el Tuenti Contest con las 3 últimas soluciones que envié ya que no conseguí que me funcionaran los casos de test del problema 16. También al final del artículo voy a dar mi opinión sobre el concurso en sí.

Vamos a ello!

Challenge 13: The Other clock

Podéis consultarlo aquí

#!/usr/bin/php
<?php
$ledsconfig = array(
   '0-1' => 0,	
   '1-2' => 4,	
   '2-3' => 1,
   '3-4' => 1,
   '4-5' => 2,
   '5-6' => 1,	
   '6-7' => 1,	
   '7-8' => 4,
   '8-9' => 0,
   '9-0' => 1,
   '5-0' => 2, // 59m or 59s -> 00 
   '2-0' => 2, // 23h -> 00
);
 
$problem = file('php://stdin');
$problem = array_map('trim', $problem);
 
foreach($problem as $i) {	
        $leds = 36;
        $antmask = array_fill(0,6,'0');
	for($j=1; $j <= $i; $j++) {
		$mask = gmdate('His', $j);
		$maskarr = str_split($mask);
 
                $tmpleds = 0;
		for($k = 0; $k < 6; $k++) {
                    if($antmask[$k] != $maskarr[$k]) {
                        $tmpleds += $ledsconfig[$antmask[$k].'-'.$maskarr[$k]];
                    }    
		}
		$antmask = $maskarr;
                $leds += $tmpleds;
	}
	echo $leds . PHP_EOL;
}
?>

De nuevo otro problema de relojes, muy similar al anterior pero en este caso había que acumular el incremento de leds. Es decir, cuantos leds se encendían respecto al segundo anterior. Es una pregunta un poco rara y me extrañó ver lo parecido que era al caso anterior, solamente cambiaba el hecho de que los segundos y minutos pasan de 59 a 00 (y hay un caso de cambio de 5 a 0) y las horas de 23 a 00 (y hay también un caso de 2 a 0).

Para todo ello me aprovecho del funcionamiento de los arrays de PHP, tratados como un hashmap con el actual-anterior.
Creo que queda bastante claro en el código 🙂

Challenge 14: Colors are beautiful

Podéis consultarlo aquí

#!/usr/bin/php
<?php
class BMP
{
	public static function imagebmp(&$img, $filename = false)
	{
		$wid = imagesx($img);
		$hei = imagesy($img);
		$wid_pad = str_pad('', $wid % 4, "\0");
 
		$size = 54 + ($wid + $wid_pad) * $hei * 3; //fixed
 
		//prepare & save header
		$header['identifier']		= 'BM';
		$header['file_size']		= self::dword($size);
		$header['reserved']			= self::dword(0);
		$header['bitmap_data']		= self::dword(54);
		$header['header_size']		= self::dword(40);
		$header['width']			= self::dword($wid);
		$header['height']			= self::dword($hei);
		$header['planes']			= self::word(1);
		$header['bits_per_pixel']	= self::word(24);
		$header['compression']		= self::dword(0);
		$header['data_size']		= self::dword(0);
		$header['h_resolution']		= self::dword(0);
		$header['v_resolution']		= self::dword(0);
		$header['colors']			= self::dword(0);
		$header['important_colors']	= self::dword(0);
 
		if ($filename)
		{
		    $f = fopen($filename, "wb");
		    foreach ($header AS $h)
		    {
		    	fwrite($f, $h);
		    }
 
			//save pixels
			for ($y=$hei-1; $y>=0; $y--)
			{
				for ($x=0; $x<$wid; $x++)
				{
					$rgb = imagecolorat($img, $x, $y);
					fwrite($f, byte3($rgb));
				}
				fwrite($f, $wid_pad);
			}
			fclose($f);
		}
		else
		{
		    foreach ($header AS $h)
		    {
		    	echo $h;
		    }
 
			//save pixels
			for ($y=$hei-1; $y>=0; $y--)
			{
				for ($x=0; $x<$wid; $x++)
				{
					$rgb = imagecolorat($img, $x, $y);
					echo self::byte3($rgb);
				}
				echo $wid_pad;
			}
		}	
	}
 
	public static function imagecreatefrombmp($filename)
	{
		$f = fopen($filename, "rb");
 
		//read header    
	    $header = fread($f, 54);
	    $header = unpack(	'c2identifier/Vfile_size/Vreserved/Vbitmap_data/Vheader_size/' .
							'Vwidth/Vheight/vplanes/vbits_per_pixel/Vcompression/Vdata_size/'.
							'Vh_resolution/Vv_resolution/Vcolors/Vimportant_colors', $header);
 
	    if ($header['identifier1'] != 66 or $header['identifier2'] != 77)
	    {
	    	die('Not a valid bmp file');
	    }
 
	    if (!in_array($header['bits_per_pixel'], array(24, 32, 8, 4, 1)))
	    {
	    	die('Only 1, 4, 8, 24 and 32 bit BMP images are supported');
	    }
 
		$bps = $header['bits_per_pixel']; //bits per pixel 
	    $wid2 = ceil(($bps/8 * $header['width']) / 4) * 4;
		$colors = pow(2, $bps);
 
	    $wid = $header['width'];
	    $hei = $header['height'];
 
	    $img = imagecreatetruecolor($header['width'], $header['height']);
 
		//read palette
		if ($bps < 9)
		{
			for ($i=0; $i<$colors; $i++)
			{
				$palette[] = self::undword(fread($f, 4));
			}
		}
		else
		{
			if ($bps == 32)
			{
				imagealphablending($img, false);
				imagesavealpha($img, true);			
			}
			$palette = array();
		}	
 
		//read pixels    
	    for ($y=$hei-1; $y>=0; $y--)
	    {
			$row = fread($f, $wid2);		
			$pixels = self::str_split2($row, $bps, $palette);
	    	for ($x=0; $x<$wid; $x++)
	    	{
	    		self::makepixel($img, $x, $y, $pixels[$x], $bps);
	    	}
	    }
		fclose($f);    	    
 
		return $img;
	}
 
	private static function str_split2($row, $bps, $palette)
	{
		switch ($bps)
		{
			case 32:
			case 24:	return str_split($row, $bps/8);
			case  8:	$out = array();
						$count = strlen($row);				
						for ($i=0; $i<$count; $i++)
						{					
							$out[] = $palette[	ord($row[$i])		];
						}				
						return $out;		
			case  4:	$out = array();
						$count = strlen($row);				
						for ($i=0; $i<$count; $i++)
						{
							$roww = ord($row[$i]);						
							$out[] = $palette[	($roww & 240) >> 4	];
							$out[] = $palette[	($roww & 15) 		];
						}				
						return $out;
			case  1:	$out = array();
						$count = strlen($row);				
						for ($i=0; $i<$count; $i++)
						{
							$roww = ord($row[$i]);						
							$out[] = $palette[	($roww & 128) >> 7	];
							$out[] = $palette[	($roww & 64) >> 6	];
							$out[] = $palette[	($roww & 32) >> 5	];
							$out[] = $palette[	($roww & 16) >> 4	];
							$out[] = $palette[	($roww & 8) >> 3	];
							$out[] = $palette[	($roww & 4) >> 2	];
							$out[] = $palette[	($roww & 2) >> 1	];
							$out[] = $palette[	($roww & 1)			];
						}				
						return $out;					
		}
	}
 
	private static function makepixel($img, $x, $y, $str, $bps)
	{
		switch ($bps)
		{
			case 32 :	$a = ord($str[0]);
						$b = ord($str[1]);
						$c = ord($str[2]);
						$d = 256 - ord($str[3]); //TODO: gives imperfect results
						$pixel = $d*256*256*256 + $c*256*256 + $b*256 + $a;
						imagesetpixel($img, $x, $y, $pixel);
						break;
			case 24 :	$a = ord($str[0]);
						$b = ord($str[1]);
						$c = ord($str[2]);
						$pixel = $c*256*256 + $b*256 + $a;
						imagesetpixel($img, $x, $y, $pixel);
						break;					
			case 8 :
			case 4 :
			case 1 :	imagesetpixel($img, $x, $y, $str);
						break;
		}
	}
 
	private static function byte3($n)
	{
		return chr($n & 255) . chr(($n >> 8) & 255) . chr(($n >> 16) & 255);	
	}
 
	private static function undword($n)
	{
		$r = unpack("V", $n);
		return $r[1];
	}
 
	private static function dword($n)
	{
		return pack("V", $n);
	}
 
	private static function word($n)
	{
		return pack("v", $n);
	}
}
 
 
$file = 'trabaja.bmp';
list($width, $height) = getimagesize($file);
$img = BMP::imagecreatefrombmp($file);
 
$lines = file('php://stdin');
$lines = array_map('trim', $lines);
 
foreach($lines as $line) {
    $y = substr($line, 1, strlen($line) - 1);
    $which = strtolower(substr($line,0,1));
    $out = 0;
    for($i = 0; $i < $width; $i++) {
        $rgb = imagecolorat($img, $i, $y);
        $r = ($rgb >> 16) & 0xFF;
        $g = ($rgb >> 8) & 0xFF;
        $b = $rgb & 0xFF;
 
        $out += $$which;
    }
    echo ($out + 1) . PHP_EOL;
}

Otro problema un poco raritu. Lo primero era encontrar un lector de imágenes BMP, que PHP no tiene por defecto (a diferencia de funciones como la anterior. Tras algo buscar, encontré por ahí la clase que veis (que me disculpe su autor pues no encuentro la referencia origen :().

Después, había que sumar el contenido de R, G o B de una fila que nos pidieran. Esta clase mola porque nos lo daba todo hecho jijiji.

Y lo más cachondo del caso, a esa suma, añadirle 1 (WHAT THE FUCK!), no entiendo nada! Si alguien sabe el motivo por favor que me ilustre.

Lo único que queda medio molón es usar el $$which (variables variables amigos! PHP Power a tope!) para sacar o $r o $g o $b. 0 optimizado como podéis comprobar pero hay que pensar que era sábado por la noche y el tiempo del concurso se empezaba a acabar.

Challenge 15: The Robot

Podéis consultarlo aquí

#!/usr/bin/php
<?php
 
$lines = file('php://stdin');
$lines = array_map('trim', $lines);
 
foreach($lines as $line) {
    $data = explode(' ', $line);
    $colors = array(1);
 
    $cwidth = array_shift($data);
    $cheight = array_shift($data);
    $squares = array_shift($data);
 
    for($i=0; $i < $cwidth; $i++) {
        for($j=0; $j < $cheight; $j++) {
            $canvas[$i][$j] = 1;
        }    
    }
 
    for($sq = 0; $sq < $squares; $sq++) {
        $tx = array_shift($data);
        $ty = array_shift($data);
        $bx = array_shift($data);
        $by = array_shift($data);
        $color = array_shift($data);
        $colors[] = $color;
 
        for($i=$tx; $i<$bx;$i++) {
            for($j=$ty; $j<$by;$j++) {
                $canvas[$i][$j] = $color;
            }
        }
    }
 
    $out = '';
    foreach($colors as $color) {
        $maybe = countcolor($canvas, $color, $cwidth, $cheight);
        if($maybe > 0) $out .= $color . ' ' . $maybe . ' ';
    }
    echo trim($out) . PHP_EOL;
}
 
function countcolor($canvas, $color, $cwidth, $cheight) {
    $count = 0;
    for($i=0; $i < $cwidth; $i++) {
        for($j=0; $j < $cheight; $j++) {
            if($canvas[$i][$j] == $color) $count++;
        }
    }
    return $count;
}
?>

Este también lo resolví a lo bruto. Meto el cuadro entero en memoria (ole yo!) y lo cambio todo ahí. Es mucho más óptimo guardarte las esquinas e ir mirando recursivamente si hemos machacado un número anterior o no. Pero a esas horas, no daba para más y con los tests iba rápido. Parece ser que en el submit te enviaban cosas mucho más gordas y se me quedaba colgado el programa. Y al intentar “debuggar” qué narices me estaba enviando, sin querer hice un exit, se submitió una respuesta incorrecta y ya nada. Epic fail yo.

Y para acabar, el problema 16, que no conseguí resolver y preferí pasar el domingo por la tarde en buena compañía jugando a la PS3 ;).

Challenge 16: The Bus Stations

Podéis consultarlo aquí

Aparentemente, es otro problema de libro de grafos. Yo lo intenté con el algoritmo de Ford-Fulkerson, del cual no encontré nada hecho en PHP. En la Wikipedia hay el código hecho en Python y lo intenté traducir, como había hecho con el Levenshtein del problema 7. El caso es que no sé Python y seguramente hice alguna cagada al traducirlo, porque no me salían bien los tests. O tal vez no sea el algoritmo correcto, ya que algunos casos iban y otros no.

Opinión personal

Por mi parte, me lo pasé muy bien intentando resolver los problemas. Es imposible no compararlo con la reciente Facebook Hacker Cup. Personalmente creo que estuvo bastante mejor montado, los problemas era más divertidos (no como en la Hacker Cup que o te sabías teoremas matemáticos raros o estabas perdido).
Hubo algunos problemas de submit el día de prueba pero fueron subsanados rápidamente. Parece ser que también cayó el servidor pero era un rato en el cual yo no estaba concursando.

Me gustó mucho el sistema de test y submit, especialmente comparado con el concurso anteriormente mencionado, pero había alguna “trampa” como que en algunos problemas el submit_challenge te enviaba otros datos y te podrían hacer petar tu solución. Y si se enviaba algo, ya no podías volverlo a intentar. No es que sea injusto, estaba claramente especificado, pero en mi caso me jorobó un par de soluciones.

No me gustó que en algunos problemas los casos de test de la explicación fueran incorrectos o incompletos. La gente se queja mucho y en realidad, apenas afectaba al desarrollo, pero queda algo descuidado. Tampoco me gustó las subidas y bajadas de dificultad de los problemas. Está claro que hay cosas que se nos dan mejor o peor a todos, pero todo el mundo se quedaba encallado en los 2, 4, 7, 12 y 16 (y no en otros). No sé si en otros lenguajes pasa lo mismo que en PHP, pero en mi caso ahí he visto los principales problemas.

He visto por ahí bastante nivel en las soluciones (casi me dan vergüenza las mías). Especial respeto a la gente que lo intentó hacer en lenguajes menos pragmáticos (como C o C++, demonios incluso he visto en pastebin una solución en assembler del primer problema, que en PHP es 1 línea). Y también comentar la absoluta elegancia de las soluciones en Python, un lenguaje que nunca he probado y que viendo el código de alguna gente, parece que es una auténtica maravilla. Bien por todos los Pythoneros.

Y finalmente, por lo que he visto, los problemas a partir del 17 eran una olla total. Poco que ver con programación y si con “hacking” y cosas de este estilo. No sé cuál era el objetivo final de montar el concurso si los últimos problemas no son retos algorítmicos.

El caso es que tras todo esto, en su día recibí un mail de Tuenti comentándome que era de los mejores (aunque según los stats habrá unas 100 personas mejores que yo) y si podía ir el 1 de julio a sus oficinas, que lamentablemente no puedo ir. A día de hoy no han publicado ningún ranking y no está muy claro qué pasara con los resultados.

En cualquier caso, me parece una buena manera de entretener a la gente y por qué no de hacer un proceso de selección de manera algo diferente. Bien por estos concursos y espero que haya muchos más, como los de Google, TopCoder, etc… la verdad es que es mucho más motivante que muchas tareas del día a día en nuestros trabajos.

En mi caso, he conseguido un montón de visitas y unos cuantos nuevos followers recíprocos en Twitter que a bien seguro llenaran mis notificaciones de cosas muy interesantes. Así que en cualquier caso, bien empleado el tiempo. Yo lo dejé en el momento que me dejó de divertir, al ver que no me salía un problema, y creo que fue una buena decisión.

Terminados estos posts, pronto más sobre PHP, seguramente con el prometido post de namespaces y nuevas aventuras, ya no en Privalia sino en Ulabox. Pronto tocaremos Redis, MariaDB, Symfony2, Behat, etc… así que Stay Tuned!

Actualización: Finalmente salieron los resultados del Tuenti Contest y quedé en la posición 71. Me pareció bastante injusto que no se penalizara el hecho de saltarte pruebas complicadas como los problemas 4 o 7. Estos problemas me hicieron perder bastante tiempo y seguramente habría podido resolver el 16 y el 17… pero nunca lo sabremos 🙂

Podéis ver las mejores puntuaciones aquí. Los 10 mejores están este fin de semana en las oficinas de Tuenti Madrid así que seguramente empezarán Julio con un nuevo contrato de trabajo. Felicidades!

You may also like...

4 Responses

  1. claretcrab says:

    Muy bien tio!

    Yo nunca me entero de estas movidas XD a ver cuando tengo un hueco y buen humor y voy haciendo estos ejercicios.

    Un saludo y mucha suerte en tu nuevo reto!

  1. 28/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 13 al 15 […]

  2. 28/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 13 al 15 […]

  3. 28/06/2011

    […] Ricard Clau (@ricardclau): Soluciones en PHP (del 13 al 15 […]