Tuenti Contest – Problemas 1 a 4

Vaya semanita nos ha dado el Tuenti Contest a todos aquellos que nos apuntamos y decidimos participar.

Hemos sacado horas de nuestros fines de semana, noches y incluso algún ratito en el trabajo para intentar solucionar los diferentes problemas planteados.

El objetivo de estos posts es presentar mis soluciones tal cual las envié, aunque allí donde vea que se pueda mejorar lo comentaré. También tengo la intención de explicar por qué hice esto o aquello, espero que sirva de ayuda!

Dicho esto, al lío!

Challenge 1: Super hard sum

Your amazing program should calculate the sum if the numbers given in each line, and output on line for each question with the response. Numbers can be negative, really big and lines contain extra spaces, so make your program resistant to input.

Your program will need to read from standard input, line by line till the end of the input. Consider each line a different question. For each line you read, output the sum of all the given numbers.

Sample input
2 3
4 5 -1
Sample output
5
8

#!/usr/bin/php
<?php
$lines = file('php://stdin');
foreach($lines as $line) {
    echo array_reduce(preg_split('/\s/', trim($line)), 'bcadd') .  PHP_EOL;
}
?>

Este problema parecía tirado, pero había espacios dobles y triples y sobretodo… en números muy grandes la suma normal de PHP nos deja tirados ya que da un overflow. La función correcta para sumar números grandes es bcadd de la librería bcmath. También me regalé un poco usando array_reduce, una función no demasiado conocida.

Challenge 2: TLang

We use a variety of languages and technologies here at Tuenti. Sometimes we even develop our own languages and tools. Here is an example from a programming language that we use when we want to blow our minds. Your task is to interpret it!

Sample input
^= 1 2$
^# 2 2$
^@ 3 1$
Sample output
3
4
2

#!/usr/bin/php
<?php
 
function decode($str) {
    $str = trim($str, '^$');
    $arg = explode(' ', $str);
 
    if(!isset($arg[2])) {
        $arg[2] = $arg[1];
        $arg[1] = 0;
    }
 
    switch($arg[0]) {
        case '=':
            return ($arg[1] + $arg[2]);
        case '#':
            return ($arg[1] * $arg[2]);
        case '@':
            return ($arg[1] - $arg[2]);
    }
}
 
$lines = file('php://stdin');
 
foreach($lines as $line) {
    $line = trim($line);
    while(preg_match('/\^[=|#|@]+ [-?\d]+( [-?\d]+)?\$/', $line, $matches) == true) {
        $line = str_replace ($matches[0], decode($matches[0]), $line);        
    }
    echo $line .PHP_EOL;    
}
?>

En este había dos putaditas. La primera la expresión regular en sí, que se las traía y no sé si esta versión mía es la más idónea ya que soy un PCRE user, no expert :). Y la segunda es que había casos donde el segundo operando es opcional. En ese caso, había que asumir un primer elemento 0, se veía con los tests pero no estaba especificado en el problema.
Por lo demás, el programa va sustituyendo hasta tener un valor final en cada fila.

Challenge 3: Emirps

What is the sum of all emirps up to X?

Sample input
100
200
Sample output
418
1489

#!/usr/bin/php
<?php
 
function checkifprime($prime){
    if($prime % 2 == 0) return false;
    $max = sqrt($prime);
    for($i = 3; $i <= $max; $i = $i+2){
        if ($prime % $i == 0) {
            return false;
        }
    }
    return true;
}
 
 
function generaEmirps($max) {
    $primos = array();
    for($i = 11; $i <= $max; $i = $i+2){
        if(checkifprime($i)){
            $primos[] = $i;
        }
    }
 
    $emirps = array();
    $total = count($primos);
    for($i = 0; $i < $total; $i++) {
        $reverse = strrev($primos[$i]);
        if($reverse == $primos[$i]) continue;
        if(checkifprime($reverse)) {
            $emirps[] = $primos[$i];    
        }
    }
    return $emirps;
 
}
 
$lines = file('php://stdin');
 
$max = 0;
foreach($lines as $line) {
    $line = trim($line);
    if($line > $max) $max = $line;
}
 
$emirps = generaEmirps($max);
 
foreach($lines as $line) {
    $line = trim($line);
    $sum = 0;
    foreach($emirps as $emirp) {
        if($emirp > $line) break;
        $sum += $emirp;
    }
    echo $sum . PHP_EOL;
}
?>

Aquí empezaba la fiesta. Primero… qué es un emirp? Emirps Wikipedia
Y una vez hecho esto… si no vamos con cuidado con la checkIfPrime se nos puede ir de madre el tiempo de ejecución, fijaros bien que voy aumentando de 2 en 2 (para evitar mirar los números pares) y solamente miramos hasta la raíz cuadrada del número ya que es absurdo mirar más adelante.

Challenge 4: Task Duration

You are trying to solve a very complex problem. In order to simplify it, you have divided it into many sub tasks. Most of these sub-tasks can be run in parallel, but some are dependent on the previous resolution of other tasks. There is no limit on the number of tasks that can be run in parallel. Each task has an associated computation time.

You are be given a subset of these tasks. For each of them you need to specify what is the minimal computation time for resolving the task (you must consider task dependencies).

The relations between the tasks are represented in the file contained in this archive: in.zip.This file is in the following format:

#Number of tasks
n

#Task duration <- task x has an associated computation time of tx x,tx #Task dependencies <- the resolution of task x depends of previously solving tasks y,z,w x,y,z,w It is imposible for two different tasks to be dependent on the resolution of one common task: #Task dependencies <- this is not valid x,y z,y The expected output is the following format: taskId taskComputationTime x tx y ty z tz From the standard input you will receive a set of tasks for which to compute the total time in the following format: x,y,z Sample input file
#Number of tasks
6

#Task duration
0,2
1,3
2,4
3,9
4,7
5,9

#Task dependencies
0,4
3,0,1,2
4,5

Sample standard input for tasks to compute time
3,1,4

Sample output
3 27
1 3
4 16

#!/usr/bin/php
<?php
ini_set('xdebug.max_nesting_level', 10000);
 
$zip = zip_open('in.zip');
do {
    $entry = zip_read($zip);
} while ($entry && zip_entry_name($entry) != 'in');
 
zip_entry_open($zip, $entry, 'r');
$entry_content = zip_entry_read($entry, zip_entry_filesize($entry));
 
$lines = explode(PHP_EOL, $entry_content);
unset($entry_content);
 
$tasks = array();
for($i = 4; $i < $lines[1] + 4; $i++) {
    list($id, $time) = explode(',', $lines[$i]);
    $tasks[$id] = array('time' => $time);    
}
 
$total = count($lines);
 
for($i = $lines[1] + 6; $i < $total; $i++) {
    $data = explode(',', $lines[$i]);
    $id = array_shift($data);
    $tasks[$id]['depend'] = $data;
}
 
$input = file('php://stdin');
foreach(explode(',', trim($input[0])) as $in) {
    echo $in . ' ' . calculaTiempo((int)$in, $tasks) . PHP_EOL;
}
 
 
function calculaTiempo($in, $tasks) {
 
    if(!isset($tasks[$in]['depend'])) return $tasks[$in]['time'];
    else {
        $total = (int)$tasks[$in]['time'];
        $timesdepend = array();
        foreach($tasks[$in]['depend'] as $depend) {
            $timesdepend[] = (int)calculaTiempo((int)$depend, $tasks);
        }         
        return $total + max($timesdepend);
    }
}
?>

Y aquí la cosa se desmadra, con una recursividad que se pone en más de 100 en un momento (de ahí la primera instrucción cambiando un parámetro del xdebug y un zip que supongo que se puede optimizar su carga en memoria pero en mi caso como véis cargo entero en memoria nada más empezar (muy optimizable).

Pues nada, por hoy os dejo estos 4, en próximos días unas cuantas soluciones más!

You may also like...

13 Responses

  1. Jose says:

    Veo que has usado PHP. Bién hecho.
    Yo he usado C++ y es una odisea, mientras que a tí las soluciones te salen super simples. Hasta el superhardsum me ha salido complicadillo al haber entradas raras con comas y tal. Y el TLang ni te cuento…¡He tenido que usar Lex+Yacc para analizar la entrada y hacer un mini-intérprete! Claro, en eso eché una cantidad de tiempo desmesurada y entre eso y que es la época de exámenes, pues no he pasado del 4.
    Para la próxima tengo que aprender PHP sí o sí. Definitivamente C++ está muy bien para hacer cálculos y algoritmos, pero para leer la entrada es una bazofia. La forma en que has resuelto el TLang, me ha dejado patidifuso. A mi me han salido unas 200 complicadas lineas de Lex/Yacc (y muchísimas horas para hacer que funcione) y a tí unas 30 lineas claras te funciona. No es matar moscas a cañonazos, yo más bien he usado una bomba H… Me dan ganas de pegarme un tiro por tonto 😛

    PD: Soy el único imbecil que ha optado por hacerlo en C++, Lex, Yacc etc?? Hay alguien más?
    PD2: Sabes de algún otro lenguaje que te permitan leer facilmente la entreda a parte de PHP?

    Saludos y gracias por compartir tus soluciones!

    • Gangi says:

      Seguramente hay más, pero yo he utilizado Python y Perl y ambos tienen “regular expresions” con lo que la lectura de entrada se hace muy amena.

  2. Hola Ricard.

    Me gusta tu solución del segundo problema por la expresión regular. Yo lo implementé como una pila, que es un poco más óptimo, pues si son muchas operaciones anidadas y tal, no sé cuál puede ser el costo de evaluar la expresión para buscar un match. Ya lo explicaré cuando llegue a él (estoy colocando mis soluciones en mi blog) y te aviso. Aunque asumir cero como primer operador puede verse feo para la multiplicación, yo también hice lo mismo. Quizás sería más puro asumir un 1 en ese caso.

    En el problema 3, cambié el chequeo de si es primo o no por un preproceso para obtenerlos con la Criba de Eratostenes. Ocupo más espacio en memoria pero es más rápido de ejecutar.

    Finalmente, con respecto al 4 un grafo tan grande como el que nos daban en el archivo resultaría en un volcado de pila seguro si se hacía una recursión. Al igual que con el 2, está pendiente de mi blog para cuando explique la solución del 4 sin recursión.

    Un saludo. Seguiré pendiente de tus soluciones para irlas comentando.

  3. Agustin says:

    Hola Ricard.
    Yo también he utilizado PHP para resolver los problemas. Por razones de tiempo y trabajo no pude llegar más allá del 7. Me parece muy elegante la forma en que resolviste el 1. No conocía la bcadd. La solución 2 la resolví interpretando directamente caracter a caracter, es verdad que el que pudiera haber operaciones de 1 solo operando (el famoso -229) era un poco especial.
    La verdad que PHP es genial para resolver los problemas (al menos hasta el 7), facilita las cosas.
    ¿Hasta cuál llegaste tu? Quedo a la espera de ver más soluciones!
    Muchas gracias.

  4. Ricard Clau says:

    Gracias por vuestros comentarios, os contesto uno a uno:

    @Jose: Creo que eres bastante duro contigo mismo. Cada uno coge el lenguaje con el que se siente más cómodo y con eso intenta solucionar. Hacer las cosas en C o C++ es generalmente más complicado pero una vez compilado va muchísimo más rápido que en PHP. En cuanto a lenguajes tan pragmáticos como PHP te recomiendo Python o Ruby.

    @Carlos: Gracias por tus comentarios, especialmente viniendo de alguien que quedó bastante mejor clasificado que yo :). En el 3, no está muy limpio pero solamente genero los emirps una vez, buscando el número más grande de la lista. Miraré el tema de la Criba de Eratóstenes ya que si es más rápido merece la pena. En cuanto al problema 4, sí fue bastante desastroso ver como la recursividad mataba mi proceso. Con el 10000 pasaba los tests pero en el submit me petó, seguramente porque enviaban algo más crítico. Espero tu solución sin allocar todo en memoria.

    @Agustin: Yo llegué hasta el 16, donde me quedé atascado y no tenía más tiempo para dedicar en el fin de semana. Estoy de acuerdo que PHP simplifica mucho la lectura de los datos y la mayoría de operaciones que se pedían

    @Todos: Esta noche las soluciones del 5 al 8!

  5. Chefwww says:

    Primero de todo felicidades por el blog es espectacularmente interesante. Estuve a punto de apuntarme pero supuse que no sería trivial y tengo el tiempo un poco justo por estas fechas. Según veo, los problemas 1 y 2 supongo que los huviese sacado sin problemas. El 3 es un poco más complicado y el 4 ya veo que la cosa se complica bastante. Supongo que en este último huvise tenido algo de complicación. Miedo me da ver el resto 😀

    P.D Lo del concurso me parece una gran idea. A ver si me apunto al próximo.

  6. Ruyman says:

    Felicidades, me parecen muy buenas las soluciones, sobretodo la primera en pocas líneas lo haces todo, buenísimo. A mi el problema 4 se me quedaba un poco colgado por el tema recursivo. Un nivel muy alto he visto por tuenti, tanto que me da hasta miedo subir mis soluciones jajajja. Estaría bien hacer un benchmark con una serie de valores para medir las velocidades de ejecución de cada solución. Un saludo y enhorabuena.

  1. 21/06/2011

    […] en el momento que me encuentre un “$”, desempilo para realizar la operación. He visto una buena solución utilizando PHP y expresiones regulares que la hacen mucho más corta en número de líneas (y me […]

  2. 22/06/2011

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

  3. 22/06/2011

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

  4. 22/06/2011

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

  5. 22/06/2011

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

  6. 23/06/2011

    […] depende directamente del OS. En el caso de Java y PHP, si no modificamos esos parámetros (como algunos hicieron), los casos de test […]