lunes, 5 de mayo de 2014

Tuenti Challenge 2014 - 1ª Parte

Bueno, pues en estos momentos ya ha finalizado la edición de esta año de la Tuenti Challenge, la competición de programación/algorítmica/problemasquetehacendartecabezazoscontralamesa de la empresa Tuenti (sí esa red social reconvertida a operadora movil).




Y como he tenido algo de tiempo (que en verdad no lo tenía, sino que se lo he quitado a otros menesteres), pues he participado en ella por primera vez y puedo contaros aquí mi experiencia, junto con mis soluciones.

Antes de nada comentar que a diferencia de otros concursos de programación competitiva en los que he participado recientemente, Tuenti Challenge no se limita a quemar nuestras cabezas unicamente con problemas de tipo algorítmico como podemos ver en otros concursos como CodeJam o TopCoder. En esta competición además se incluyen retos de seguridad informática o de ingeniería inversa, y como postre algunos retos en los que prima más el ingenio que la capacidad técnica: un "completo" en toda regla.

Es más, por momentos he podido remontarme a mi infancia, y recordad esa sensación que tenía cuando jugaba aventuras gráficas como "Maniac Mansion" o "Monkey Island" (que por cierto había un problema que lo homenajeaba), y me pasaba horas y horas repitiendo las mismas acciones y estrujándome la sesera para llegar finalmente a la conclusión de que la contraseña de la prisión es "0000".  Aquella época pre-web en la que enfrentarse a una de esos videojuegos era poco más que una odisea.

Bueno, pero voy al grano, mi resolución de los problemas. Para que podáis criticarme vilmente y herir mi denostada autoestima xd



Challenge 1 - Anonymous Poll

 

 El primero de todos los problemas. Aquel al que uno llega con toda la ilusión del mundo. Aquel cuya dificultad uno espera que se mantenga a lo largo del resto del desafío. Y aquel que comienza a darnos los primeros quebraderos de cabeza xd.

El problema nos mencionaba que nuestra universidad quería rellenar una encuesta anónima, que finalmente resultaba no ser tan anónima, y por tanto nos daba un archivo con 5000 entradas, donde cada entrada contenía el nombre del alumno, genero, edad, estudios y año académico.

A continuación por la entrada estándar se nos daba el número de casos a resolver y las características del alumno/alumnos. Nuestra tarea consistía en devolver el nombre de aquellos que coincidieran con dichas características o "None" en caso de no haber ninguna coincidencia. Un problema típico de bases de datos, facilito para empezar.

Pd: La descripción exacta de todos los problemas los podéis encontrar en la web del concurso: https://contest.tuenti.net/Challenges

Además otra de las características del desafío, es que el lenguaje de programación a elegir es secundario, siempre que nuestro código sea "legible" (si bien es cierto que he visto una clara orientación hacia la utilización de lenguajes como php o python, normal por otra parte tratándose de una empresa como tuenti). Para ello, cada uno de los desafíos se ejecutan en nuestra máquina, y mediante las "tools" que se nos proporciona se da el visto a nuestra solución, recibiendo tanto los casos de prueba como los definitivos desde los servidores de tuenti y enviándose de igual modo. La verdad es que en este aspecto, un 10 para los chicos de ingeniería de Tuenti, porque la herramienta me ha funcionado a la perfección.

Bueno volviendo al tema del lenguaje, mi idea en un principio era utilizar aquel lenguaje que mejor se desenvolviera para cada problema, si bien es cierto que acostumbro a utilizar C++ cuando participo en algún concurso de este tipo, y además es el lenguaje que más domino (junto con C). El primer problema además se prestaba a su uso. Aquí os muestro mi solución:


/* C++ HEADERS */
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;


int main(){

    //Utilizaremos una tabla hash con múltiples valores por cada clave
    unordered_multimap<string, string> hashTable;

    ifstream students_list("students");
    if(students_list.is_open()){

        string mapped;
        while(getline(students_list, mapped, ',')){

            string key;

            getline(students_list, key);

            hashTable.insert({key,mapped});
        }
    }

    int T; //Number of test cases (T<=100)
    cin >> T;

    string query;

    //Flush cin
    cin.ignore(256,'\n');
    cin.clear();

    for(int t=0; t<T; t++){

        cout << "Case #" << t+1 << ": ";

        getline(cin, query);

        auto its = hashTable.equal_range(query);

        int sizeV = distance(its.first, its.second);

        if(sizeV==0){
            cout << "NONE" << endl;

        }else{

            vector<string> answer(sizeV, "");

            int i=0;
            for(auto it = its.first; it != its.second; ++it){
                answer[i] = it->second;
                i++;
            }

            //Realizamos ordenación alfabética de los resultados
            sort(answer.begin(), answer.end());


            for(int j=0; j<i; j++){
                cout << answer[j];
                if(j<i-1){ cout << ","; }
            }
            cout << endl;
        }
    }

    return 0;
}
 
Como veis este primer desafío no tiene mucho que comentar. Hago uso de un contenedor "unordered_multimap" de STL, que es basicamente una tabla hash que permite varios valores por clave, e introduzco como clave los valores de cada alumno y como valor el nombre del alumno.

Después para cada input realizo una consulta a dicha tabla hash, si no hay ningún valor muestro "NONE", y en caso de que si haya valores que se correspondan con dicha clave, procedo a realizar la ordenación de los resultados con la función "sort" (que no es más que una ordenación "Introsort").

A continuación llega el momento de realizas los test, y tras ser satisfactorios el envío definitivo. En este momento se nos muestra un mensaje que acojona un poco acerca de que tenemos una única oportunidad y será la única y unicamente única de las únicas, pero tras tragar saliva con decisión pulsamos "yes" y nuestro programa envía nuestro código y los resultados de la ejecución final. 

Aquí es importante matizar, que tal y como nos advierten en las bases del concurso, los datos de entrada pueden ser mucho mayores que los de prueba, y por tanto llegar a que nuestra ejecución se alargue eternamente (ya lo veremos más adelante, ya...). Afortunadamente, estamos en el desafío 2.


Challenge 2 - F1 - Bird's-eye Circuit

Segundo desafío, en esta ocasión con el equipo Tuenti Racing Team como aderezo, y con un circuito a vista de pájaro como primer plato.
Ahora se nos proporcionaba un circuito ASCII en una sola línea del input, y nosotros debíamos de ser capaces de ensamblarlo y mostrarlo correctamente por la salida, como si de una vista aérea se tratase. La única condición que se nos imponía es que la meta debe de encontrarse en una recta horizontal y de izquierda a derecha.

Se trata de un problema para que nos peleemos con la salida, y le demos vueltas a ese salto de línea que no termina de encajar o ese espacio que nos sobra. Con un poco de paciencia se puede sacar adelante sin mucho problema. 

Mi solución fue la siguiente:


/* C++ HEADERS */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>


using namespace std;

enum _direction{toRight, toLeft, up, down};

class circuitMatrix{

    private:

        int SIZE;

        char **matrix;

        int min_col;
        int max_col;
        int min_row;
        int *max_row;


        int posX;
        int posY;
        _direction dir = toRight;

    public:

        circuitMatrix(int _size){

            SIZE = _size;

            matrix = new char*[SIZE];
            for (int i = 0; i < SIZE; i++)
                matrix[i] = new char[SIZE];


            for(int i=0; i<SIZE; i++)
                for(int j=0; j<SIZE; j++)
                    matrix[i][j] = ' ';

            max_row = new int[SIZE];
            for(int i=0; i<SIZE; i++)
                max_row[i] = 0;

            min_col = SIZE-1;
            max_col = 0;
            min_row = SIZE-1;

            posX = SIZE/2;
            posY = SIZE/2;

        }

        ~circuitMatrix(){

            for (int i = 0; i < SIZE; i++)
                delete [] matrix[i];
            delete [] matrix;

            delete [] max_row;
        }

        void insert(const char caracter){

            char c = caracter;

            if(c == '-')
                if(dir == up || dir == down)
                    c = '|';


            matrix[posX][posY] = c;

            if(posX > max_col)
                max_col = posX;

            if(posX < min_col)
                min_col = posX;

            if(posY > max_row[posX])
                max_row[posX] = posY;

            if(posY < min_row)
                min_row = posY;

            if(c == '-' || c == '#'){

            }else if(c == '/'){
                if(dir == toRight)
                    dir = up;
                else if(dir == toLeft)
                    dir = down;
                else if(dir == up)
                    dir = toRight;
                else if(dir == down)
                    dir = toLeft;

            }else if(c == '\\'){
                if(dir == toLeft)
                    dir = up;
                else if(dir == toRight)
                    dir = down;
                else if(dir == down)
                    dir = toRight;
                else if(dir == up)
                    dir = toLeft;
            }


                if(dir == toRight)
                    posY++;
                else if(dir == toLeft)
                    posY--;
                else if(dir == up)
                    posX--;
                else if(dir == down)
                    posX++;
        }


        void print(){
            for(int i=min_col; i<=max_col; i++){
                for(int j=min_row; j<=max_row[i]; j++){
                    cout << matrix[i][j];
                }
                cout << "\n";
            }
        }
};


//Para comprender el uso de Arrays sobre Listas enlazadas, mirar la siguiente referencia:
//http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
//y como la localidad de cache se torna en clara vencedora frente al rendimiento asintótico

int main(){

    string input;

    cin >> input;
    int inputSize = input.size();

    circuitMatrix circuit(inputSize+2);

    for(int n=0; n<inputSize; n++){
        circuit.insert(input[n]);
    }

    circuit.print();

    return 0;
}
Una clase circuito, con una matriz de caracteres, y un método insert que me realiza la inserción y en la que solamente hay que ir teniendo en cuenta los cambios de dirección. La única dificultad que se podía alguien encontrar aquí estaba en como realizar la inserción y la impresión por pantalla de los datos. En mi caso no me complique y opté por empezar a escribir los datos desde el centro de la matriz y que fuera después mi función de impresión la que se encargara de fijar los límites. Fácil y sencillo.

 Y al 3º desafío. http://programacioncompetitiva.blogspot.com.es/2014/05/tuenti-challenge-2014-2-parte.html

No hay comentarios:

Publicar un comentario