Resolviendo el #TuentiContest: Problema 4 – Task Duration

Para este problema nos dan una serie de tareas, con su duración y las dependencias entre ellas y nos piden devolver el tiempo mínimo que tardará cada una. En realidad no lo piden para cada una, sino unas en específico que ellos nos indicarán, pero veremos que solucionarlo para todas las tareas puede ser más fácil que buscar solucionarlo solo para algunas. Esta solución la implementé en C++. Mi lenguaje de competencia siempre ha sido Java, pero en mis actividades del doctorado he tenido que trabajar con C++, así que implementar este tipo de problemas me ha servido de práctica (y para seguir odiando su sintaxis y su reguero de includes cada día que pasa). Recuerda que también puedes ver mis otras soluciones. Antes del análisis del problema, es importante destacar que una de las fallas más feas en la competencia se dio aquí. Muchos preguntaron cómo lidiar con el archivo y con los casos de prueba a la vez, pues no se entendía si sería el mismo archivo siempre o si era un ejemplo, o cualquier otra cosa. Había que asumir que el archivo se leía como uno quisiera mientras se dejara libre la entrada estándar para los ejemplos. Las respuestas fueron escasas por parte del equipo de Tuenti y dado que Twitter no es un cómodo foro para aclaraciones, era una odisea divagar por la línea de tiempo para encontrar alguna duda de algún participante. Además, este problema también trae consigo la dificultad del tiempo de ejecución, pues si metes la pata en la solución, puede dispararse (hay que ser cuidadoso con tanto loop involucrado). Mucha gente se quejaba de que el script de Tuenti se colgaba y no podían enviar sus soluciones y aseguraba que era culpa del script pues su solución era correcta. Resulta que el script ejecuta el programa en la máquina local y luego de obtener el resultado, lo enviaba de vuelta. Por lo tanto, si tardaba, era cosa nuestra. Eso podrían aclararlo para calmar a los participantes (caso aparte la noche en que se cayó el servidor de Tuenti).

Análisis del problema

Un problema muy genérico de muchas más aplicaciones en la vida real de las que se puede creer. Esta colección de tareas puede verse como el pensum (o plan de estudios) de una carrera, donde no puedes inscribir asignaturas si no has completados otras antes, un diagrama de Gantt de un proyecto empresarial (o personal si eres muy ordenado), o un traductor automático (sí, del estilo de Google) en donde para traducir una palabra, debes haber cubierto otras anteriormente. Dada la naturaleza del problema, la estructura indicada para resolverlo es un grafo. Daré por sentado que sabemos lo que es para poder avanzar más rápido. Este tipo de grafos en particular es acíclico, pues si una tarea A depende de B, B no puede depender de A (¿cuándo comenzarías?) y tienen una propiedad clave, poseen un orden topológico. Por lo tanto, si obtenemos el orden topológico de nuestro grafo, podremos recorrer los nodos de forma lineal sin usar la recursión. ¡Ah la recursión! La mejor amiga de los lenguajes funcionales. La querida por todos para obtener números factoriales pequeños y resolver las Torres de Hanoi. Una recursión es sin duda una de las formas de escribir código más bonitas. Pocas líneas, muy legibles y funcionan… casi siempre. El problema principal de la recursión muchas veces no es del algoritmo en sí, sino de la pila de ejecución, la cual se nos puede volcar si la recursión es muy profunda. Y con la pinta que tenía ese grafo, esto se veía venir. Ya conocidas las herramientas y precauciones, pasemos al rollo. Uno de los datos más importantes del problema es que nos dicen que las tareas se pueden paralelizar tanto como queramos. Por lo tanto, antes de cumplir con una tarea A con precedencias B, C y D, podemos ejecutar todas las precedencias en paralelo y cuando terminen, entonces ejecutar A. De aquí que el tiempo mínimo para completar A sea: total(A) = t(A) + max(total(B),total(C),total(D)) Con lo cual, la recursión es una tentación irresistible. Más fácil de implementar imposible… con la salvedad de que nuestro amigo grafo tiene un millón de nodos unidos y moriremos en el intento. Para eliminar la recursión (la cual es una aproximación “top-down” del problema) haremos los cálculos al revés, primero obtendremos los tiempos de los nodos que no tienen precedencias, luego de los nodos que tenían a los primeros como precedencia, y así sucesivamente hasta encontrar el nodo que queramos. Esta aproximación se denomina “bottom-up” y suele ser la manera de eliminar recursiones. ¿Cómo hacemos “bottom-up”? Pues con el orden topológico. Solución enviada Gracias a mis conocimientos limitados de C++, este es uno de los problemas más largos que implementé. Lo iré explicando por partes (a alto nivel y sin entrar en detalles del lenguaje). Si luego del repaso, ven que pude haber hecho algo mejor, agradecería los comentarios. El primer bloque de código muestra mi implementación de un grafo (y el chorro de includes que necesité). Lo defino como una serie de tareas (Task, los nodos del grafo) que contienen un identificador (task), la cantidad de dependencias inconclusas (dependencies), una lista con las tareas de la que depende (before) y otra con las tareas que dependen de ella (after). Adicionalmente algunas variables globales como el número de tareas, la duración de cada tarea, el tiempo mínimo necesario por cada tarea (lo que nos pedirán luego) y las tarea independientes (aquellas que no necesitan ninguna tarea para arrancar)

#include <string>
#include <map>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <list>

using namespace std;

class Task {
public:
 int task;
 int dependencies;
 vector<int> before;
 vector<int> after;

 Task() {
 task = -1;
 dependencies = 0;
 }
};

map<int,Task> graph;
int numberOfTask;
vector<int> durations;
vector<int> minimun;
list<int> independent;

Con nuestras estructuras definidas es tiempo de leer el archivo de entrada. 50 líneas de las que puede que se rían muchos, sobre todos los amigos de python o PHP, que tienen mejores herramientas de parseo y operaciones funcionales. Lo importante a destacar aquí es que cuando me dan las dependencias, guardo en las líneas resaltadas tanto la información “A depende de B” como “B es predecesor de A” y para A, la cantidad de dependencias que tiene. La función loadIndependents(), de la línea 81 agrega en una lista todos los nodos que no tienen dependencias. Estas serán las primeras tareas que podremos completar e inaugurarán nuestro orden topológico.

void loadFile(string filename) {
  ifstream file(filename.c_str());
  int estado = 0;
  string linea;
  while (getline(file, linea)) {
    if (linea == "#Number of tasks") {
      estado = 1;
    } else if (linea == "#Task duration") {
      estado = 2;
    } else if (linea == "#Task dependencies") {
      estado = 3;
    } else if (linea.size() > 0) {
      size_t pos;
      size_t newPos;
      int task;
      int info;
      switch (estado) {
      case 1:
        numberOfTask = atoi(linea.c_str());
        for (int i = 0; i < numberOfTask; i++) {
          durations.push_back(0);
          minimun.push_back(0);
        }
        break;
      case 2:
        pos = linea.find(',');
        task = atoi(linea.substr(0, pos).c_str());
        info = atoi(linea.substr(pos + 1).c_str());
        durations[task] = info;
        minimun[task] = info;
        break;
      case 3:
        pos = linea.find(',');
        task = atoi(linea.substr(0, pos).c_str());
        while (pos != string::npos) {
          newPos = linea.find(',', pos + 1);
          info = atoi(linea.substr(pos + 1, newPos - (pos + 1)).c_str());
          pos = newPos;

          graph[task].task = task;
          graph[task].before.push_back(info);
          graph[task].dependencies++;

          graph[info].task = info;
          graph[info].after.push_back(task);
        }
      }
    }
  }
}
void loadIndependents() {
  for (int i = 0; i < numberOfTask; i++) {
    if (graph[i].dependencies == 0) {
      independent.push_back(i);
    }
  }
}

Y ahora, la función estrella. computeTimes() sigue el orden topológico que se inicia llamando a loadIndependence() y a partir de allí, empieza a resolver tareas. Primero calcula el tiempo mínimo necesario para cada tarea independiente t (líneas [92,98]) y luego actualiza las tareas que tiene a t como dependencia, avisándoles que t ya ha sido completada (línea 101). En caso de que una de estas tareas ya no tenga dependencias, podemos agregarla a nuestra lista de independientes para que sea completada en su momento (líneas [102,103]).

void computeTimes() {
  for (list::iterator it = independent.begin(); it != independent.end(); it++) {
    int task = (*it);
    Task& t = graph[task];
    for (vector::iterator dep = t.before.begin(); dep != t.before.end(); dep++) {
      int dependency = (*dep);
      if (minimun[dependency] + durations[task] > minimun[task]) {
        minimun[task] = minimun[dependency] + durations[task];
      }
    }
    for (vector::iterator aft = t.after.begin(); aft != t.after.end(); aft++) {
      int after = (*aft);
      graph[after].dependencies--;
      if (graph[after].dependencies == 0) {
        independent.push_back(after);
      }
    }
  }
}

Estamos listos. Lo que queda es poner orden a todo esto. Leemos el archivo, buscamos los primeros nodos independientes, resolvemos todo el grafo y luego simplemente respondemos las preguntas que nos hagan sin calcular nada más.

int main(int argc, char** argv) {
  string filename(argv[1]);
  loadFile(filename);
  loadIndependents();
  computeTimes();

  string line;
  while (getline(cin, line)) {
    size_t pos = line.find(',');
    size_t newPos;

    int task = atoi(line.substr(0, pos).c_str());
    cout << task << " " << minimun[task] << endl;

    while (pos != string::npos) {
      newPos = line.find(',', pos + 1);
      task = atoi(line.substr(pos + 1, newPos - (pos + 1)).c_str());
      pos = newPos;

      cout << task << " " << minimun[task] << endl;
    }
  }
}

Solución mejorada 

Las mejoras fáciles vienen por cambiar algunos vectores por listas, como before y after que siempre se recorren linealmente y cambiar independent por una cola o una pila (gracias por la idea de tener una pila, aunque en mi caso no es el mismo uso) para que los nodos que ya hemos visitado no ocupen espacio. durations y minimun en cambio deben ser vectores por su acceso aleatorio. Y en general, detalles respecto a C++ que debo seguir mejorando, principalmente con el parseo de datos y las iteraciones. Supongo que a fuerza de map y funcionales, en python este algoritmo debe escribirse más comprimido. A punta de Wikipedia me acabo de enterar que C++ tiene un map. Good to know. Maybe next time. El resto me parece bastante limpio (dentro de lo legible de C++) y creo que la aproximación por orden topológico es la adecuada para este problema. Sobre la solución recursiva (Actualización: 23-jun) A través de sus comentarios, me han dicho que la solución recursiva es admisible. Y quiero aclarar este punto aquí porque me parece bastante importante como para que quede guindando en los comentarios. La recursión efectivamente soluciona el problema. El volcado de pila que he comentado anteriormente es un problema real que se me ha presentado infinidad de veces en competencias como esta. Sin embargo, hasta ahora, siempre había usado Java como lenguaje de programación pues es el que conozco en mayor detalle y sospechaba que me podría encontrar con este problema. De allí que mi solución se fuese directamente a la estrategia bottom-up. Por otro lado, los programas escritos en C++ tienen unos límites distintos a los de Java o PHP, pues depende directamente del OS. En el caso de Java y PHP, si no modificamos esos parámetros (como algunos hicieron), los casos de test fallarán. Mi desconocimiento en C++ me hizo seguir con la suposición del problema de la pila. De todas formas, a manera pedagógica, creo que aporta más esa aproximación que la simple recursión. ¿Qué opinan sobre eso? He implementado la recursión en Java (para comprobar que sí hay un volcado de pila con los límites por defecto de la JVM) y luego en C++, donde sí funciona la recursión con los limites iniciales de mi MacBook. Así que considero conveniente compartir con ustedes la función recursiva implementada en C++. Con la recursión la clase Task queda así:

class Task {
public:
  vector before;
};

y debe cambiarse la carga de archivo para no guardar toda esa información extra que tenía. Mientras que las funciones loadIndependents y computeTimes desaparecen del juego, así como los vectores minimun e independent (durations sí hace falta). La función solve será entonces nuestra recursión y quedaría de la siguiente manera:

int solve(int task) {
  if(graph[task].before.size() == 0) {
    return durations[task];
  } else {
    vector& dep = graph[task].before;
    vector results(dep.size(),0);
    transform(dep.begin(),dep.end(),results.begin(),solve);
    return *max_element(results.begin(), results.end()) + durations[task];
  }
}

Y en vez de llamarla como preproceso, la llamaría directamente en el main:

cout << task << " " << solve(task) << endl;

Muchas gracias por todas las aportaciones. ¿Qué piensas? ¿Lo resolviste con una estrategia diferente? Y tú ¿en qué lenguaje lo resolviste?

19 thoughts on “Resolviendo el #TuentiContest: Problema 4 – Task Duration

  1. Se nota que el c++ no es tu fuerte. De todas formas, sí que el número de líneas es más alto… pero quizás no tanto. Hay cosas que se pueden hacer “más en c” y ganar eficiencia. Eso son cosas particulares del lenguaje.

    De todas formas, dada las características del archivo “in”, quizás no te diste cuenta de que las dependencias son casi todas “de anteriores a la actual”. Por lo tanto, en dos pasadas una (de 1->fin) y otra (de fin->1) resolviendo dependencias te resuelve todas.

    Yo me aventuré a eso asumiendo que el archivo “in” era invariable… se procesa y posteriormente se ejecuta en orden constante para cualquier dato de entrada… es decir, rechacé obviamente hacer (en este) recursión.

    Mi algoritmo: http://pastebin.com/ZRtuaxD5

  2. Efectivamente no lo es. Por eso me forcé en realizar varios problemas en ese lenguaje, pues es un ambiente controlado en el que conozco las respuestas y podía practicar un poco.

    El parseo es lo que se me da peor. Sigo explorando el API para encontrar las funciones más adecuadas. Sobre todo para pasar de string a número (que el atoi con c_str no me gusta) y definitivamente para tokenizar. Ya encontré el boost::tokenizer que ayuda un montón pero no me gusta que, o terminas haciendo un montón de typedefs y “using namespace”, o te tiras 3/4 de linea escribiendo encabezados de nombres de clase (ni hablar de cuando quieres un iterador). Supongo que es la costumbre de Java y Perl que es donde más me muevo actualmente.

    Lo del archivo se veía. Y apuesto a que fue porque Tuenti quiso un grafo inmenso y hacer el archivo automático, y se inventó lo que se inventó. Aún así preferí implementar la solución general para practicar un poco.

    ¿Qué te parece la explicación en prosa de la solución? Un poco extensa quizás pero me estoy enfocando más en las personas que aprenden algoritmos que en los que se saben las soluciones y quieran comparar código. Ellos siempre podrán bajar y ver la fuente y sobre todo comentar. Que la idea es que todos podamos aprender un poco.

    La solución 5 me tomará un tiempo pues hoy estaré ocupado, pero vendrá 😉 ¡Saludos!

  3. Como se nota quien sabe algoritmia y quien es un pobre PHPero que confía en la recursividad 😉

    Gran solución, sin duda es la única manera de que no reviente la ejecución con un grafo tan grande.

  4. Hola lagunex. Yo fuí uno de los que caí en la trampa de la recursividad. Esta claro que era necesario pasar el algoritmo a iterativo y para ello supongo que la mejor solución era resolver todo el grafo. Sólo una pregunta: quanto tardava tu programa para resolver todo el grafo?

    Un saludo!

      1. mi solución con recusividad era instantánea… 2seg a lo sumo… mmm… por eso no me metí más a fondo. Sabía que podía acarrear problemas, pero es lo más simple y si funciona es lo más limpio. Yo cargaba todo el fichero en un Array y luego accedía a el con una función estática recursiva. Estoy un poco sorprendido por lo que decís, así que a ver si le echo un vistazo porque mi ordenador no es que sea de la NASA.

        1. Hola yo.
          ¿Qué lenguaje utilizaste? No lo he reimplementado en Java pero en PHP me cuentan que se vuelca la pila y como la JVM usa una memoria y tamaño de pila por defecto (que se pueden ampliar) estoy suponiendo que también pasará. En mi experiencia personal, he visto que en este tipo de problemas siempre fuerzan la pila en los casos de prueba reales, pues es lo que hace interesante la solución. Quizás Tuenti fue un juez light.
          Sé que lenguajes como C, C++ y Perl usan todos los recursos que necesiten sin límite como los dos anteriores.
          Lo de la velocidad no me sorprende. Las dependencias entre nodos son pocas en el archivo in y varias tareas no pueden depender de la misma (por restricción del problema) así que la recursión no revisita nodos durante su ejecución.
          Te invito a que nos pongas un enlace a tu código para que le echemos un vistazo.
          Saludos.

          1. Hola de nuevo yo.
            He implementado la solución en Java y efectivamente provoca un volcado de pila con el tamaño de pila estándar de mi JVM (es una MacBook).
            Exception in thread "main" java.lang.StackOverflowError
            Por otro lado, lo he implementado en C++ y en ese caso la recursión se ejecuta perfectamente. Como te decía, C++ lenguaje consume todos los recursos que necesite y no tiene limitantes iniciales como PHP o Java.
            Por lo tanto, dependiendo del lenguaje sí puedes elegir el camino recursivo. Dicho esto, actualizaré la parte “Solución mejorada” para aclarar que en C++ sí se puede aplicar la recursión, mientras que en Java o PHP no (a menos que aumentes los recursos).
            Muchas gracias por tu aportación.

  5. Hola, en Java al hacerlo recursivo efectivamente da un StackOverflowError, a mi me pasó eso mismo y lo solucioné transformando el método recursivo en iterativo, usando una pila para simular la recursión, era algo que recordaba de 2º de carrera.

    http://pastebin.com/6AZ0sHwv método iterativeCalculation

    De todas formas, se puede aumentar el tamaño de la pila de java añadiendo el parámetro -Xss[Size] a la máquina virtual, que por defecto está a 512kb http://stackoverflow.com/questions/2127217/java-stack-overflow-error-how-to-increase-the-stack-size-in-eclipse

    salu2

  6. El problema de desbordamiento de la pila con una solución basada en recursividad existe también en C++ y puede resolverse dándole más memoria al programa. Realicé el programa en C++ y en Python (éste con límite de recursividad ajustable :P) y si me pasaba (quise calcular el tiempo del proceso 3) acababa el programa con un bonito “segfault”. Para solucionarlo, en sistemas Unix, existe la instrucción “ulimit”. Si se escribe en el terminal “ulimit -s” se puede ver el límite clásico de 8MB de memoria para el programa. Se puede cambiar éste límite fácilmente con “ulimit -s 100000″ por ejemplo. Una vez cambiado (y en el mismo terminal) la ejecución del programa acaba con éxito.

    1. Hola Thar.
      Sigo aprendiendo. Esto no lo sabía. Pensé que C++ era un desconsiderado sin control para la pila, como lo es para la memoria (aunque en realidad, todo eso son límites del OS, no del lenguaje). La solución recursiva que implementé en C++, luego de que nació todo este rollo de que si es posible o no, funcionó en mi portatil sin ajustar ese parámetro.
      He modificado algunos párrafos para ajustarlos a esta nueva información.
      Gracias por el dato.

Deja un comentario