Resolviendo el #TuentiChallenge4: Challenge 4 – Shape shifters

Continuo compartiendo mi recorrido por el #TuentiChallenge4 con el cuarto problema. Historias aparte, en este caso nos dan una lista de estados, nos explican las transiciones entre ellos y nos piden encontrar la ruta más corta para llegar de un estado inicial a un estado final.

Análisis del problema

El planteamiento de este problema pertenece al ámbito de la Teoría de Grafos, específicamente a la tarea de encontrar el camino más corto entre un par de nodos. La forma de general de resolver este tipo de problemas es mediante el algoritmo de Dijkstra. Para este caso particular, también es posible resolver el problema implementando una búsqueda en amplitud o BFS por sus siglas en inglés (Breadth First Search). La búsqueda en amplitud recorre un grafo por capas. Es decir, partiendo desde el nodo incial primero visita todos los nodos a los que pueda llegar con una sola transición, luego todos los nodos a los que pueda llegar con dos, luego con tres, y así sucesivamente hasta que recorre todo el grafo. Entonces, nuestra estragia será simplemente recorrer nuestro grafo de estados hasta encontrar el estado final. Debido a que el recorrido será en amplitud, encontraremos el estado final con la mínima cantidad de transiciones.

Análisis alternativo

Que Dijkstra y BFS solucionen el problema no quiere decir que sean las únicas formas de solucionarlo (aunque sí son las más óptimas). Otra solución posible (y que de hecho fue la que eligió la mayoría de los participantes que han publicado sus soluciones) es realizar una búsqueda en profundidad o DFS (Depth First Search) revisitando un nodo si durante el recorrido se encuentra un camino más corto. Esta estrategia, aunque también consigue la solución deseada, tardará más en hacerlo.

Análisis incorrecto

Entre las soluciones que he revisado, hay una cuyo razonamiento puede que resuelva la entrada dada pero no ofrece una solución completa al problema. La estrategia fue leer de forma secuencial los estados y, partiendo desde el inicio, ir avanzando conforme se encontraban transiciones válidas en la entrada hasta llegar a la salida. El inconveniente aparecerá en el momento en que la ruta más corta te la pongan después de una alternativa larga. Allí la estrategia fallará. Lo mostraré con dos ejemplos, uno en el que el algoritmo funciona bien y otro en el que no. Ejemplo 1

AAA
ABZ
AAA
ABA
ABZ

Solución encontrada (correcta):

AAA->ABA->ABZ

Ejemplo 2

AAA
ABZ
AAA
ABA
ABC
ABZ

Solución encontrada (incorrecta):

AAA->ABA->ABC->ABZ

Solución enviada

Mi solución está hecha en Python, implementa BFS y separa la solución en tres etapas: construir el grafo, realizar el recorrido en amplitud y por último reproducir el camino más corto.

Hago un pequeño paréntesis en este párrafo para resaltar una gran aportación que han hecho en los comentarios. La primera parte de construir el grafo puede omitirse (tal como lo propone Pedro) para ir ampliando el grafo a medida que avanza la búsqueda en amplitud. Su análisis es muy interesante y resulta en una optimización significante dada la naturaleza del problema. Muchas gracias. 

Continuo entonces con mi solución. Para construir el grafo, iba leyendo la entrada línea a línea y verificaba si los estados cumplían la regla de transición (que la diferencia entre ellos fuese de un solo carácter). De ser así, agregaba las transiciones en las dos direcciones. Este es el método que añadía un nuevo estado al grafo:

def add_node(node, graph):
  if node not in graph: graph[node] = set() # first time

  # compute valid transitions
  for other_node in graph:
    if other_node == node: continue

    # diff('ACB','AXB') = [0,1,0]
    diff = [int(x!=y) for (x,y) in zip(node, other_node)]
    if sum(diff) == 1: # a transition is valid if only one nucleotid is changed
      graph[node].add(other_node)
      graph[other_node].add(node)
  return node

Luego de cargado el grafo, procedemos a recorrerlo con BFS hasta encontrar llegar al estado final. La cola que actualizo en la línea 13 es la que asegura que visitamos el grafo “por capas”

def bfs(begin, end, graph):
  queue = [begin]
  visited = set([begin])
  previous = {begin: None}

  # BFS Algorithm
  found = False
  while len(queue) > 0 and not found:
    node_from = queue.pop(0)
    neighbors = graph[node_from]
    for node_to in neighbors:
      if not node_to in visited:
        queue.append(node_to)
        visited.add(node_to)
        previous[node_to] = node_from
        if node_to == end:
          found = True
          break

Durante el recorrido en BFS vamos guardando en el diccionario “previous” el antecesor a cada nodo. Es decir, si podemos ir de A a B, previous[B] = A. Con esta estructura, podemos recuperar el camino más corto partiendo de previous[end] hasta llegar a begin. Inicialmente, el camino nos vendrá al revés (pues fuimos de end hacia atrás). Por eso aplicamos reverse al final para enderezarlo.

  # Backtrack to obtain shortest path
  path = [end]
  node = end
  while previous[node] != None:
    path.append(previous[node])
    node = previous[node]

  path.reverse() # Reverse the stack to get the order right
  return path

¡Listo! El resto del código simplemente lee la entrada e imprime el resultado. He decidido omitirlo para centrarme en la parte importante de la solución. Con respecto a las soluciones de los compañeros, he encontrado dos que me han gustado bastante:

Más allá de que seamos capaces o no de implementar ciertos algoritmos, el valor real de solucionar un problema está en reconocer la estrategia y utilizar las herramientas disponibles para resolverlo. Isaac, de manera muy inteligente, se valió de librerías ya implementadas en vez de escribir el código desde cero. Bravo.

Y tú ¿cómo lo resolviste?

5 thoughts on “Resolviendo el #TuentiChallenge4: Challenge 4 – Shape shifters

  1. Two observations for a slightly different implementation:

    1) For this specific problem, you can do BFS without building the graph explicitly.You can load all the “acceptable” states into a set in the beginning, and at each step in the BFS find all possible neighbors of the sequence and check if they are in the “acceptable” set.

    If there are C different characters in the alphabet (in our case C=4), with sequences of size L, each sequence has (C-1)*L possible neighbors. If there are V admissible sequences (i.e. the graph has V vertices), and for each of these we will need to check the (C-1)*L possible neighbors, the whole BFS takes O(V*C*L) steps.
    Contrast this with building the graph a priori in O(V^2 * L) followed by performing the BFS in O(V * L) and you can see that for C << V the implicit graph is a very good idea.

    2) As a lower-level optimization, representing the strings as numbers to serve as keys for the sets is a good idea. In our case, each character occupies a byte as a string but only needs to occupy 2 bits, allowing strings with L up to 32 to be represented in a long integer. Using integers, operations like "check if the sequence is in the set" have O(1) behavior instead of O(L).

    This is not too important if we build the graph a priori, as you did – even if we represent the nodes as integer values in the graph we shave the L factor off and have a BFS with O(V) but the runtime is still dominated by building the graph in O(V^2 * L).
    However… If we want to use the approach that does it with the implicit graph, building each of the neighbor strings (strings are immutable in python so O(L)) and checking if they are in a set of strings would be O(L) operations and it would increase the complexity to O(V*C*L^2). With integer representations, the sequence that is modified at a certain position can be obtained with a single addition and subtraction and checking membership in a set of integers is also an O(1) operation, so everything works well to keep the O(V*C*L).

    Solution at: https://github.com/pedrosorio/tuenti_2014/tree/master/prob04

    1. Thanks for the feedback Pedro.
      Interesting analysis on building the graph. I didn’t stop to think about it but your are correct. It is the perfect alternative for C < < V. I will update the post to add your reasoning on this during the day. Your low level optimizations are really nice. Actually, I’m planning to talk about you again on Challenge 5. I liked how you (and others as well) represented the Life board with a 64bit integer. I’m glad you are reading the posts :) I hope to read from you again soon.

Deja un comentario