lunes, 5 de mayo de 2014

Tuenti Challenge 2014 - 2ª Parte

Challenge 3 - The Gambler's Club

Llegamos al primero de los problemas "no convencionales", entendiendo de esto modo aquellos que se alejan de la vertiente puramente algorítmica, para en este caso requerir de también de un poco de ingenio.

En este reto se recrea una de las etapas de Monkey Island 2, en la que debemos de intentar ganar a la ruleta, la cual evidentemente está trucada. Para ello se nos proporciona una web http://gamblers.contest.tuenti.net/ que como veremos también tiene truco.


En este caso se nos proporcionan 2 campos de entrada: "X" e "Y", y un campo de salida Z que varía en función de los 2 primeros. Nuestro objetivo es conseguir averiguar el valor de Z para 2 X,Y cualquiera, sabiendo que la web dada solo acepta valores enteros menores que 30, aunque en los test el valor puede llegar a 1337 ("you're ELITE hacker!!). Eso es lo que nos dice la teoría... osea el enunciado, pero como sabemos la teoría en muchas ocasiones difiere de la práctica.

¿Estamos seguros de que solo aceptan números enteros dichos campos de entrada? ¡¡Efectivamente!! Podemos introducir números flotantes y obtener un resultado mucho más preciso que nos permita obtener la progresión. Precisamente es este el punto clave para resolver rápido dicho ejercicio (y probar con cuantos más números mejor), dado que la progresión para este problema no es nada difícil de encontrar (por otros lares se ven algunas progresiones de enteros que hacen pupita). 

Así que tras probar con distintos valores, podemos comprobar como el resultado se dobla si se dobla la entrada, como si un valor es 0 el valor resultante es el otro valor, como 2 ceros nos dan 0... y si no, siempre podemos hacer uso de alguna herramienta adicional que nos ayude en nuestra tarea... por ejemplo... http://www.wolframalpha.com/input/?i={0.14%2C+0.28%2C+0.56%2C+1.12%2C+2.24%2C+4.47%2C+8.94%2C+17.89}

A partir de aquí, ya simplemente codificar la fórmula encontrada en nuestro lenguaje favorito, teniendo eso sí, especial cuidado con el redondeo de los números (a 2 decimales según el enunciado) y otro problema que nos apuntamos.

Dejo mi código por si alguien quiere verlo, pero es más simple que el mecanismo de un botijo:
 
/
/* C++ HEADERS */
#include <iostream>
#include <algorithm>


using namespace std;


int main(){

    int N; //Number of test cases
    cin >> N;

    double X,Y; //(X,Y < 1337)

    for(int n=0; n<N; n++){

        cin >> X >> Y;

        double smaller, higher;

        if(X<Y){
            smaller = X; higher = Y;
        }else{
            smaller = Y; higher = X;
        }

        if(smaller == 0){
            cout << higher << endl;

        }else{

            double base = higher/smaller;

            double op = pow(base, 2) + 1.0;

            double result = sqrt(op) * smaller;

            result = floor(result*100+0.5)/100; //Redondeo a 2 decimales

            cout << result << endl;
        }
    }

    return 0;
}

Dividimos el numero mayor entre el menor, elevamos al cuadrado, sumamos uno, realizamos raíz cuadrada y multiplicamos por el número menor. Todo ello redondeado con floor() a 2 decimales.

Aclaración: Como apunta Lagunex, la solución más simple hacía uso del teorema de Pitágoras. En mi caso la solución es una aproximación del mismo que funciona dentro de los rangos del problema.

Pd: En este caso era una secuencia de números en coma flotante, pero si alguna vez os encontráis con una secuencia de enteros nada mejor que https://oeis.org/

Challenge 4 - Shape Shifters

¿Pero qué hace aquí nuestra amiga mística? Seguro que nada bueno...

Nos trae un problema de mutación de nucleótidos, o lo que es lo mismo, de cambio de caracteres. Una serie de cadenas de caracteres divididas en:
  • 1º linea: Cadena de caracteres de partida
  • 2ª linea: Cadena de caracteres objetivo
  • 3ª linea en adelante: Cadenas de caracteres intermedias permitidas
Y nuestro objetivo es dictaminar la secuencia que nos lleva desde la cadena de partida hasta la cadena objetivo, pasando por las cadenas intermedias, y con solo un cambio de letra por vez. 

Como podéis ver este problema sube un escalón la dificultad con respecto a los anteriores, aunque es todavía un problema bastante asequible.

En mi caso opté por una búsqueda en profundidad con backtracking y tablas hash para tener una comparación constante de estados permitidos y ya generados. 

Como las letras son 4 únicamente: {A,C,G,T} se reduce considerablemente nuestro abanico de búsqueda. Como mi algoritmo cumplía tanto en la solución como en los tiempos con pruebas mayores que realicé, no contemplé otra alternativa, aunque este tipos de problemas suelen ser susceptibles de obtener un óptimo mediante un algoritmo greedy. Por eso si alguien optó por un algoritmo totalmente diferente y me lee (alguien me leerá no???) me gustaría que me lo hiciera saber.

El código del ejercicio resuelto es el siguiente:
/
/* C HEADERS */
#include <limits.h>


/* C++ HEADERS */
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

class depthSearch{

    private:

        int length;

        string initState;
        string targetState;

        stack<string> transitions;
        stack<string> best;

        int minDepth = INT_MAX;
        int depth=0;

        char nucleotides[4] = {'A', 'C', 'G', 'T'};

        unordered_map<string, bool> safeStates;

        string actualState = targetState;
        unordered_map<string, bool> generados;


    public:

        //Busqueda en profundida con backtracking y tablas hash para comparación constante
        depthSearch(string _initState, string _targetState, unordered_map<string, bool> _safeStates){

            initState = _initState;
            targetState = _targetState;
            safeStates = _safeStates;

            length = initState.size();
        }

        stack<string> search(){
            generados[targetState] = true;
            transitions.push(targetState);
            recursive(targetState);
            return best;
        }

        void recursive(string actualState){

            for(int i=0; i<length; i++){ //CAA
                char ant = actualState[i];
                for(int j=0; j<4; j++){

                    actualState[i] = nucleotides[j]; //CGA

                    //Se comprueba si no está entre los ya generados
                    if(!generados.count(actualState)){

                        //Se comprueba si dicho sucesor esta entre los estados permitidos
                        if(safeStates.count(actualState)){
                            generados[actualState] = true;
                            transitions.push(actualState);
                            depth++;

                            if(actualState == initState){
                                if(depth < minDepth){
                                    minDepth = depth;
                                    best = transitions;
                                }
                                return;
                            }else{
                                recursive(actualState);
                            }
                            transitions.pop();
                            depth--;
                        }
                    }

                    actualState[i] = ant; //CGA
                }
            }
        }

};


int main(){

    string sourceState;
    cin >> sourceState;

    string targetState;
    cin >> targetState;


    unordered_map<string, bool> safeStates;

    string tmp;
    int s=0;
    while (cin >> tmp){

        safeStates[tmp] = true;
        s++;
    }

    depthSearch mySearch(sourceState, targetState, safeStates);

    stack<string> transitions = mySearch.search();

    int _size = transitions.size();
    for(int i=0; i<_size; i++){
        cout << transitions.top();
        if(i<_size-1)
            cout << "->";
        transitions.pop();
    }
    cout << endl;

    return 0;
}
Opté por utilizar recursividad para la búsqueda en profundidad, y por realizar backtracking si uno de los estados obtenidos no estaba entre los permitidos o si dicho estado se había generado previamente (para evitar bucles tontos del estilo aaa->aac->aaa).

Tras obtener el visto bueno del jurado virtual, ya había conseguido completar el 20% de la competición. Pero la cosa seguiría complicándose cada vez más...

Challenge 5 - Tribblemaker

Reconozco que no soy nada aficionado a Star Trek: esos tipos raros, que parecen elfos interestelares; pero por el contrario, si que conocía bien el juego de la vida, y aún recuerdo cuando en primero de carrera nuestro profesor nos lo contó con un aire de emoción incontenible (cosas de la docencia universitaria xd).

Para quien no conozca el juego de la vida, puede tirar un poco de wikipedia: http://es.wikipedia.org/wiki/Juego_de_la_vida 

Realmente no es un juego, dado que no hay jugadores ni ganadores, sino que se trata de situar en un tablero cierto patrón, y que este, mediante unas reglas de asociación con sus vecinos, evolucione a lo largo del tiempo, simulando la propagación de la vida (a lo 'Spore' setentero). Sobre él hay un montón de bibliografía, estudios e incluso hasta gente que se atreve a realizar deducciones filosóficas (sí, sobre unos puntos que se mueven sobre una matriz).

Pues bien, resulta que la evolución a lo largo del tiempo tiene la peculiaridad de que genera ciertos patrones que se repiten de forma cíclica. Y nuestra labor será, a partir del estado de entrada, buscar el primer patrón que se repite, y decir en que estado se produce y cual es su periodo.

Para este fin hay muy diversas opciones, pudiendo algunas llegar a alcanzar unas cotas de eficiencia muy altas, como los modelos de bases disjuntas que podrían hacer uso de la gran cantidad de patrones conocidos para calcular directamente dicho patrón.

Pero algo muy importante a la hora de resolver un problema de tipo algorítmico es tener en cuenta las restricciones y el tamaño de los datos de entrada. Y en este caso los datos son muy claros: un tablero de 8x8 del cual no hay vida más allá de su bordes , y solo 100 iteraciones de tiempo en las que debemos de buscar patrones. Sí, definitivamente me voy a decantar por un algoritmo cuadrático y no me complico la vida.

Pero siempre hay algunos factores que se pueden tener en cuenta de cara a optimizar un mínimo el algoritmo. Por ejemplo, como en nuestro caso el tablero es de 8x8... eso significa que tenemos 64 casillas... y quizás... solo quizás... podríamos hacer hacer uso  de un entero de 64 bits para representar todo el tablero ¿no? xd

Manos a la obra: creemos un array de tipo long long y 101 elementos (dado que podemos llegar a la iteración 100), y calculemos las 100 iteraciones a partir del estado de partida. Para calcular las iteraciones debemos de conocer las reglas básicas del juego de la vida:
  • Una célula con más de 3 vecinos muere por sobrepoblación
  • Una célula muerta nace con exactamente 3 vecinos
  • Una célula viva con 2 o 3 vecinas sigue viva
  • Y en otro caso muere o permanece muerta
 Una vez calculadas y almacenadas las 101 primeras iteraciones, es la  hora de realizar una simple búsqueda cuadrática, que se limita a comparar un entero de 64bits con otro:

 
/
/* C++ HEADERS */
#include <iostream>

using namespace std;


class lifeGame{

    private:

        bool grid[8][8]; //Actual grid

        //Como el tablero tiene 64 casillas, se puede representar como un entero de 64 bits (2^64)
        unsigned long long int iterations[101];

        //Conversion de un tablero booleano a un entero de 64 bits
        void grid_to_bits(unsigned long long int &n, bool grid[8][8]){

            for(int i=0; i<8; i++){
                for(int j=0; j<8; j++){
                    if(grid[i][j])
                        n |= 1 << ((i*8)+j);
                }
            }
        }

        void printGrid(bool grid[8][8]){

            for(int i=0; i<8; i++){
                for(int j=0; j<8; j++){
                    if(grid[i][j])
                        cout << "X";
                    else
                        cout << "-";
                }
                cout << endl;
            }
        }


    public:

        lifeGame(bool initGrid[8][8]){

            for(int i=0; i<8; i++){
                for(int j=0; j<8; j++){
                    grid[i][j] = initGrid[i][j];
                }
            }

            for(int i=0; i<101; i++)
                iterations[i] = 0;
        }

        void computeIterations(){o

            //Convertimos a un entero de 64bits
            grid_to_bits(iterations[0], grid);

            //The grid is guaranteed to loop eventually before reaching generation 100
            for(int l=1; l<=100; l++){

                //Game of life
                bool newGrid[8][8];

                int neighbors;
                for(int i=0; i<8; i++){
                    for(int j=0; j<8; j++){

                        //Para cada posición del tablero calculamos el numero de vecinos
                        neighbors = 0;

                        for(int m=-1; m<2; m++){
                            for(int n=-1; n<2; n++){
                                if(grid[i+m][j+n]
                                   && (i+m>=0 && j+n>=0 && i+m<8 && j+n<8)
                                   && (m!=0 || n!=0) ){ //La propia casilla no cuenta como vecino
                                    neighbors++;
                                }

                                if(neighbors>3) //Con más de 3 vecinos siempre muere por sobrepoblacion
                                    goto _exit;
                            }
                        }

                        _exit:

                        //Una celula muerta nace con exactamente 3 vecinos
                        if( !grid[i][j] && neighbors == 3)
                            newGrid[i][j] = true;

                        //Una celula viva con 2 o 3 celulas vecinas vivas sigue viva
                        else if( grid[i][j] && (neighbors == 2 || neighbors == 3) )
                            newGrid[i][j] = true;

                        //En otro caso muere o permanece muerta
                        else
                            newGrid[i][j] = false;
                    }
                }

                for(int i=0; i<8; i++)
                    for(int j=0; j<8; j++)
                        grid[i][j] = newGrid[i][j];


                //Convertimos a un entero de 64bits
                grid_to_bits(iterations[l], grid);
            }

        }

        void findLoops(int &first, int &period){

            /*Se podría haber utilizado algún algoritmo más complejo, pero dado que solo tenemos 100 elementos
            un algoritmo de eficiencia cuadrática es totalmente viable*/

            for(int i=0; i<100; i++){
                for(int j=i+1; j<100; j++){
                    if(iterations[i] == iterations[j]){
                        //cout << "ciclo encontrado\n";
                        first = i;
                        period = j-i;
                        i=100; break;
                    }
                }
            }
        }

};


int main(){

    bool grid[8][8];

    char tmp;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            cin >> tmp;
            if(tmp == 'X')
                grid[i][j] = true;
            else
                grid[i][j] = false;
        }
    }


    lifeGame myGame(grid);

    myGame.computeIterations();

    int first,period;

    myGame.findLoops(first, period);

    cout << first << " " << period << endl;

    return 0;
}

Cruzamos los dedos, realizamos el test, enviamos código y finalizamos con un OK de aprobación. ¡Pues adelante!

Capítulo 6
http://programacioncompetitiva.blogspot.com.es/2014/05/tuenti-challenge-2014-3-parte.html 

8 comentarios:

  1. Yo creo que el problema 3 podías resolverlo usando el teorema de Pitágoras.

    ResponderEliminar
    Respuestas
    1. Sí, tal cual. Con (1,1) daba 1.41 y con (3,4) daba 5. Los números correspondían. Mañana empiezo a publicar mis soluciones. Te aviso para que les eches un vistazo. Seguiré viendo las tuyas. Saludos.

      Eliminar
  2. Creo que la solución esperada del 4 es un BFS, un recorrido en anchura. El DFS que propones hay casos específicos en los que tarda demasiado (aunque hay que tener mala suerte y son difíciles de generar). Estos casos consisten básicamente en que a pesar de que encuentres un camino que te lleve a tu destino, nada te asegura que sea el óptimo, de forma que tienes que volver y considerar el resto de caminos, y a poco que encuentres que puedes llegar a un nodo intermedio siguiendo un camino más corto tienes que volver a empezar. Con mucha mala suerte un DFS puede llegar a tardar tiempo exponencial, mientras que el BFS no tarda más que el número de aristas (que en este caso es lineal con la entrada). En general, cualquier problema en el que debas encontrar el camino más corto entre dos puntos se hace con BFS (en caso de aristas sin pesos), o Dijkstra (si las aristas tienen pesos).

    ResponderEliminar
    Respuestas
    1. Gracias por tus comentarios Lander.

      Por cierto me suenta tu nick... puede ser de TopCoder???

      Un saludo

      Eliminar
  3. Agh!, mira que el puñetero Monkey lo intenté probar con Wolphram Alpha al ver que Excel no sacaba nada (y ante mi desconocimiento de paquetes matemáticos, ya sean online o no). Y no sé qué botón pulsé o cómo llegué, pero no me dejaba introducir datos, como si fuera una característica de pago. Me jodió porque aunque lo entregué sabía que lo estaba haciendo mal (me decanté por poner una interpolación, más que nada por si acaso).

    ResponderEliminar
    Respuestas
    1. Sí, el uso de herramientas complementarias es muy útil cuando se trata de problemas de secuencias de números.

      Y además en muchas ocasiones estos problemas depende de que como te venga la inspiración ese día.

      Un saludo

      Eliminar