lhchavez/comesolo.txt

## comesolo.txt
Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.

La solución del problema es bastante sencilla de explicar: haz una búsqueda en profundidad intentando todos los posibles movimientos por fuerza bruta hasta que te salga una solución aceptable e imprímela. El problema es que esta estrategia es $O(n!)$, y como $n$ puede valer hasta 30x30, puedes esperar que el programa corria varios milenios antes de encontrar la solución óptima. Hay tres trucos (en orden de importancia) para obtener una solución decente en un tiempo razonable:

* No repetir estados.
* No "clavarse" con soluciones que parece que son muy buenas, pero en realidad llevan a callejones sin salida.
* Encontrar una manera de darle prioridad a los estados que tengan más probabilidad de llegar a una solución buena.

La estrategia que yo personalmente seguí fue que cada que encontraba un nuevo estado, obtenía su <a href="http://es.wikipedia.org/wiki/Funci%C3%B3n_hash">hash</a> (que resultaba en un entero de 64 bits) y verificaba si no lo había visitado usando una tabla de hash<sup><a href="#note">*</a></sup>. Si no la había visitado, encontraba todos los estados vecinos (todos los tableros que resultaban de hacer un movimiento válido) y los guardaba en una fila de acuerdo a la cantidad de puntos (entre más puntos, más adelante en la fila). Luego, elegía aleatoriamente un estado de la fila dándole prioridad a los que estaban más adelante (pues son los que tienen mayor probabilidad de llegar a una buena solución), lo cual también me evitaba seguir un único camino donde me podría atorar. Repetí eso hasta que se me terminó la memoria de la computadora e imprimí la mejor solución.

A continuación, el pseudocódigo de la solución:

  class Estado:
    int puntos = 0
    bool[N][N] tablero
    Estado padre = null

    def __init__(Estado p):
      puntos = p.puntos
      tablero = p.tablero
      padre = p

    def hash():
      # Puedes usar cualquier algoritmo que genere un entero de 64 bits
      # a partir de tablero y puntos. Este es el más sencillo.
      hash = puntos
      for i in range(0, N):
        hash = ((hash << 7) | (hash >> 53)) ^ tablero[i]
      return hash

    def siguientes(queue[300] colas):
      # Para todas las celdas (i, j) del tablero...
      for i in range(0, N):
          for j in range(0, N):
            # Si la celda tiene una pieza...
            if tablero[i][j]:
              # Para todos los vecinos contiguos (i+k, j+l)...
              for k in range(-1, 2):
                for l in range(-1, 2):
                  # Asegúrate que se haya movido _algo_.
                  if k == 0 && l == 0: continue
                  # Y que pueda brincar dentro del tablero.
                  if j + 2 * l < 0 or j + 2 * l >= N: continue
                  # Y que haya brincado una pieza.
                  if not tablero[i + k][j + l]: continue
                  # Y que el lugar a donde brinca esté desocupado.
                  if tablero[i + 2 * k][j + 2 * l]: continue

                  hijo = new Estado(this)
                  # Aumenta la puntuación del hijo
                  hijo.puntos++
                  # Borra la ficha original y la "comida".
                  hijo.tablero[i][j] = hijo.tablero[i + k][j + l] = False
                  # Agrega la ficha en su posición final.
                  hijo.tablero[i + 2 * k][j + 2 * l] = True
                  # Agrégala a la cola correspondiente.
                  colas[hijo.puntos].push(hijo)

  def elige_estado():
    # Número aleatorio entre 0 y 1.
    r = (random() / (float)RAND_MAX)
    # El índice de la última cola que estuvo llena.
    ultimolleno = -1
    # La cola que se está considerando.
    x = 0
    # Elige la cola con mayores puntos que no esté vacía como
    # primera opción.
    for i in range(0, N):
      if not colas[i].vacio():
        x = i
    # La primer cola tiene probabilidad de 31% de ser elegida.
    # La segunda cola tiene probabilidad de 21%, la tercera 14%,
    # la cuarta 10% y así sucesivamente.
    while x >= 0:
      if not colas[x].vacio():
        ultimolleno = x
      x--
      r *= 1.45
      if r >= 1 and ultimolleno != -1 break
    if ultimolleno == -1: return Null
    return colas[lastfull].pop()

  queue[300] colas
  hashtable<int64> estados_visitados

  # lee el estado original
  colas[0].push(estado_original)
  Estado mejor = estado_original

  while no_se_haya_terminado_la_memoria():
    Estado s = elige_estado()
    # Si ya no hay más estados por visitar,
    # encontramos la respuesta óptima en algún punto.
    if s == Null: break
    # Actualiza |mejor| si hay una respuesta mejor.
    if mejor.puntos < s.puntos: mejor = s
    # Repetir estados es malo.
    if s.hash() in estados_visitados: continue
    estados_visitados.add(s.hash())
    # Agrega todos los vecinos.
    s.siguiente(colas)

  # A partir de este punto, |mejor| contiene la mejor solución. Podemos saber
  # qué movimiento se hizo para llegar a él comparando las diferencias entre el
  # tablero de |mejor.padre| y |mejor|. Ya solo es cuestión de imprimir el resultado
  # y listo.

<sup><a name="note">*</a></sup> Aquí mucha gente se va a quejar porque solo guardar el hash abre la puerta a que haya dos estados que puede tener hasta 900 bits que tengan el mismo hash de 64 bits (por el <a href="http://es.wikipedia.org/wiki/Principio_del_palomar">principio del palomar</a>) y esté considerando que ya visité un estado que en realidad es nuevo. Si haces las cuentas, la probabilidad de colisión es negligible: la cantidad de estados que podía visitar en mi computadora (27 millones) es significativamente más pequeña que el número de estados necesarios para que la probabilidad de colisión sea de 1% ($\approx 10^135$, por la <a href="http://es.wikipedia.org/wiki/Paradoja_del_cumplea%C3%B1os">paradoja del cumpleaños</a>).
	Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.

	La solución del problema es bastante sencilla de explicar: haz una búsqueda en profundidad intentando todos los posibles movimientos por fuerza bruta hasta que te salga una solución aceptable e imprímela. El problema es que esta estrategia es $O(n!)$, y como $n$ puede valer hasta 30x30, puedes esperar que el programa corria varios milenios antes de encontrar la solución óptima. Hay tres trucos (en orden de importancia) para obtener una solución decente en un tiempo razonable:

	* No repetir estados.
	* No "clavarse" con soluciones que parece que son muy buenas, pero en realidad llevan a callejones sin salida.
	* Encontrar una manera de darle prioridad a los estados que tengan más probabilidad de llegar a una solución buena.

	La estrategia que yo personalmente seguí fue que cada que encontraba un nuevo estado, obtenía su <a href="http://es.wikipedia.org/wiki/Funci%C3%B3n_hash">hash</a> (que resultaba en un entero de 64 bits) y verificaba si no lo había visitado usando una tabla de hash<sup><a href="#note">*</a></sup>. Si no la había visitado, encontraba todos los estados vecinos (todos los tableros que resultaban de hacer un movimiento válido) y los guardaba en una fila de acuerdo a la cantidad de puntos (entre más puntos, más adelante en la fila). Luego, elegía aleatoriamente un estado de la fila dándole prioridad a los que estaban más adelante (pues son los que tienen mayor probabilidad de llegar a una buena solución), lo cual también me evitaba seguir un único camino donde me podría atorar. Repetí eso hasta que se me terminó la memoria de la computadora e imprimí la mejor solución.

	A continuación, el pseudocódigo de la solución:

	class Estado:
	int puntos = 0
	bool[N][N] tablero
	Estado padre = null

	def __init__(Estado p):
	puntos = p.puntos
	tablero = p.tablero
	padre = p

	def hash():
	# Puedes usar cualquier algoritmo que genere un entero de 64 bits
	# a partir de tablero y puntos. Este es el más sencillo.
	hash = puntos
	for i in range(0, N):
	hash = ((hash << 7) \| (hash >> 53)) ^ tablero[i]
	return hash

	def siguientes(queue[300] colas):
	# Para todas las celdas (i, j) del tablero...
	for i in range(0, N):
	for j in range(0, N):
	# Si la celda tiene una pieza...
	if tablero[i][j]:
	# Para todos los vecinos contiguos (i+k, j+l)...
	for k in range(-1, 2):
	for l in range(-1, 2):
	# Asegúrate que se haya movido _algo_.
	if k == 0 && l == 0: continue
	# Y que pueda brincar dentro del tablero.
	if j + 2 * l < 0 or j + 2 * l >= N: continue
	# Y que haya brincado una pieza.
	if not tablero[i + k][j + l]: continue
	# Y que el lugar a donde brinca esté desocupado.
	if tablero[i + 2 * k][j + 2 * l]: continue

	hijo = new Estado(this)
	# Aumenta la puntuación del hijo
	hijo.puntos++
	# Borra la ficha original y la "comida".
	hijo.tablero[i][j] = hijo.tablero[i + k][j + l] = False
	# Agrega la ficha en su posición final.
	hijo.tablero[i + 2 * k][j + 2 * l] = True
	# Agrégala a la cola correspondiente.
	colas[hijo.puntos].push(hijo)

	def elige_estado():
	# Número aleatorio entre 0 y 1.
	r = (random() / (float)RAND_MAX)
	# El índice de la última cola que estuvo llena.
	ultimolleno = -1
	# La cola que se está considerando.
	x = 0
	# Elige la cola con mayores puntos que no esté vacía como
	# primera opción.
	for i in range(0, N):
	if not colas[i].vacio():
	x = i
	# La primer cola tiene probabilidad de 31% de ser elegida.
	# La segunda cola tiene probabilidad de 21%, la tercera 14%,
	# la cuarta 10% y así sucesivamente.
	while x >= 0:
	if not colas[x].vacio():
	ultimolleno = x
	x--
	r *= 1.45
	if r >= 1 and ultimolleno != -1 break
	if ultimolleno == -1: return Null
	return colas[lastfull].pop()

	queue[300] colas
	hashtable<int64> estados_visitados

	# lee el estado original
	colas[0].push(estado_original)
	Estado mejor = estado_original

	while no_se_haya_terminado_la_memoria():
	Estado s = elige_estado()
	# Si ya no hay más estados por visitar,
	# encontramos la respuesta óptima en algún punto.
	if s == Null: break
	# Actualiza \|mejor\| si hay una respuesta mejor.
	if mejor.puntos < s.puntos: mejor = s
	# Repetir estados es malo.
	if s.hash() in estados_visitados: continue
	estados_visitados.add(s.hash())
	# Agrega todos los vecinos.
	s.siguiente(colas)

	# A partir de este punto, \|mejor\| contiene la mejor solución. Podemos saber
	# qué movimiento se hizo para llegar a él comparando las diferencias entre el
	# tablero de \|mejor.padre\| y \|mejor\|. Ya solo es cuestión de imprimir el resultado
	# y listo.

	<sup><a name="note">*</a></sup> Aquí mucha gente se va a quejar porque solo guardar el hash abre la puerta a que haya dos estados que puede tener hasta 900 bits que tengan el mismo hash de 64 bits (por el <a href="http://es.wikipedia.org/wiki/Principio_del_palomar">principio del palomar</a>) y esté considerando que ya visité un estado que en realidad es nuevo. Si haces las cuentas, la probabilidad de colisión es negligible: la cantidad de estados que podía visitar en mi computadora (27 millones) es significativamente más pequeña que el número de estados necesarios para que la probabilidad de colisión sea de 1% ($\approx 10^135$, por la <a href="http://es.wikipedia.org/wiki/Paradoja_del_cumplea%C3%B1os">paradoja del cumpleaños</a>).