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 depends previously solving tasks y,z,w x,y,z,w it is imposible for two different to be dependent on one common task: #task this not valid x,y z,y expected output following format: taskid taskcomputationtime x tx y ty z tz from standard input you will receive a set which compute total in 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...