Solución a “Los Callejones de Guanajuato”

Problema: Los Callejones de Guanajuato.

En este problema se nos está pidiendo que, dado un grafo conexo no dirigido, encontrar un camino tal que pasemos por todas las aristas.

Esta es una aplicación directa de un problema conocido de grafos, aunque no es tan común como otros problemas, estoy hablando de los ciclos Eulerianos.

Continue reading

Solución a “Splatoon”

Problema: Splatoon.

Este problema pide llevar a un inkling desde el inicio de una calle hasta el final siguiendo sus reglas de movimiento.

Ignoremos por un momento el hecho de que los inklings pueden pintar el piso y con ello alterar la calle en donde se realiza la carrera. Si los inklings no tuvieran esta habilidad, se puede hacer un algoritmo de fuerza bruta intentando todas las operaciones posibles, es decir, hacer una búsqueda en amplitud para encontrar el camino más corto, en donde el estado está representado únicamente por la posición en donde se encuentre el inkling.

Recuerda que en las búsquedas es importante marcar visitados para que la complejidad del algoritmo no se vuelva exponencial.

Para cada posición, se tienen dos posibles operaciones, saltar, o caminar, ambas toman 1 segundo y la distancia a la que se llega depende directamente del color sobre el que se está parado. El movimiento de saltar es muy fácil pues solo hay una casilla donde se puede caer, pero el movimiento de avanzar difiere cada vez pues depende directamente del color de las siguientes casillas.

Es posible hacer un ciclo para ver hasta donde puedes llegar avanzando desde la casilla en donde estás, y agregar a la búsqueda el lugar más lejano a donde puedas llegar. Sin embargo, si únicamente registramos la última casilla a donde se puede llegar, casos como el siguiente se nos escaparán:

En la solución superior, primero se avanza todo lo que se puede en la pintura naranja hasta llegar a la casilla azul, de ahi ya sea saltando o avanzando únicamente se puede llegar a la casilla blanca, y de ahí, no importa lo que hagas, te tomará dos segundos llegar al final.

En cambio, en la solución inferior, se avanza solo 3 casillas en la pintura naranja, lo cual es 1 casilla menos del máximo, de ahí se hace un salto el cual nos deja de nuevo en pintura naranja, desde donde podemos llegar caminando hasta el final en un total de tan solo 3 segundos, 1 segundo menos que la solución anterior.

Por lo tanto, no es suficiente visitar la distancia máxima, también hace falta visitar la distancia máxima – 1. Si intentamos hacer cosas similares con otro color de pintura, o más deteniéndonos todavía más atrás del máximo, no hay realmente ninguna ventaja, por lo que el caso presentado anteriormente es el único caso especial.

Una búsqueda en amplitud bien hecha que considere este caso sacará 30 puntos, una que no considere este caso sacará únicamente 5 puntos. Da perfectamente en tiempo y memoria porque a lo más tendremos un total de 1000 estados.
Sin embargo, la parte interesante de este problema es que los inklings son capaces de alterar el estado de la calle usando la pintura que traen en su tanque para poder recorrer más rápido la calle, utilizando hasta D disparos de tinta.

En este caso, necesitamos agregar una segunda dimensión al estado de nuestra búsqueda, ahora no sólamente es suficiente con guardar el lugar en donde estamos, sino que es necesario guardar también cuanta tinta queda en el tanque. En este caso, agregamos una operación más, la cual es pintar, la cual cuesta 0 segundos, nos avanza 0 casillas y nos quita una unidad D de pintura.

Si hacemos esto, nuestro espacio de búsqueda crece del N que era en la solución de 30 puntos, a N x D, lo cual es 1000 x 1000 y aún da en tiempo y memoria.

No obstante, la operación de pintar altera el mapa, por lo que si no guardamos también en el estado que las casillas siguientes ahora son de otro color, pintar no servirá de nada. Podríamos agregar una dimensión más a la búsqueda para considerar este caso, pero esto solo le agregaría complejidad innecesaria a la búsqueda.

La clave está en que pintar toma 0 segundos, por lo que podemos convertir la operación de pintar en una operación compuesta, que sea pintar y avanzar.

Pintar y avanzar toma 1 segundo, y nos permite avanzar 4 casillas hacia adelante siempre, por lo que hacer una operación de pintar y avanzar nos lleva del estado (i, d) al estado (i + 4, d – 1) con un costo de 1 segundo.

El detalle con esta solución, es que estamos ignorando de nuevo el caso especial explicado en la solución de 30 puntos, por lo que si se nos olvida que es posible ahorrarnos un segundo en ciertas ocasiones, sacaremos entre 35 y 90 puntos dependiendo de la implementación.

Para sacar los 100 puntos, es necesario agregar una operación más, la cual es pintar, avanzar y saltar, la cual nos lleva del estado (i, d),  al estado (i + 6, d – 1) con un costo de 2 segundos. Y como esta operación toma 2 segundos en vez de tan solo 1, no es suficiente con utilizar una cola común y corriente para hacer la búsqueda en amplitud, sino que es necesario utilizar una estructura de datos más avanzada, como una cola de prioridad o un montículo que nos ayude a ordenar los estados y elegir siempre con el tiempo más pequeño.

 

Solución a “Los Chocolates del Agente Nieves”

Problema: Los Chocolates del Agente Nieves

En este problema tenemos un tubo de chocolates los cuales se van a vender uno cada día, pudiendo vender únicamente los que están en ese momento en los extremos. El precio por vender un chocolate es igual al precio base de chocolate multiplicado por el número de días que se han vendido chocolates (empezando en 1).

El objetivo es encontrar la mayor ganancia posible al vender todos los chocolates.

 

Si lo quisiéramos resolver como una búsqueda, ¿qué tendríamos que considerar? En una búsqueda, nos importa obtener dos cosas, el espacio de búsqueda (es decir, cómo estará representado nuestro estado y qué valores puede tener), y las operaciones en nuestra búsqueda.

En cuanto a nuestros estados en la búsqueda, nos importa saber qué chocolates aún tenemos disponibles y cuántos días han pasado. Podríamos empezar teniendo N valores booleanos por cada chocolate y un número para saber cuántos días han pasado, por ejemplo, si tenemos 3 chocolates y aún no vendemos nada, tendríamos el estado (1, 1, 1, 1), si ya vendimos el primer chocolate, tendríamos (0, 1, 1, 2), si vendimos el tercer chocolate tendríamos (1, 1, 0, 2) y si vendemos los chocolates 1 y 2, tendríamos (0, 0, 1, 3). Sin embargo, esta representación es un poco inútil, ya que en el peor de los casos, tendríamos 1000 chocolates, lo cual hace un estado de 1000 posibles valores.

Podemos mejorar esto solo guardando únicamente los índices a los extremos del tubo, ya que ya sabemos que aún tenemos todos los chocolates entre estos dos valores. Eso transforma los estados anteriores a los siguientes estados respectivamente: (1, 3, 1), (2, 3, 2), (1, 2, 2). y (3, 3, 3). Esto vuelve al estado muchísimo más manejable, pues cada valor puede valer únicamente entre 1 y 1000.

Ya que tenemos nuestro estado, definimos las operaciones que hay que hacer para ir entre estado y estado, y estas operaciones son únicamente 2, vender el chocolate de la izquierda, o vender el chocolate de la derecha, si estamos en el estado (1, 3, 1) y vendemos el de la izquierda, nos lleva al estado (2, 3, 2), y si vendemos el de la derecha, nos lleva al estado (1, 2, 2). Podemos continuar estas instrucciones recursivamente sobre los estados que resulta y generar un árbol de búsqueda:

Una vez teniendo el árbol de búsqueda, podemos proceder a darle valor a cada uno de los nodos. Del nodo inicial (1, 3, 1), si decides vender el chocolate de la izquierda, obtendrás una ganancia igual a lo que te de el nodo (2, 3, 2) más el precio del chocolate 1 multiplicado por el número de días, que en este caso es 1, y si decides vender el chocolate de la derecha, la ganancia será lo que de el nodo (1, 2, 2) más el precio del chocolate 3 (múltiplicado por 1). De las dos opciones, tomaremos el máximo.

Llenemos ahora el resto del árbol de búsqueda con estos datos:

De aquí podemos ver dos cosas, la primera es que los nodos de hasta abajo, que son nuestros nodos hoja, tienen el mismo valor en el chocolate izquierdo como en el derecho, por lo que el valor máximo que podemos obtener de ellos es el precio de ese único chocolate por el número de días que llevamos. Y la segunda cosa es que tenemos nodos repetidos, por lo que cuando hagamos nuestra búsqueda, necesitamos guardar cálculos que ya hayamos hecho para no calcular un mismo estado más de una vez.

Nuestro árbol de búsqueda ya está terminado, así que es hora de convertirlo a una función matemática. Nuestra función recibe como entrada un estado, en este caso el chocolate más a la izquierda que nos queda, el más a la derecha y el nivel en el que estamos, y dado lo que aprendimos de nuestro árbol de búsqueda, regresará el siguiente valor:

Con esto, y considerando que debemos evitar repetir valores duplicados, es más que suficiente para resolver el problema con el método que más te guste, ya sea dinámica o memorización, aunque hay un pequeño problema para guardar los valores visitados.

Vamos a necesitar un arreglo de 1000 x 1000 x 1000 si es que queremos guardar un arreglo que se identifique de esta forma:

arreglo[izquierda][derecha][nivel]

Y esto es mucho más de lo que cabe en memoria, por lo que tenemos que encontrar una forma de reducir la memoria que necesitamos.

Lo que nos tenemos que dar cuenta es que la variable nivel es innecesaria, pues puede calcularse utilizando el número de chocolates que nos quedan en el tubo y el número de chocolates que teníamos originalmente:

nivel = total – chocolates_en_el_tubo + 1

Y para calcular el número de chocolates que nos quedan en el tubo solo se necesitan el índice del chocolate más a la izquierda, y más a la derecha, que ya tenemos en nuestro estado.

chocolates_en_el_tubo = derecha – izquierda + 1

Despejando:

nivel = total – derecha + izquierda – 1 + 1

nivel = total – derecha + izquierda

De esta forma, podemos eliminar el nivel de todos nuestros estados y cambiar el valor de nivel de todas las fórmulas por el valor de arriba. Esto simplifica nuestro arreglo de visitados de 1000 x 1000 x 1000 a un arreglo de tan solo 1000 x 1000, lo cuál es suficiente en tiempo y memoria.

 

Solución a “Temblor”

Problema: Temblor

Primero que nada, tratemos de entender qué es lo que se nos pide, pues es un problema poco tradicional: Dado un mapa de a lo más 4×4, hay que dar una serie de instrucciones que, sin importar en donde te encuentres en el mapa, logre llevarte a una salida; esta secuencia además, debe de ser la más pequeña posible.

Este es el caso de ejemplo:

mapa

La solución correcta es ONNEE, pues con esas instrucciones, podemos salir no importando en que lugar estemos (el lugar inicial está marcado con un punto rojo):

  • En el caso 1, las instrucciones ONN no hacen nada pues hay paredes, y las instrucciones EE nos sacan del mapa.
  • En el caso 2, ONN no hacen nada de nuevo y la primera E nos saca del mapa (la última E ya no importa).
  • En el caso 3, O no hace nada, pues hay pared, N nos sube un lugar, la segunda N no hace nada, y EE nos saca del mapa.
  • El caso 4, O nos lleva a la izquierda, donde se vuelve el mismo caso que el caso 3.
  • En el caso 5, O no hace nada, y NN nos lleva al caso 1.
  • Y finalmente, en el caso 6, O nos lleva al caso 5 y de ahí podemos salir.

Es mucho más fácil ver la solución si vemos a todos los olímpicos moverse al mismo tiempo:


Esto ejemplifica dos cosas: en primer lugar, el camino no debe de ser óptimo para cada uno, sino para todos en general, por ejemplo, el punto que inicia en la esquina superior derecha (cerca de la salida), podría salir yendo hacia la derecha, y saliendo en un único movimiento, pero si lo primero que hacemos es un “este”, estaremos complicando más las cosas para el resto de los olímpicos atrapados. En segundo lugar, puede haber más de un olímpico en un mismo lugar, y una vez que hay dos olímpicos en un mismo lugar, no importa realmente cuántos hay, sino que hay al menos 1 olímpico en ese lugar:

O bien, si lo vemos como unos y ceros:

Donde 1 significa hay al menos un olímpico ahí y 0 significa no hay ningún olímpico ahí.

Por lo tanto podemos concluir que nuestra tarea es convertir un tablero lleno de 1’s en un tablero lleno de 0’s.

 

A estas alturas, ya tenemos lo suficiente como para hacer una búsqueda en amplitud sobre el problema. Los estados de nuestro espacio de búsqueda están representados por un mapa de NxM lleno de 1’s y 0’s y las transiciones entre un estado y otro son las operaciones Norte, Sur, Este y Oeste.

Nuestro árbol de búsqueda empezaría más o menos así:

Solo tendríamos que hacer una búsqueda en amplitud hasta llegar al mapa con puros ceros y reconstruir la solución para resolver el problema.

Sin embargo, representar un mapa entero como un estado puede ser algo problemático, pues podemos tener hasta 16 casillas. Como puede haber un total de 2^16 estados, eso quiere decir que tendremos un arreglo de 17 dimensiones y estaremos usando 2^32 casillas de enteros, lo cual es completamente absurdo, pues aunque nos cupiera en memoria, dudo mucho que un compilador soporte tantas dimensiones y mucho menos que vaya a ser fácil manipularlas.

Lo que nos tenemos que dar cuenta es que como nuestro estado son únicamente 1’s y 0’s podemos olvidarnos de la representación del arreglo, pues podemos convertir cada estado en un número binario. Por ejemplo, a continuación presentamos diferentes mapas y su representación binaria:

Esto simplifica muchísimo nuestro espacio de búsqueda, ya que en vez de necesitar dieciséis enteros para representar un estado, ahora solo necesitamos 1, donde cada bit del estado representa una casilla del mapa.

La pregunta que nos tenemos que hacer ahora es si es posible representar todos los estados con nuestra representación numérica, y la respuesta es que sí, pues solo son hasta 16 casillas en el mapa, o lo que es igual a 16 bits, y sabemos que un entero en la mayoría de los lenguajes modernos soporta hasta 32 bits, por lo tanto nos alcanza y nos sobra para representar todos los enteros.

La siguiente pregunta que nos tenemos que hacer es si nos va a alcanzar la memoria. Y la respuesta también es sí, pues tenemos hasta 2^16 estados, lo cual es alrededor de 65,000 casillas, cada una de ellas puede guardar ya sea la operación que se hizo para llegar a ella, o el estado del que se llegó, ¡o incluso se pueden guardar ambas cosas! Pues solo necesitamos 16 bits para representar el estado de donde vienes y otros 2 para representar la operación que hiciste. Pero la implementación del problema ya se la dejamos a los competidores. En todo caso, necesitamos únicamente 65,000 enteros lo cual cabe en menos de 300 KB.

De esta forma, nuestro árbol de búsqueda se transforma, y se vuelve más fácil de manipular:


Una vez hecha la conversión con bits, esto se vuelve una búsqueda en amplitud común y corriente desde un número con NxM bits prendidos, hasta 0. Una búsqueda así debe de ser fácil de hacer para cualquier competidor.