Resolviendo el #TuentiChallenge4: Challenge 7 – Yes we scan

Otra entrada más sobre soluciones del #TuentiChallenge4. En el problema 7 mantienen el ambiente de espionaje y ahora nos piden que interceptemos las comunicaciones de la gente para detectar si dos terroristas se han comunicado indirectamente.

Análisis del problema

El problema nos da un registro de llamadas en el cual cada línea del registro tiene la forma “X Y”, siendo X e Y números que representan a las personas involucradas en la llamada. Luego el problema nos pide identificar en qué punto del registro los terroristas “A” y “B” se han comunicado, así sea de forma indirecta. Por ejemplo, si el registro tiene esta forma:

0 1
1 2
4 5
2 3

Y nos piden el momento en el que los terroristas “0” y “3” se comunicaron, la respuesta sería en la cuarta llamada.

Fíjate que en ese momento, si quisiéramos agrupar las personas según si se han comunicado o no, tendríamos dos subconjuntos: {0,1,2,3} y {4,5}. Si pudiéramos crear esta partición de personas a medida que leemos el registro, podremos concluir que nuestro terrorista se han comunicado en el momento en el que ambos pertenezcan al mismo subconjunto.

Esta estructura de datos de conjuntos disjuntos (o partición que no sé por qué se complican tanto con los nombres, es como si a los teléfonos se llamaran “aparato tecnológico para comunicarnos bidireccionalmente con otra persona mediante la voz”) tiene una implementación específica que nos ofrece la manera más óptima de resolver el problema: el algoritmo de unión y búsqueda.

Aquí quisiera hacer un comentario generacional. Cuando hice la carrera, entre 2000 y 2006, nuestros referentes en algoritmo fueron los libros del profesor Cormen (si querías bastantes detalles) y el profesor Skiena (si te gusta más ir al grano) y ahora con la moda de Coursera (plataforma que me encanta y en la que creo firmemente) la fama se la ha llevado el profesor Sedgewick. Ojo que no es una crítica, el profesor Sedgewick tiene más que merecida la fama. Su curso está muy bien llevado, explica de forma excepcional todos los algoritmos y además hizo su doctorado en Quicksort. Yo lo he disfrutado un montón. Es solo un comentario.

Análisis alternativo

Otra solución a este problema, aunque menos óptima, es implementar una búsqueda en amplitud partiendo desde uno de los terrorista y parar cuando encontremos el otro, similar al problema 4. El inconveniente con esta aproximación es que debe leerse el grafo entero antes de ejecutar la búsqueda y que, si resulta que los elementos no pertenecen al mismo subconjunto, entonces debes recorrer el grafo entero para darte cuenta. Y ya pensando en alternativas, ofrezco una tercera variante que sería implementar Floyd-Warshall sobre el grafo y luego responder en tiempo constante si dos nodos están conectados.

Solución enviada

Una vez más, mi solución está implementada en Python. El algoritmo, como su nombre, tiene dos componentes principales, la unión y la búsqueda. A continuación, mi implementación de la unión (el método same_union lo definí para promover el encapsulamiento).

  def same_union(self, node0, node1):
    return self.find(node0) == self.find(node1)

  def union(self, node0, node1):
    if not self.same_union(node0, node1):
      union0 = self.find(node0)
      union1 = self.find(node1)
      self.unions[union0] = union1
    return self

La implementación es sencilla. Si dos elementos pertenecen a subconjuntos distintos, los uno. El método find es el que encuentra el identificador de cada subconjunto, su implementación es la siguiente:

class UnionFind():
  def __init__(self):
    self.unions = {} # contains nodes' partitions

  def find(self, node0):
    '''self.find(int) -> int
    returns the union that contains node0
    '''
    if not node0 in self.unions:
      self.unions[node0] = node0 # initially, all nodes are in their own union
    else:
      # iterate over all joined unions until we get to the root
      while node0 != self.unions[node0]:
        # optimize self.unions structure by transitivity
        # if A->B and B->C, then A->C
        parent = self.unions[node0]
        self.unions[node0] = self.unions[parent] # child now points to grandpa
        node0 = parent
    return node0

Esta tiene un poco más de jugo, pues es donde está la gracia de la optimización. Internamente, las particiones se representan como árboles y la forma de saber si dos elementos pertenecen a un mismo subconjunto es comprobando que pertenezcan al mismo árbol, es decir que ambos tengan la misma raíz. Lo que hago en las líneas resaltadas es aplanar (comprimir) el  árbol interno de manera que la altura sea 1 de manera que se reduzca la altura a la mitad, para que la próxima búsqueda sea en tiempo constante más rápida. Una mejor optimización es apuntar directamente todos los nodos a su raíz (lo que puede lograrse con una implementación recursiva), en vez de cada nodo a su abuelo.

Además, existe una optimización adicional denominada unión por rango, que consiste en unir el árbol de menor rango a la raíz del árbol de mayor rango. Esta optimización de hecho es más importante que la de compresión pues es la que asegura que no caigamos en el peor caso de construir una lista enlazada (en donde la búsqueda sería lineal y no logarítmica). Esto no lo tenía claro la primera vez que escribí la entrada (Pedro me ayudo a entenderlo) y por eso he tachado el resto del párrafo, que correspondía a la entrada original.  A mi me gusta esa optimización si consideramos como “rango” la altura del árbol. La implementación usada en la competencia (que es la enseñada en el curso del profesor Sedgewick) es contar la cantidad de hijos de un árbol como su rango. Yo no implementé esta optimización pues aplanar el árbol igual asegura una búsqueda en tiempo constante, por lo tanto contar la cantidad de hijos de un árbol se vuelve irrelevante.

El resto de la solución era simplemente leer la entrada y luego ir leyendo el registro de llamadas hasta que los terrorista se conectaran.

def obtain_connection(terroristA, terroristB, filename):
  call_logs = open(filename)
  union_find = UnionFind()
  connection = 'Not connected'
  for (index, call) in enumerate(call_logs):
    (begin, end) = [int(x) for x in call.split(' ')]
    union_find.union(begin, end)
    if union_find.same_union(terroristA, terroristB):
      connection = 'Connected at %d' % index
      break
  return connection

if __name__ == '__main__':
  terroristA = int(raw_input())
  terroristB = int(raw_input())
  print obtain_connection(terroristA, terroristB, sys.argv[1])

Entre las soluciones de los compañeros, las que más me gustaron fueron la de C++ por enviada por @SrXimo y Python enviada por Pedro Osorio. La de @SrXimo implementa la unión por rango y realiza la compresión de forma iterativa como yo. La de Pedro implementa la compresión del árbol de forma recursiva y la unión por rango, lo que la convierte en la solución más óptima. Hubo otra implementación en Java pero no me gustó porque para resolver el problema hizo una inicialización innecesaria que necesitaba de mucha memoria RAM para encontrar la solución.

Y entre los valientes encontré a @Dark_eye9, quien volvió a atreverse con bash. Y cómo dije en el problema 2, todo el que se atreve con bash a algo no tradicional, merece un aplauso por el esfuerzo. Reconozco que no me queda muy claro qué intenta hacer pero parece una búsqueda en amplitud. Dark_eye9, si te asomas por aquí, me encantaría que nos comentaras tu solución.

Y tú ¿cómo lo resolviste?

4 thoughts on “Resolviendo el #TuentiChallenge4: Challenge 7 – Yes we scan

  1. Once again a very nice blog post. A few observations:

    “Lo que hago en las líneas resaltadas es aplanar el árbol interno de manera que la altura sea 1″

    In fact you are applying path compression (the same I do) which iterates through the ancestors of the node you apply the find operation on and defines each node’s parent as its grandparent. This halves the tree height but it does not compress it to height 1.

    “Yo no implementé esta optimización pues aplanar el árbol igual asegura una búsqueda en tiempo constante, por lo tanto contar la cantidad de hijos de un árbol se vuelve irrelevante.”

    The algorithm Sedgewick presents has an amortized cost per operation given by the inverse of the Ackermann function (which can indeed be considered approximately constant). However, since you implement it without union by rank, and your tree does not have height 1, I believe your worst case amortized cost per operation is not constant but logarithmic [1] (which admittedly is more than enough for this problem).

    [1] This stackoverflow link has an answer that references a google book with the asymptotic complexity of your approach: http://stackoverflow.com/questions/2323351/union-find-algorithm-without-union-by-rank-for-disjoint-set-forests-data-structu

    1. Hi Pedro.
      Thanks for your observations. I saw the recursion in your code but missed the fact that you updated the parent variable as well. I’ve updated my post.
      I also missed the purpose of each optimization completely the first time. Now I get it, and I agree that union by rank is more important than path compression.
      Don’t stop reading :) I’ve learned a lot from your feedback.

      1. Your posts are really good. I will not stop reading for sure. I would say that union by rank and path compression are both “equally important” in some sense. But since path compression can only compress a specific path in the tree for each find operation, even if all nodes in that path are pointed to the root, if we join sets in the “wrong order” the performance is worse than ideal as you pointed out (amortized log(n) per operation).

  2. Hola gente!

    Pues sí, mi solución consiste en una búsqueda en anchura. Aunque he de reconocer que se me ocurrió el algoritmo por mi sólo, ya que carezco de conocimientos de algorítmica. Ver ahora que este algoritmo es el famoso BFS tan oido por todo el concurso me deja sorprendido 😉

    Básicamente lo que pensé es que si se trataba de búsquedas en archivos gigantes, nadie es tan rápido buscando como grep. Así que formo un array en el que voy almacenando los sospechosos “suspects”, al que primero añado el segundo terrorista.

    Después formateo un poco la salida del array para que me cuadre con el formato de las regex extendidas de grep: “valor1|valor2|valor3|valor4″ así grep me buscará en el archivo cualquiera de esos valores.

    1ª Pega: Grep es muy rápido, si, pero cuando tiene que buscar 9000 números de 9 cifras en un archivo gigante, no tanto.

    1ª Optimización: Usar fgrep, que busca sólo los strings enteros y por tanto es más eficiente. El problema es que hay que adaptar el array a que sea una lista de teléfonos separados por \n. Y luego metérselo por sustitución de procesos (http://carloslindado.wordpress.com/2013/04/05/sustitucion-de-comandos-y-sustitucion-de-procesos-en-bash/).

    Bueno que después de que fgrep arroje los sospechosos de haber hablado con el terrorista, los añado al array de sospechosos. Así voy buscando cada vez más gente hasta que alguien resulte haber hablado con el otro terrorista.

    También uso las opciones del grep para que me arroje la línea donde existe la conexión, número que extraigo usando awk e inserto en la cadena ‘Connected at $1′

    Para la condición de parada usaba el conteo de la gente que actualmente estoy buscando, si no hay conexión, se supone que he de llegar a un punto donde mi lista de sospechosos no crezca más porque he recorrido todo el árbol ya.

    Resultaba bastante lento por el hecho de que se hace pesado buscar tantos strings a la vez, y sumado a la lentitud de bash… Pues tardé como 7 minutos en pasar el test. Una optimización creo que hubiese sido almacenar en el array sólo la generación de sospechosos actual, no todas :/

    Si hay algo que queráis preguntar, sentíos libres!

Deja un comentario