lunes, 5 de mayo de 2014

Tuenti Challenge 2014 -4ª Parte

Challenge 8 - Tuenti Restructuration

El problema 8 comenzaba contándonos los planes de re-estructuración que el jefe de personal de Tuenti tenía en mente. Dichos cambios estaban apuntados en una tabla de 3x3 que se correspondía con la oficina, y cada una de esas casillas con una de las mesas de los empleados.

Pues bien, para llevar a cabo la mudanza de escritorio se había pensado en. que los empleados se intercambiaran su mesa con el compañero que tuviera adyacente, llevándose a cabo un cambio por día. Al final del proceso, tras un periodo de X días, la disposición final de los compañeros debe ser tal cual, el jefe había planificado en su tabla (también se menciona que la casilla central debe estar vacía).

El objetivo es encontrar el número mínimo de días necesario para llevar a cambio la mini-mudanza, dado como entrada la situación original, y la situación final deseada.

Nada más comenzar a leer el problema no podía evitar acordarme de dos tipos a los que seguro que muchos de vosotros conoceis:


Quizás estas caras no os digan nada, pero si os digo el título de uno de sus libros seguro que algo os suena: 
"Artificial Intelligence: A modern approach" , en español "Inteligencia Artificial: Un enfoque moderno". 

Este libro es a día de hoy, el más utilizado en las universidades de todo el mundo para enseñar a sus alumnos las bases de la inteligencia artificial. Y aún recuerdo, cuando hace apenas 2 años lo estudiaba, y en uno de sus capítulos aparecía la siguiente figura:


Se trata ni más ni menos del juego del 8-puzzle, el hermano menor del 15-puzzle, y en el libro era uno de los ejemplos principales de mejora de rendimiento al utilizar heurísticas óptimas con A*. Se explicaban los fundamentos del algoritmo A*, sus variantes, y se explicaban la creación y elección de una heurística apropiada. Para quien quiera conocer algo más acerca de A* visitar http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*

A grosso modo, se trata de un algoritmo greedy, que elige en cada momento aquella opción con un menor coste f(n), donde f(n) = g(n)+h(n), siendo g(n) la distancia actual recorrida (o el coste verdadero), y h(n) la distancia esperada si tomamos esa decisión (esperada porque es una heurística). A cambio, el coste que pagamos por elegir un algoritmo heurístico es que aún obteniendo una solución de mucha calidad, puede no ser óptima.

Pero este aspecto está también cubierto para el caso de A*, y bajo 2 condiciones una heurística ofrecerá un resultado óptimo:
  • Que sea una heurística admisible, es decir, que en ningún momento piense que el valor de una elección es mayor que el que realmente es (que siempre piense de forma optimista).
  • Que cumpla la desigualdad triangular, lo que se traduce en que el coste para llegar desde un nodo a otro nodo, siempre debe ser menor que la suma de llegar a este nodo pasando por otro y desde este al buscado, si estos sumados nos dan un coste mayor. 
Es importante remarcar que todo esto se engloba dentro de una búsqueda en arboles, por lo que la elección de una heurística de calidad tendrá un peso decisivo en el factor de ramificación del árbol de búsqueda (una mejor heurística proporcionara un árbol mucho más reducido). Por tanto, cuanto mejor sea la heurística menor tiempo de ejecución, y sobre todo, menos gasto de memoria, ya que en el algoritmo A* el gran limitante es el consumo de memoria al guardar todos los nodos previamente generados (hay variantes de A* que sacrifican rendimiento a favor de un consumo menor de memoria).

Las heurísticas son por tanto dependientes del problema, y deben de ser estudiadas cuidadosamente para el problema en cuestión que estemos tratando. Dentro de las heurísticas más usuales para resolver problemas de tipo 8-puzzle/15-puzzle podemos encontrar:
  • Número de casillas discordantes
  • Distancia de Manhattan
  • Conflicto lineal
  • Patrones disjuntos
Aparecen ordenadas de menos eficientes a más eficientes (desgraciadamente también de menos complejas de implementar a más complejas de implementar).

Bueno, una vez soltado esta "intro", abordaré como afronté este problema.

En primer lugar, antes de lanzarse a implementar nada, es importante reflexionar acerca de las herramientas y ayudas previas con las que contamos. Si por ejemplo, tenemos una contenedor de tipo "stack" no tiene sentido implementar nuestra propia pila. Además en C++ contamos tanto con STL (dentro del standard), como con Boost (que amplia vastamente las posibilidades de la STL).

Sin embargo, a la hora de tratar con estructuras de datos como son los arboles, no existe una librería de uso general a la que acudir por antonomasia, dado que las implementaciones de un árbol suelen ser bastante dependientes del problema, por lo que se suele implementar para el propósito concreto.

En mi caso, hace algún tiempo atrás había implementado el algoritmo A*, pero no disponía a día de hoy de dicho código. Por tanto opté, por implementarlo desde 0 y de repaso pegarle un repaso a algunos conceptos que tenía un poco oxidados.

A continuación el código:


/* C++ HEADERS */
#include <iostream>
#include <fstream>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iterator>
#include <utility>

using namespace std;

int NODOS=0;


//Tuenti Challenge 8:
//  Problema de tipo 8-puzzle con strings
/*-----------------------------------------------------------------------------------------------*/
/*---------------- SOLUCION CON A ESTRELLA Y HEURISTICA DE MANHATTAN MODIFICADA -----------------*/
/*-----------------------------------------------------------------------------------------------*/

template <class T>
class node{

    private:
    //Cada nodo tendrá su propio contenido
    T _data;

    //Puntero al nodo padre
    node * _parent;

    //Apuntamos a los nodos hijos de dicho nodo
    vector<node *> _child;

    int _gn; //g(n) = profundidad de dicho nodo

    //Función a la que se llama para generar los hijos de un nodo
    void (*funcPtr)();

    public:

        node(){
            _parent=0;
            _child.reserve(12); //12 para este caso
            _gn = 0;
        }

        void insert(const T &in){
            _data = in;
        }

        T data(){
            return _data;
        }

        node * parent(){
            return _parent;
        }

        void printPath(){
            node * nodo = this;
            cout << nodo->_data << endl;
            while(nodo->_parent!=0){
                nodo = nodo->_parent;
                cout << nodo->_data << endl;
            }
        }

        int gn(){
            return _gn;
        }

        node * child(int n){
            return _child[n];
        }

        node<T>* addChild(T data){
            node<T> *nodo = new node;
            nodo->insert(data);
            nodo->_parent = this;
            for(int i=0; i<12; i++)
                nodo->_child[i] = 0;
            nodo->_gn = _gn+1; //Aumentamos en 1 la profundidad del recorrido
            _child.push_back(nodo);
            return nodo; //Devolvemos una referencia al nodo insertado
        }


};

template <class T>
class link{

    private:

    public:

        node<T>* ptr;
        int _fn;

};

bool operator<(const link<int>& op1, const link<int> op2){
            return op2._fn < op1._fn;
}


template <class Te>
class tree{

    private:

        node<Te> root;

        node<Te> * nodoActual;

        int (*genFunction)(Te&, const int);//Función sucesor

        int (*hFunction)(const Te&, const Te&);//h(n)

        priority_queue<link<Te>> liveNodes;

        int best=-1;

        node<Te>* addNode(Te data){
            NODOS++;
            return nodoActual->addChild(data);

        }


        void recursiveFree(node<Te> *nodo){

            for(int i=0; i<12; i++){
                if(nodo->child(i) == 0){
                    delete nodo;
                    //nodo = nodo->parent();
                    break;
                }else{
                    recursiveFree(nodo->child(i));
                }
                //nodo = nodo->parent();
            }
        }

    public:

        tree(const Te &data){
            root.insert(data);
            nodoActual = &root; //Nodo Actual = nodoRaiz
        }

        ~tree(){
            node<Te> *nodo = &root;
            recursiveFree(nodo);
        }

        //Función a la que se llama para generar cada nodo (Función Sucesor)
            //Como primer parámetro se pasa el contenido de dicho nodo
            //Como segundo parámetro se pasa el numero de iteración en dicho nivel(comenzando por 1)
        void generationFunction(int (*funcPtr)(Te&, const int)){
            genFunction = funcPtr;
        }

        //Función heurística a utilizar en la búsqueda A*
            //Como primer parámetro se pasa el estado actual
            //Como segundo parámetro se pasa el estado objetivo
        void heuristicFunction(int (*funcPtr)(const Te&, const Te&)){
            hFunction = funcPtr;
        }

        //Realiza una búsqueda A* sobre dicho arbol, encontrando la solución óptima
        int Astar(Te searchFor){

            //Si no quedan más nodos para expandir no existe solución

            //Llamamos a la función 'genFunction' sobre el nodo actual
            Te data = nodoActual->data();

            if(data == searchFor){
//                cout << "Encontrado con numero de movimientos : " << nodoActual->gn() << endl;
//                nodoActual->printPath();
                best = nodoActual->gn();
                return best;
            }

//            if(NODOS>500000){
//                best = 14;
//                return best;
//            }

            for(int n=1; genFunction(data, n) != -1; n++){

                link<Te> tmpLink;
                tmpLink.ptr = addNode(data); //Añadimos cada uno de los nodos hijos
                tmpLink._fn = hFunction(data, searchFor) + nodoActual->gn() + 1; //f(n) = h(n)+g(n)

                liveNodes.push(tmpLink); //Añadimos un puntero al nuevo nodo hijo, junto con su valor f(n) a la cola con prioridad

                data = nodoActual->data();
            }

            //link<Te> debug = liveNodes.top();

            if(!liveNodes.empty()){


                //Una vez generados todos los nodos del nivel inferior, elegimos el nodo vivo con menor valor f(n)
                //mediante una consulta a nuestra cola con prioridad, y cambiamos el nodoActual por dicho nodo

                nodoActual = liveNodes.top().ptr;


                //Eliminamos dicho enlace de la cola con prioridad
                liveNodes.pop();

                //debug = liveNodes.top();
                //cout << debug.ptr->data() << endl;

                Astar(searchFor);
            }


            //Devolvemos el valor encontrado
            return best;
        }

};

//La funcion debe devolver -1 cuando haya realizado la ultima generación
int exchange(int &num, int numLlamada){

    string tmp = to_string(num);

    if(numLlamada == 1){
        swap(tmp[0],tmp[1]);
    }else if(numLlamada == 2){
        swap(tmp[1],tmp[2]);
    }else if(numLlamada == 3){
        swap(tmp[3],tmp[4]);
    }else if(numLlamada == 4){
        swap(tmp[4],tmp[5]);
    }else if(numLlamada == 5){
        swap(tmp[6],tmp[7]);
    }else if(numLlamada == 6){
        swap(tmp[7],tmp[8]);


    }else if(numLlamada == 7){
        swap(tmp[0],tmp[3]);
    }else if(numLlamada == 8){
        swap(tmp[3],tmp[6]);
    }else if(numLlamada == 9){
        swap(tmp[1],tmp[4]);
    }else if(numLlamada == 10){
        swap(tmp[4],tmp[7]);
    }else if(numLlamada == 11){
        swap(tmp[2],tmp[5]);
    }else if(numLlamada == 12){
        swap(tmp[5],tmp[8]);
    }else if(numLlamada == 13){
        return -1;
    }

    num = stoi(tmp);
    return 1;
}


//Función heurística para el problema basada en la distancia de Manhattan (dividida por 2 dadas las caracteristicas del problema)
int Manhattan(const int &confActual, const int &confBuscada){

    int distanciaM = 0;

    int origen[3][3];
    int destino[3][3];

    string tmp = to_string(confActual);
    int k=0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            origen[i][j] = tmp[k] - '0';
            k++;
        }
    }

    tmp = to_string(confBuscada);
    k=0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            destino[i][j] = tmp[k] - '0';
            k++;
        }
    }

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

            for(int l=0; l<3; l++){
                for(int k=0; k<3; k++){

                    if(origen[i][j] == destino[l][k]){
                        //Calculamos distancia
                        int dist = abs(l-i) + abs(k-j);
                        distanciaM += dist;
                        l=3; k=3;
                    }
                }
            }
        }
    }

    int valor;

    if(distanciaM > 2)
        valor = (distanciaM/2) + (distanciaM/12);
    else
        valor = (distanciaM/2);
    return valor;
}

//Función heurística para el problema basada en el numero de piezas mal colocadas
int MalColocadas(const int &confActual, const int &confBuscada){

    int mal = 0;

    int origen[3][3];
    int destino[3][3];

    string tmp = to_string(confActual);
    int k=0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            origen[i][j] = tmp[k] - '0';
            k++;
        }
    }

    tmp = to_string(confBuscada);
    k=0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            destino[i][j] = tmp[k] - '0';
            k++;
        }
    }

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

            if(origen[i][j] != destino[i][j]){
                mal++;
            }
        }
    }

    return mal/2;
}



void miFuncion(int &number){
    number++;
}

int encodeTable(int table[3][3]){

    int entero = 0;
    entero += table[0][0]*100000000;
    entero += table[0][1]* 10000000;
    entero += table[0][2]*  1000000;
    entero += table[1][0]*   100000;
    entero += table[1][1]*    10000;
    entero += table[1][2]*     1000;
    entero += table[2][0]*      100;
    entero += table[2][1]*       10;
    entero += table[2][2]*        1;
    return entero;
}


class parseTables{

    private:

        string origen[3][3];
        string destino[3][3];

        //Tabla hash que asocia cada numero con su correspondiente string
        unordered_map<int, string> hash_itos;

        //Tabla hash que asocia cada string con su correspondiente numero
        unordered_map<string, int> hash_stoi;


        void readTable(string table[3][3]){

        string name;

        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                cin >> name;
                if(name.find(',')!=string::npos)
                    name.erase(name.find(','),1);
                table[i][j] = name;
//                cout << name << " " ;
            }
//            cout << endl;
        }
        table[1][1] = "*"; //Elemento central

        }

    public:

        void readTables(int orig[3][3], int dest[3][3]){

            readTable(origen);
            readTable(destino);

            //Sustituimos cada string por un digito del 1 al 9
            for(int i=0; i<3; i++){
                for(int j=0; j<3; j++){
                    int digito = 3*i + j + 1;
                    orig[i][j] = digito;
                    hash_itos[digito] = origen[i][j];
                    hash_stoi[origen[i][j]] = digito;
                }
            }

            //Realizamos dicha sustitucion tambien en la tabla destino
            for(int i=0; i<3; i++){
                for(int j=0; j<3; j++){
                    auto it = hash_stoi.find(destino[i][j]);
                    dest[i][j] = it->second;
                }
            }
        }

};


int main(){

    int T;
    cin >> T;

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

        int origen[3][3];
        int destino[3][3];

        parseTables myParser;

        myParser.readTables(origen, destino);

        tree<int> arbol(encodeTable(origen)); //El nodo raiz contiene el valor 5

        arbol.generationFunction(exchange); //Fijamos la función de generación de nuevos nodos

        arbol.heuristicFunction(Manhattan); //Fijamos la función heurística = h(n)
        //arbol.heuristicFunction(MalColocadas);

        cout << arbol.Astar(encodeTable(destino)) << endl;

    }
}

Quizás tendría que haber escogido alguna otra modificación de A* como BRPM, o similares con el fin de minimizar la cantidad de nodos en memoria, pero tras algunos ajustes a la heurística la cantidad de memoria utilizada me pareció razonable.

En cuanto a la estrutura de la clase he de reconocer que todavía esta en pañales porque la he creado a toda prisa expresamente para este problema. Pero la idea es que tuviera una estructura lo suficientemente genérica como para poder re-aprovecharla en futuros problemas similares.

Con ese fin he creado los métodos generationFunction(), y heuristicFunction(), los cuales toman como parámetros la respectiva función de generación y función heurística a utilizar por la clase A*, en este caso las funciones exchange y manhattan (esta también codificada una heurística Mal_Colocadas que se corresponde con una heurística de número de casillas discordantes, pero obviamente su rendimiento era mucho peor).

El tema de la heurística, comentar que es una modificación de la distancia de Manhattan, la cual hay que dividir por 2 en este caso para que siga siendo óptima, dado que los intercambios que propone dicho problema difieren del concepto original de 8 puzzle en el que se mueve una ficha cada vez. Queda pendiente para un futuro implementar una heurística de bases disjunta (quizás el año que viene?).

Nota: Otra opción que he visto que ha utilizado @Landertxu0 es la siguiente: dado que tenemos solo un tablero de tamaño 3x3 (esto nos da un total de 9! = 362880 posiciones distintas en el tablero), precalcular la distancia a cada una de estas, almacenarlas y después utilizarla para cada uno de los casos que se nos pedían. Esta técnica se conoce como precomputación y me parece una solución fantástica dado el tamaño del problema. Después podemos obtener cada solución en un tiempo constante. Podéis consultar su descripción original en http://www-ma2.upc.edu/lramos/wp-content/uploads/2014/05/writeup.pdf

Queda en el tintero una posible solución con A* + precomputación. Si alguno de los que me leéis habéis utilizado dicha solución, agradecería mucho que lo comentarais.

@Landertxu0 además sugiere una búsqueda bidireccional como otra posible solución al problema.

Precisamente la idea de utilizar una búsqueda bidireccional para problemas de tipo 8-puzzle también aparece en el libro de Russell y Norvig:


Si bien es cierto que la eficiencia de una búsqueda bidireccional es bastante más pobre que la de un A* con una heurística adecuada: O(b^d/2), siendo 'd' la profundidad de la solución y 'b' el factor de ramificación.

Challenge 9 - Bendito Caos

Un enunciado inicialmente muy confuso, o por lo menos esa fue la impresión que inicialmente me dió. El problema nos comentaba la situación de un joven que quería montar una fiesta para los habitantes de las ciudades cercanas. Y para tener el suficiente avituallamiento para todos, debía de calcular la cantidad de personas que podrían llegar teniendo en cuenta las limitaciones de la carretera.

Al principio creí que se trataba de un problema de teoría de colas, pero cuando por fin pude comprenderlo en su totalidad (porque el enunciado se las traía), lo oriente simplemente como un problema de restricciones en grafos.

Vayamos al tema del enunciado: 

  • Se nos daba el número de ciudades siento todas ellas independientes en sus conexiones, y siendo subproblemas distintos. Hasta aquí todo bien.

     

    Se nos explicaba que había 2 tipos distintos de carreteras, cada una con un tipo de velocidad distinta. Vale.

     

    Ahora llega la primera duda que me surgió: se especificaba que las carreteras tenían uno o dos carriles unidireccionales "Each road may have one or two lanes", sin embargo en los ejemplos de prueba se daban carreteras de 1,2 o 3 carriles.

     

    Después se nos explicaba el concepto de intersección, pero a mi gusto era un poco superficial la explicación que se daba, y a continuación se nos explicaba que las carreteras estaban definidas "desde-hasta", es decir por un origen y un final, pudiendo ser estos una intersección o una ciudad. Aquí la verdad que me costo un poco hasta que pude comprender plenamente el formato de los archivos de entrada.

     

    Por último lo que más claro quedaba era que los coches median 4metros con 1metro entre cada uno de ellos. Por lo tanto 5metros por cada coche.

     

El problema ahora nos pedía que calcularamos el número de coches que podían viajar desde la ciudad de origen hasta AwesomeVille en una hora.


La cantidad de vehículos viene dada por la suma de las carreteras entrantes, y estas se ven limitadas por la carretera de menor velocidad que surte de coches a dicha carretera. Por tanto de primeras podríamos utilizar una búsqueda en profundidad recursiva y de este modo ir a través de las distintas intersecciones y calcular el cual es el limitante.


Pero este tipo de aproximación se torna extremadamente ineficiente (exponencial con respecto al número de nodos).


Desde mi punto de vista este problema encaja bien con un problema de satisfacción de restricciones, y en mi caso lo implementé como un grafo con propagación de restricciones. Este es mi código:


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

using namespace std;

/*------------------ IMPLEMENTACION MEDIANTE UN GRAFO CON PROPAGACI�N DE RESTRICCIONES ------------------*/



class Edge{

    private:

    public:

        int origin;
        int destination;
        int vel;
        int lanes;

};


int main(){

    int C; //Number of cities
    cin >> C;

    for(int c=0; c<C; c++){

        string cityName;
        cin >> cityName;

        int S; //Maximum speed for roads
        int D; //Maximum speed for dirt roads

        cin >> S;
        cin >> D;

        int I; //Intersection numbers
        int R; //Road numbers

        cin >> I;
        cin >> R;

        vector<int> inter(I,0); //Guardamos el flujo de trafico entrante

        vector<Edge> edges;
        edges.reserve(R);

        string origin, destination, type, lanesNum;

        //Leemos cada una de las carreteras del mapa
        for(int r=0; r<R; r++){

                Edge edge;

                cin >> origin;
                cin >> destination;
                cin >> type;
                cin >> lanesNum;

                if(type == "normal")
                    edge.vel = S;
                else
                    edge.vel = D;

                edge.lanes = stoi(lanesNum);

                if(origin == "AwesomeVille"){
                    edge.origin = -1;
                }else if(origin == cityName){
                    edge.origin = -2;
                }else{
                    edge.origin = stoi(origin);
                }

                if(destination == "AwesomeVille"){
                    edge.destination = -1;
                }else if(destination == cityName){
                    edge.destination = -2;
                }else{
                    edge.destination = stoi(destination);
                }

                edges.push_back(edge);
        }


        //Calculamos ahora el valor total de entrada de todas las intersecciones
        for(int r=0; r<R; r++){
            if(edges[r].destination >= 0){ //Tiene como destino una interseccion
                if(edges[r].origin == -2){ //Si dicha arista parte de la ciudad visitante
                    inter[edges[r].destination] += edges[r].vel * edges[r].lanes;
                }
            }
        }

        //Iteramos mientra haya cambios en la propagacion de las restricciones
        bool modificado=true;
        while(modificado){
            modificado = false;
            for(int r=0; r<R; r++){
                if(edges[r].destination >= 0){ //Tiene como destino una interseccion
                    if(edges[r].origin >= 0){ //Y parte de una interseccion
                        int add = min(edges[r].vel * edges[r].lanes, inter[edges[r].origin]);
                        int ant = inter[edges[r].destination];
                        inter[edges[r].destination] = max(add, inter[edges[r].destination]);
                        if(ant != inter[edges[r].destination] )
                            modificado = true;
                    }
                }
            }
        }



        long long velTotal = 0;
        for(int r=0; r<R; r++){

            //Solo tenemos en cuenta las carreteras con destino a "AwesomeVille"
            if(edges[r].destination == -1){

                //Si es una carretera directa
                if(edges[r].origin == -2){
                    velTotal += edges[r].vel * edges[r].lanes;

                //En caso contrario vendrá limitada por la intersección
                }else{
                    velTotal += min(inter[edges[r].origin] , edges[r].vel * edges[r].lanes);
                }
            }

        }

        velTotal *= 1000; //Las medidas de los coches en metros

        //cout << "\n\nvelTotal = " << velTotal << endl;
        cout << cityName << " " << velTotal/5 << endl; //5 metros = 4metros coche + 1metro separación
    }

    return 0;
}

De esta forma las restricciones (en este caso la velocidad limitante) se progagan a las intersecciones vecinas hasta que no hay más cambios sobre el grafo.


Importante ver también que aquellas carreteras cuya dirección de circulación es contrario a la ciudad de destino, ni siquiera las tengo en cuenta, dado que no afectan al resultado del problema los coches que vienen de AwesomeVille.

Esta era otra de las dudas que me surgían, si el trafico entrante en las intersecciones bloqueaba al tráfico en la dirección contraria de la intersección (de ahí lo de la teoría de colas).


Después ya simplemente nos queda dividir el número total de "ancho de banda" de las carreteras por 5 metros, que es la longitud de un coche con su respectiva separación para obtener el resultado pedido.


Y con esto me  encontraba en el desafio 10 con todos los desafios completados hasta el momento. Pero aún no era consciente de la pesadilla que me esperaba...


Desafio 10 http://programacioncompetitiva.blogspot.com.es/2014/05/tuenti-challenge-2014-5-parte.html

10 comentarios:

  1. Tu pesadilla fue el 10, la mía fue el 8. Por desgracia no me han presentado el algoritmo de A*, pero si investigando llegué a él. Al tiempo de conocerlo lo descarté, no supe encajar las modificaciones y pensé que estaba metiendo la gamba. A partir de ahí otro puñado de ideas arrojadas y de investigaciones matemáticas. Aun sueño con el problema, literalmente.

    El 9 llegué a verlo horas antes de acabar y no pude terminar la implementación. Mi idea era parecida, pero en lugar de propagar, cada nodo era un "Buffer" cuya función de obtener coches llamaba a sus nodos padres recursivamente. Buen trabajo!

    ResponderEliminar
    Respuestas
    1. Para todo el tema de heurísticas el libro que arriba menciono es una maravila, si tienes ocasión echale un vistazo (googleando lo encuentras). Te da las pautas básicas y además te aporta referencias claras a sitios donde ampliar la información. Además para problemas de tipo N-puzzle A* no tiene rival, permitiendo resolver problemas 24-puzzle y mayores.

      En cuanto al problema 9, y el tema de la propagación de restricciones, lo tenía todavía muy fresco, porque nos lo machacaron un montón en unas prácticas de la carrera, y la verdad que aunque mi implementación aquí es un poco churro, la técnica da mucho de sí y se utiliza un montón en la implementación de planificadores (HTN y similares), pero vamos que yo solo conozco lo básico porque esa rama de la Inteligencia Artificial es todo un mundo aparte.

      Un saludo

      Eliminar
  2. Yo pensé la misma implementación! La puedes ver en https://github.com/Darkeye9/tuenti-challenge4/blob/master/c9/c9.php

    ResponderEliminar
    Respuestas
    1. Sí, realmente creo que era una de las mejores elecciones para este problema, porque era sencilla de implementar y eficiente.

      Solo que en tu caso has utilizado PHP, y veo que queda una implementación mucho más compacta, practicamente la mitad de lineas.

      Un saludo

      Eliminar
  3. Parece que hay algo que algunos no hemos contemplado en el problema 9... ¿has visto que tu solución da dos WRONG [1 y 2] en el submit?

    ResponderEliminar
    Respuestas
    1. --- OUTPUT CHECK --------------------------
      Line 1 [OK!] : NiceVille 37200
      Line 2 [OK!] : StrangeVille 6000
      Line 3 [OK!] : UglyVille 16200
      Line 4 [OK!] : RandomVille 18600

      Estos fueron los casos con los que se probaban en el test durante el concurso, pero efectivamente para el caso final da dos fallos el programa (lo acabo de probar ahora porque durante el concurso no se tienen dichos resultados). Voy a echarle un vistazo y si doy con la tecla lo comento y lo arreglo.

      Un saludo

      Eliminar
    2. Estoy echándole también un vistazo a las soluciones de otros participantes, y por ahora las 3 que he probado tienen alguno de sus casos mal.

      Voy a seguir indagando a ver donde puede estar el fallo, porque quizás no hayamos tenido en cuenta alguna restricción del problema. Como ya digo en el post, el enunciado era un poco confuso.

      Un saludo

      Eliminar
    3. La solución correcta para dicho problema es la siguiente:

      Line 1 [OK!] : NiceVille 168400
      Line 2 [OK!] : StrangeVille 21400
      Line 3 [OK!] : UglyVille 58400
      Line 4 [OK!] : RandomVille 18000

      , y mi código falla las 2 primeras, con 108000 y 72600. Ahora solo queda averiguar porqué se produce dicho fallo.

      Eliminar
  4. Ei, gracias por la mención! Respecto a usar A* más precomputación, la verdad es que no lo acabo de ver. La gracia del A* es que llega al objetivo antes que un BFS, ya que vas guiando el camino. Pero en este caso concreto no queremos llegar a un estado, sino a todos, por lo que no creo que un A* nos pudiera ayudar, ya que no tenemos que guiar la solución hacia ningún sitio en concreto.

    Respecto a la búsqueda bidireccional, sí es cierto que tarda en caso peor O(b^d/2), pero claro, esta cota supone que nunca hay coincidencias (es decir, que no podemos llegar a un estado por dos caminos diferentes), y en este problema en concreto esto no sucede. De hecho aplicando esta misma cota, un BFS ordinario (unidireccional), tardaría tiempo O(b^d), que es 12^14, más de 10^15, cuando el espacio de estados es mucho menor. También es cierto que la cota inferior de la raíz cuadrada del número de estados no creo que se alcance, pero sería cuestión de probarlo.

    ResponderEliminar
  5. Muchas gracias por tus aportes Lander, es un placer leer a gente como tú con tanto conocimiento en la materia.

    Un saludo

    ResponderEliminar