Advent of Code 2018: segunda semana

Segunda semana del Advent of Code. En esta semana ya hemos tenido algunos problemas muy interesantes. Intentaré comentarlos de la mejor manera posible. Todo el código está aquí y en este otro post comenté mis soluciones de la primera semana.

Día 8

El día 8 se nos propone un problema de grafos también. Básicamente se nos define un árbol, donde cada nodo puede tener hijos y metadatos. En la primera parte nos piden sumar todos los metadatos.

Aquí al contrario que en el día 7, no voy a usar networkx. Era más difícil adaptar networkx al problema que hacer el árbol a mano. Uno de los puntos complicados de este problema es el parseo de la entrada, que hice de forma recursiva. Cada nodo es un diccionario con las propiedades tamaño, una lista de metadatos y una lista de nodos hijo.

En la segunda parte se define el concepto de valor de nodo y como calcularlo. También es bastante sencillo de implementar. Finalmente hacemos un recorrido por el árbol de tipo primero en anchura (BFS) con una deque de Python.

Día 9

Este día fue muy interesante. Se nos explica un juego, que consiste en ir añadiendo canicas en una circunferencia y cuando el número de canica que añadimos es múltiplo de 23, obtenemos puntos y quitamos una canica 7 puestos por detrás.

Aquí tuve una mala decisión de diseño ya que al principio quise hacer esto con una lista de Python (el equivalente a vector en otros lenguajes de programación). La idea era sencilla y funcionaba hasta que llegó la parte 2. La parte 2 te pedría calcular los puntos teniendo en cuenta 100 veces más canicas. Esto fue un grave problema para mi código. Calculo que tardaría 6 horas en calcularlo, pero antes optimicé. La optimización consistía en usar una lista circular doblemente enlazada. ¿Esto qué es? Se trata de una lista enlazada, doblemente, porque cada nodo tiene referencia al elemento siguiente y al anterior. Y es circular porque ambos extremos están unidos. Esto permite las inserciones y borrados en O(1). Además los movimientos relativos (en este problema todos son así) son extremadamente sencillos. La implementación de esta estructura de datos en Python es muy sencilla (en otros lenguajes es más complicado). No me molesté en hacer funciones que me hiciesen sencilla la vida y las conexiones/desconexiones las hago a mano directamente en el código del problema.

Curiosamente, en la propia librería de Python deque tiene una operación llamada rotate que permite hacer este problema en poquísimas líneas y de forma muy eficiente. Pero desconocía la existencia de esa función (que lo que hace es mover la “cabeza” de la lista enlazada que es deque).

Día 10

Este problema es muy interesante. Se nos da una serie de puntos que van moviéndose por la pantalla. En un determinado momento estos puntos se juntan y forman un mensaje en pantalla.

Aquí lo interesante no es mover los puntos, eso es trivial, simplemente es sumar la velocidad cada vez las coordenadas. Lo interesante es saber cuando parar. Existen varias ideas:

  • Revisión humana de cada iteración
  • Comprobar que no haya puntos separados del resto (con grafos)
  • Comprobar que el área de concentración de puntos es mínima

Y alguna más. Para el ejemplo la primera idea servía. Pero en la prueba real, era más complicado. A mí se me ocurrió la tercera opción, la cuál es bastante eficiente. En cada iteración calculamos el área que contiene a todos los puntos, cuando ese área ya no se reduce más, hemos llegado al mensaje.

La parte de dibujado me costó y ahí tuve un fallo que me costó media hora aproximadamente en resolver. Una mejor opción, pero que no se me ocurrió, hubiese sido usar Pillow y crear una imagen. Es mucho más fácil que dibujar sobre una terminal (y posiblemente más rápido).

Día 11

Para este problema hay 3 posibles algoritmos. En la primera parte nos piden que de una matriz extraigamos el cuadrado de 3×3 con mayor valor. La matriz hay que construirla pero es trivial. Yo decido usar un diccionario, con clave la tupla de coordenadas. Vamos recorriendo todas las posiciones y calculamos el valor. Ahora para buscar el cuadrado, simplemente vamos probando todos los posibles cuadrados.

En la segunda parte nos dicen que bsuquemos el cuadrado máximo pero el tamaño puede ser cualquiera. Aquí con la fuerza bruta ya tarda demasiado. Mi solución fue usar programación dinámica, para ello la clave pasa a tener un valor más, el tamaño del cuadrado. Cuando creamos la tabla estamos asignando valor al cuadrado 1×1 de posición X,Y. Representado es la tupla (x,y,1). Según vamos avanzando hasta 300×300 vamos guardando los resultados intermedios, de modo que podamos reutilizarlos. Por ejemplo, el valor de (x,y,4) solamente es la suma de (x,y,2), (x+2,y,2), (x,y+2,2) y (x+2,y+2,2). Evidentemente esto solo funciona en los tamaños pares. En los tamaños impares decidí coger el cuadrado de dimensión inmediatamente menor y calcular los laterales con los cuadrados de tamaño 1. Este sistema funciona mucho mejor que la fuerza bruta pero es lento. Los profesionales usaron el algoritmo Summed Area Table (del que desconocía su existencia). Este algoritmo es el óptimo para este problema.


Día 12

El día 12 me trajo recuerdos de un algoritmo con el que me peleé mucho, el denominado HashLife. El problema es un autómata celular unidimensional. Las reglas vienen dadas como patrones. La única diferencia es que hay que guardar su posición para luego calcular un número. La primera parte es bastante sencilla.

La segunda parte nos pedía lo mismo pero para el número ¡50000000000! Inmediatamente pensé en optimizarlo de forma similar a HashLife. La idea consiste en almacenar patrones mayores a los de las reglas (que son todos de tamaño 5), para poder evitar cálculos innecesarios.Además añadí un recolector de basura para ir eliminando por la izquierda las celdas inútiles.

No obstante, y aunque es muchísimo más eficiente, sigue sin ser capaz de procesar tal bestialidad de número en un tiempo razonable.

Y he aquí lo que me ha cabreado, porque no he podido sacarlo. A partir de cierto momento, el dibujo siempre es el mismo pero desplazándose a la derecha. De modo que el valor del siguiente paso siempre es la suma de una constante. Finalmente modifiqué el código para que buscase una situación en la que el número fuese resultado de una suma de una constante. Una vez hecho eso, calcula con una multiplicación lo que valdría cuando llegase a 50000000000.

Y con esto pude finalmente calcular el resultado.

Día 13

El día 13 teníamos unas vías de tren. En estas vías había unos trenecitos que se desplazaban siguiendo unas normas. El objetivo en la primera parte era conocer el donde se producía el primer choque.

Para esta parte ya decidí usar Pillow para mostrar la salida. Esto fue muy útil para la depuración. Por lo demás, volví a usar un diccionario para guardar coordenadas. De hecho, no se guardan las casillas que no son vías. Las vías se guardan en ese diccionario y los carritos en una lista. El problema define que los trenecito que se mueven antes son los que están más arriba y en caso de empate, los que están más a la izquierda. Esto es muy sencillo de hacer en Python ya que la ordenación del método sort es estable, lo que quiere decir, que en caso de empate, se respeta el orden original. En cada trenecito se guarda su coordenada, su dirección (hacia el sitio donde se va a mover en el siguiente turno) y su estado para la elección de dirección en los cruces.

La segunda parte pedía que ante una situación de muchos trenecitos, ¿en qué posición quedaba el último carrito? Esto es algo más complicado. Aquí fui bastante tonto y cometí un error al borrar los carritos de la lista, que hacía que todo se estropease. La manera correcta de hacerlo es anotar en una lista que trenecitos hay que quitar y una vez haya finalizado la iteración se eliminan los trenecitos.

Aprovechando las imágenes decidí generar una visualización de este problema. ¡Disfrutad los 20 minutos de puntitos moverse!

Día 14

El enunciado del día 14 es algo enrevesado pero básicamente se va generando una cadena de números ad infinitum. Tenemos que buscar los 10 elementos después de N posición. La solución de la parte 1 es bastante sencilla cuando se entiende el problema y se pueden usar sin problema listas normales de Python. En la parte 2 se pide lo contrario. Dado un patrón, encontrar la posición en la que aparece.

Aquí decidí usar la función find de str, que está optimizada para esto. No obstante, la cantidad es tan grande que no debemos comprobar todo si queremos que el programa acabe en un tiempo razonable. Para ello uso el argumento start y pido que solo busque entre los 10 últimos caracteres de la cadena. Tarde mucho en darme cuenta de esto y me desesperé bastante ya que no veía forma de optimizarlo más.

Conclusiones

Y con esto acabamos la segunda semana del Advnt of Code 2018. Estos problemas ya me están llevando mucho más tiempo y me estoy desesperando más con ellos. Lo que más rabia me da es que muchas cosas se me podrían haber ocurrido antes, ya que salvo el día 11, podía haber sabido perfectamente desde el principio la solución óptima.

La próxima semana los problemas serán más complicados y no estoy seguro de poder ofrecer mis soluciones a todos.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *