Resolviendo el #TuentiChallenge4: Challenge 8 – Tuenti Restructuration

Hola, he aparecido.

La semana pasada estuve perdido pues me dediqué a añadirle funcionalidades a mi juego de Android. Si te gustan los números y los juegos de mesa, te invitó a descargar Lagunex Domino y jugar una partida, ya sea clásica o de muggins. Y ya puestos a la publicidad, también puedes seguirnos en @LagunexDomino para estar al día con las actualizaciones. Pronto estrenará nuevo diseño y un modo multijugador :)

Bueno, a lo que vinimos. El octavo problema fue el primer gran obstáculo de este año y debo confesar que me avergüenzo bastante por haberlo saltado. Lo entendí, sabía lo que me pedían (verás que el razonamiento es similar al problema 4) pero me encerré en una estrategia innecesaria dado el alcance del problema.

Sin embargo, como en internet podemos ser guapos, me atreveré a contarles el razonamiento y la solución correcta que acabo de escribir. Me he sacado el clavo.

Análisis del problema

Con un confuso planteamiento, nos piden reorganizar los puestos de los ingenieros en una mesa. Como restricción nos indican que el único movimiento permitido es cambiar dos personas que estén en puestos adyacentes (o entre un puesto vacío y uno adyacente). Por ejemplo en la siguientes mesas, los únicos cambios permitidos para las ‘O’ son los ilustrados por las ‘X’.

OX. | ... | ..X | .X.
X.. | .X. | ..O | XOX
... | XOX | ..X | .X.

De entrada, nos dan una disposición inicial de personas en la mesa y nos preguntan el mínimo número de movimientos que existen para llegar de esa disposición inicial a una disposición final dada. Por ejemplo:

ABC    ACB
DEF -> GHF 4 movimientos: B-C, D-G, E-H, E-I
GHI    DIE

¿Qué aspectos claves podemos ver en este planteamiento que ya hemos visto antes?

  1. Dan un estado inicial.
  2. Explican como poder ir de un estado a otro.
  3. Preguntan el camino mínimo entre dos estados

De aquí concluimos que es un problema de grafos y que puede resolverse de tres maneras: A* (y necesitamos una heurística admisible), Dijkstra y búsqueda por amplitud (BFS). En este caso, como todos los cambios tienen el mismo peso (un día), Dijkstra y BFS son equivalentes. Durante la competencia, no me detuve a pensar en las dimensiones del problema (grave error pues era un problema pequeño) así que elegí A* con una heurística incorrecta y lo que me tocó fue un desperdicio de tiempo durante toda la madrugada, cuando pude estar durmiendo feliz con mi esposa.

El problema de una heurística no admisible para A*

Al leer el problema la primera vez, lo primero que pensé fue en el taken. ¿Por qué? Pues cambias casillas adyacentes hasta encontrar un patrón. Además es un juego que me encanta desde niño, fue el primer proyecto de algoritmos en la universidad (allá por 2001), mi primer proyecto personal programando para un nokia con J2ME y el primero para BlackBerry con WebWorks y mi próximo juego para Android (lo modificaré un poco para darle sazón ;)).

El inconveniente con esa asociación es que la heurística típica que se usa para el taken no es admisible en este problema (sobre estima el camino óptimo). En taken se usa, como heurística de coste futuro, la suma de las distancias de Manhattan de todas las casillas incorrectas a su posición final. Veámos con un ejemplo por qué no es admisible y como afecta al algoritmo:

En el caso de prueba 10 nos dan los siguiente estados inicial y final

012    318
345 -> 746
678    502

Si utilizamos la distancia de Manhattan como heurística, encontramos dos “segundos pasos” con igual distancia g+h, donde g es el coste real hasta ese punto y h el coste futuro aproximado por la heurística:

012    312             312
345 -> 045 g:1 h:14 -> 645 g:2 h:12
678    678             078

                       312
                    -> 048 g:2 h:12
                       675

El primer camino nos devolverá un resultado de 10 pasos, que es incorrecto. El segundo camino nos devolverá 8 pasos. Debido a que la heurística está sobre estimando la solución (devuelve 14 y 12 cuando el mejor caso es 8), la información de las hipótesis es incorrecta. Ahora, si elegimos el primer camino como el de menor coste y el próximo a expandir, el algoritmo seguirá así:

012    312             312             312
345 -> 045 g:1 h:14 -> 645 g:2 h:12 -> 648 g:3 h:10
678    678             078             075

                       312
                    -> 048 g:2 h:12
                       675

Y a partir de aquí es el caos. A* seguirá el camino de menor coste g+h, con lo cual seguirá por el camino de arriba hasta encontrar la solución y entonces se detendrá en 10 pasos.

A pesar de la frustración de no haberlo resuelto en la competencia, este problema está genial como aprendizaje. Denota la importancia de que la heurística sea admisible en un algoritmo de A* a la vez que permite plantearse una opción más costosa, que es la de BFS, gracias a lo acotado que es el enunciado.

Dijkstra y BFS

Si observamos un poco las dimensiones del grafo, vemos que en una mesa de 3×3. La máxima cantidad de disposiciones distintas de los ingenieros en la mesa es 9!, que es 362.880. En memoria y en tiempo de ejecución 9! no es muy grande así que la complejidad de A* no era necesaria para el ámbito de este problema. Más aún, si vemos que todos los casos de este problema parten del mismo estado inicial, con calcular BFS una sola vez, ya tenemos las respuestas a todas las consultas que nos hagan.

El hecho de que todos los casos parten del mismo estado inicial puede no resultar obvio. Para ello, consideremos siempre nuestro estado inicial de la siguiente manera:

012
345 (puedes usar letras si te gusta más :P)
678

Y ahora aprendamos una correspondencia entre los nombres que nos dan y la posición que tienen. En el caso 10, la correspondencia sería:

0-Goran,   1-Einar, 2-Javier
3-Ignacio, 4-vació, 5-Bartek
6-Vincent, 7-Ivan,  8-Andrew

Luego, la posición final vendrá dada por la disposición de números que mantenga la correspondencia de nombres. En el caso 10 sería:

318
746
502

Con este razonamiento, cada problema se reduce a aprender la correspondencia de nombres con nuestro estado inicial e identificar la disposición del estado final. Y así nuestro grafo siempre empieza igual.

Solución correcta

Como ya te he comentado, este problema no lo envié, así que esta sección pasa a llamarse solución correcta. Se basa en el algoritmo de BFS según la estrategia explicada anteriormente. Como siempre, el problema lo divido en subproblemas más pequeños.

Primero, una función que dado un estado de la mesa, nos devuelva todos los estados adyacentes. Yo representé la mesa de 3×3 como una cadena de caracteres.

def swap(current_table,i,di):
  new_table = list(current_table) # switch from str to list
  new_table[i], new_table[i+di] = new_table[i+di], new_table[i]
  return ''.join(new_table) # return as a string

def neighbors(current_table):
  for index in range(len(current_table)):
    row,column = index/3,index%3
    if column > 0: yield swap(current_table, index, -1)
    if column < 2: yield swap(current_table, index, 1)
    if row > 0: yield swap(current_table, index, -3)
    if row < 2: yield swap(current_table, index, +3)

Luego la función de correspondencia para la disposición inicial

def read_current_table():
  inverse_index = {}
  rows = 3
  cur_index = 0
  for r in range(rows):
    names = raw_input().split(', ')
    for name in names:
      inverse_index[name] = str(cur_index)
      cur_index += 1
  return inverse_index

y la función de correspondencia para la disposición final.

def read_organized_table(inverse_index):
  desired_order = []
  rows, columns = 3, 3
  for row in range(rows):
    names = raw_input().split(', ')
    for column in range(columns):
      desired_order.append(inverse_index[names[column]])
  return ''.join(desired_order)

Ahora toca el recorrido BFS que nos devolverá el camino más corto desde la disposición inicial a cualquier otro estado

def bfs():
  initial_state = '012345678'
  distance = {initial_state: 0}
  queue = [initial_state]
  while len(queue) > 0:
    elem = queue.pop(0)
    for n in neighbors(elem):
      if n not in distance: # haven't being reached
        queue.append(n)
        distance[n] = distance[elem]+1
  return distance

Finalmente, el código que une todo lo anterior, lee la entrada y devuelve la solución

if __name__ == '__main__':
  distance = bfs() # bfs over all 9! states. takes a few seconds
  cases = int(raw_input())

  for case in range(cases):
    raw_input() # blank line
    inverse_index = read_current_table()
    raw_input() # blank line
    desired_order = read_organized_table(inverse_index)
    print distance[desired_order]

Para finalizar, felicidades a todos los que resolvieron exitosamente el problema. Como siempre, me toca elegir entre los códigos de los compañeros aquellos que me han gustado más. En esta caso fueron los sospechosos habituales Leo y Pedro. Leo, con su solución en Python, nos ofrece un código impecable que no necesita ni comentarios para entenderse y cuya solución se basa en la idea de BFS que he explicado en esta entrada. Pedro, quien lo resolvió con C++, fue un poco más aventurero y definió una heurística admisible para resolver el problema con A*. Como siempre, encontrarán buenas optimizaciones de bajo nivel en el código de Pedro, como su representación del tablero con un entero, escribiendolo de forma decreciendo para no tener problemas con un entero que empieza en cero.

Y tú ¿cómo lo resolviste?

3 thoughts on “Resolviendo el #TuentiChallenge4: Challenge 8 – Tuenti Restructuration

    1. Hola.
      Pues sí, dividir entre 2 la hace admisible. Usando el mismo ejemplo, el algoritmo seguiría por el camino de 10 pasos hasta llegar al quinto paso, donde f = g + h = 5 + 4 = 9 y a partir de allí consideraría otros caminos de menor coste.
      ¡Buena observación!

Deja un comentario