Advent of Code 2018: primera semana

Este año, como ya viene siendo habitual, tiene lugar la competición de programación Advent of Code. El objetivo es resolver un problema de programación al día, hasta el día de navidad, a modo de un particular calendario de adviento. Este año, como ya no viene siendo tan habitual, me he propuesto hacerlos todos y explicar mis soluciones. Esta semana todos han sido resueltos en Python.

Los programas que he usado, así como los enunciados y los datos de entrada que me han tocado (a cada uno le tocan datos diferentes) están en este repositorio de GitHub.

Día 1

El primer reto que nos proponen es muy sencillo. Se nos pasa un archivo con sumas y restas y tenemos que calcular el resultado final. Pongamos un ejemplo trivial:

+1, +1, -2 = 0

El procesdimiento es sencillo, leer cada operación, extraer el signo, convertir a número y aplicar la operación detectada por el signo.

La segunda parte es más interesante, ya que nos dice que tenemos que aplicar la misma cadena de operaciones de forma indefinida hasta encontrar una resultado repetido.

Aquí la clave es conocer el funcionamiento de un Set o conjunto. Se trata de una estructura de datos que no permite elementos repetidos. La idea está en ir almacenando los resultados que van saliendo hasta encontrar uno que ya esté dentro. Al encontrarlo salir e indicarlo.

Aquí viene una anécdota interesante. Estoy haciendo estos retos con unos amigos en un grupo de Telegram y al poco de yo haberlo terminado empezaron a preguntar cuánto tardaba en ejecutarse la segunda parte. Al parecer les iba muy lento, yo sorprendido les dije que había sido instantáneo y que estaba usando Python. Ellos se preguntaban como podía ser, ya que lo habían hecho en C y les estaba tardando varios minutos.

Una representación de un set o conjunto. No puede haber elementos repetidos. No existe orden definido

La respuesta tiene que ver con el set. Yo sinceramente fui a él directamente pero otros compañeros no, y usaron listas y arrays. La búsqueda que realizaban para saber si el elemento estaba dentro era lineal. Comparada con la búsqueda en un set implementado con tabla hash que es constante, el rendimiento es muy inferior. He aquí un ejemplo de como lo más importante de cara a la eficiencia es el algoritmo y las estructuras de datos que usamos para resolver un problema.

Día 2

El segundo día se nos propone otro problema de dificultad similar. Sobre una lista de palabras tenemos que contar cuantas palabras tienen 2 letras repetidas y 3 letras repetidas, para finalmente multiplicar ambos números.

En este caso fui bastante pragmático y opté por usar la clase Counter de Python. Counter cuenta cuantas veces aparece una letra y lo deja en un diccionario. Podemos ignorar las claves, ya que lo único que tenemos que hacer es buscar en los valores si está el 3 y el 2, y si es así, sumar uno a nuestro contador.

La segunda parte ya es más interesante. Se nos pide que la misma lista de palabras, encontremos las dos palabras que solo se diferencian en una letra (se tiene en cuenta el orden). Aquí el algoritmo es un poco más lento ya que para cada palabra la comparamos con el resto de palabras, hasta encontrar aquella que efectivamente tiene un cambio de únicamente una palabra.

Para ello hace falta una función que nos diga cuantas palabras hay de diferencia entre dos palabras, que es bastante sencillita.

Una vez tengamos las dos palabras que solo se diferencian en una letra, hacemos un bucle similar al usado para encontrarlas, solo que esta vez para formar la palabra con todas las letras que tienen en común, ignorando la diferente.

Día 3

En el día 3 nos proponen un problema muy interesante. Tenemos una lista de parcelas rectangulares, definidas por la posición de su esquina superior-izquierda y su ancho y alto, todo en metros. Para la primera parte tenemos que encontrar cuantos metros cuadrados del universo ficticio están en dos o más parcelas a la vez.

Lo primero que hay que hacer es leer la entrada, que esta vez ya no es tan trivial. Un simple RegEx nos permite obtener toda la información de forma sencilla.

Para el algoritmo en sí, vamos a usar defaultdict. La idea es tener una tabla hash, cuya clave sean las coordenadas del mundo y su valor, el número de parcelas que estan sobre ella. Usamos defaultdict para que por defecto cualquier coordenada que no existiese con anterioridad tenga valor 0.

Así pues vamos a recorrer todas las parcelas y para cada parcela vamos a visitar todos los metros cuadrados que contiene en la tabla hash, sumando 1 para indicar que ese metro cuadrado pertenece a una parcela (más).

La segunda parte nos indica que solo existe una parcela que no esté invadida por otra parcela. Hay que buscar cuál es e informar del ID que tiene. Para esto he simplemente vuelto a recorrer cada parcela comprobando si tienen algún metro cuadrado con uso por más de 1 parcela. Si para una parcela no se encuentran metros compartidos, automáticamente se devuelve su ID (ya que solo hay una parcela de estas características).

El código completo es el siguiente:

En esta segunda parte, tengo la intuición de que existe una manera más eficiente de hacerlo, pero todavía no he encontrado esa solución más eficiente.

Día 4

El problema del día 4, aunque aparentemente distinto al anterior, tiene muchas cosas en común y mi forma de resolverlo fue bastante parecida.

Se nos pide que sobre un registro de todas las noches identifiquemos el guardia que duerme más horas, y posteriormente su minuto preferido para quedarse dormido.

En primer lugar, la entrada de texto ya es bastante más compleja, pero con unos simples regex se puede analizar rápidamente, al menos para extraer la información que necesitamos. Aquí conviene prestar atención a que los registros de dormirse y despertarse ya que todos ocurren a la misma hora, luego lo único importante son los minutos. Otro detalle respecto a la entrada es que nos indican que está desordenada, sin embargo el formato de representación de la fecha que nos dan (parecido al ISO), se ordena cronológicamente simplemente con una ordenación alfabética.

La idea es muy similar a la del algoritmo anterior, primero tenemos una tabla hash con todos los guardias. Allí almacenamos otra tabla hash con los minutos de la hora y ponemos un cero si nunca se han dormido en ese minuto. Si usamos defaultdict, como en el código anterior, el código se simplifica bastante. En definitiva estamos usando dos tablas hash en vez de una y aplicar la misma idea de sumar 1, salvo que esta vez con el tiempo en vez del espacio (aunque Einstein vino a decir que eran cosas muy parecidas).

Posteriormente se recorren estas tablas hash para calcular lo pedido.

La segunda parte nos pide algo similar pero no idéntico, el guardia que se ha quedado dormido más veces en el mismo minuto (e indicar que minuto es).

La estructura de datos es exactamente la misma y solamente añadimos otro bucle para que busque este otro dato:

En este caso, la segunda parte apenas ha implicado modificaciones, siendo la estructura de datos subyacente intacta.

Día 5

Este día se nos propone un reto aparentemente sencillo, pero cuya resolución puede ser muy lenta o rápida dependiendo de como lo hagamos. He de decir, que mi solución era muy lenta, extremadamente y tuve que mirar como lo habían hecho otras personas para entender como se podía optimizar.

La primera tarea consiste en reducir unas cadenas de reactivos. La norma es que si hay una letra minúscula y una mayúscula al lado, se pueden quitar. Se nos pide la longitud de la cadena de reactivos después de reducirlo al máximo.

La versión original consistía en ir realizando elimaciones sobre la propia lista. Todo ello en un bucle que para cuando en una iteración no se modifica la cadena. Esto es extremadamente ineficiente. Tomando el código de Peter Tseng, existe una opción mejor. Se puede ir haciendo un string nuevo poco a poco comprobando si la nueva letra reacciona con la última del string nuevo. Esto tiene la ventaja de que solo hace falta una iteración para cubrir todas las reacciones. La versión mejorada es la siguiente:

Para la segunda parte se nos pida que encontremos la letra, que si eliminamos del compuesto antes de empezar la reacción, genera la cadena más pequeña. Hay que probar con todas las letras, mención especial a string.ascii_lowercase que tiene un iterador con todas las letras minúsculas del alfabeto inglés. Y posteriormente, encontrar la que de resultado inferior. Como no nos pide la letra, solamente la longitud que tendría esa cadena, no tenemos que pasar información extra.

Día 6

Esto se empieza a complicar. El día 6 nos pide que sobre una cuadrícula encontremos qué punto de control está más cercano a esa posición. De los puntos de control que un número de cuadrículas cercanas finitas, encontrar cuántas cuadrículas tiene el punto de control con más cuadrículas asociadas. Para saber la distancia de una cuadrícula al punto de control se usa la distancia de Manhattan.

Lo primero es reconocer que puntos de control tienen áreas infinitas, para no tenerlos en cuenta.

Para ello, voy a calcular dos puntos extremos (esquina superior izquierda y esquina inferior derecha), dentro del rectángulo que forman estos puntos están contenidos todos los puntos de control. El objetivo es calcular las distancias de las cuadrículas justo por fuera de este rectángulo. Las cuadrículas que estén más lejos de eso no van a cambiar de punto de control, ya que el más cercano en el borde seguirá siendo el más cercano en el borde + N, ya que no hay más puntos de control fuera.

Posteriormente, empezamos a calcular las distancias de todos los puntos de la cuadrícula. Para almacenar los datos vuelvo a usar una tabla hash (defaultdict de Python), donde la clave es la coordenada X,Y y el valor es el punto de control más cercano a esa cuadrícula. Si dos puntos de control están a la misma distancia o no se ha calculado, se usa -1.

Cuando se ha calculado el punto de control más cercano, se revisa si ese punto estaba fuera del rectángulo que contiene a los puntos de control. Si está fuera, el punto de control pasa a un conjunto de puntos con infinitas cuadrículas cercanas.

Para el conteo de cuántas cuadrículas tiene un punto de control que sabemos que es finito, uso otra tabla hash, inicializada por defecto a 0, cuya clave es el identificador de punto de control y su valor, el número de cuadrículas. Después, de los valores almacenados se calcula el máximo.

En la segunda parte nos dicen que hay una región de puntos cuya suma de distancias a todos los puntos de control es menor a 10000. ¿Cuántos puntos forman esta región? Aquí creo que el enunciado no fue demasiado claro, ya que en un principio pensé que podría haber varias áreas, o que podría haber puntos sueltos, no conectados a la región. Sin embargo eso no pasa. Yo diseñé un algoritmo que iba visitando las celdas adyacentes, pero en realidad no hacía falta, simplemente se puede contar cuantos puntos cumplen la condición. Y se puede hacer en el mismo bucle que la primera parte.

Día 7

El día 7 se nos propone un reto muy interesante. En primer lugar, tenemos una lista de tareas que hacer en orden. Cada tarea depende de que otras hayan finalizado. Se nos pide el orden en el que se deberán hacer. Para resolver esto vamos a usar una estructura de datos nueva, el grafo dirigido. No voy a implementarlo yo, sino que voy a usar la magnífica librería networkx.

La idea es construir un grafo dirigido, con las tareas. Un nodo dirigido de C a A significa que antes de hacer la tarea A, C tiene que estar completado. Por supuesto puede darse el caso de que antes de hacer A haya que hacer C y otras tareas.

Vamos a realizar una búsqueda primero en anchura (DFS en inglés). Para ello mantenemos una lista con las tareas completadas y otra lista con las tareas que podríamos empezar a hacer. Cuando completamos una tarea vemos si las tareas a las que llevan necesitan todavía más tareas por realizar o en cambio ya pueden ser añadidas a la lista de “listas para empezar”. El enunciado nos indica que ante la situación de dos tareas listas para empezar, se usa el orden alfabético para determinar cuál va antes.

Hace falta además una lista de tareas iniciales, que pueden empezar sin esperar. Esto se hace con dos conjuntos según leemos el archivo. Se hace la diferencia entre ellos y esas tareas no tienen prerrequisitos.

La segunda parte también es muy interesante. Se nos indica que las tareas tienen una duración de N segundos, dependiendo del valor alfabético de la letra. Además, ahora existen 5 trabajadores que pueden ir haciendo tareas en paralelo. ¿En cuánto tiempo podemos acabar todas las tareas?

Bien, partiendo del mismo grafo dirigido ahora vamos a hacer otro tipo de recorrido, también DFS, pero no vamos a añadir nuevos elementos a la lista de forma inmediata, sino cuando hayan sido acabados de procesar. Almacenamos los trabajadores como listas dentro de una lista de trabajadores. Cada trabajador guarda la tarea que estaba haciendo y el segundo en el que acabará. Defino una función para saber si los trabajadores están todos ocupados.

Lo primero a tener en cuenta es que el tiempo no avanza hasta que la lista de tareas que se puede realizar está vacía o los trabajadores están llenos. Luego en cada iteración del bucle, analizamos a los trabajadores. Si no han acabado, no se hace nada. Si ya han acabado y estaban con una tarea, se añade la tarea a la lista de tareas finalizadas, y se analiza si se han desbloqueado nuevas tareas disponibles para realizar. Si la tarea que ha realizado es la última tarea, se acaba el programa.

Por último si hay una tareas disponible para hacer, se la añadimos al trabajador y si no, pues le indicamos que no haga nada (así no añadimos por duplicado la tarea en el futuro).

Salida de debug que saqué en el día 7

Conclusión

Esta ha sido la primera semana del Advent of Code 2018. Como vemos, el nivel de los problemas ha ido aumentado de forma progresiva. La próxima semana comentaré las soluciones correspondientes. Tenéis todo el código hasta ahora aquí.

 

Juego de la Vida de Conway en C# con interfaz gráfica

Hoy os traigo un proyecto que realizamos Daniel Bazaco y yo. Se trata del clásico de juego de la vida, esta vez hecho en C# con .NET Core y Avalonia como librería gráfica. Funciona tanto en Windows como en GNU/Linux. El programa tiene la peculiaridad de que tiene implementados dos algoritmos totalmente distintos para el juego de la vida:

  • El clásico algoritmo de la matriz infinita.
  • Un algoritmo usando Quadtrees y tablas de dispersión optimizadas, que permite tener patrones precalculados.

La velocidad de este segundo algoritmo es muy superior a la del primero, aunque he de confesar que este segundo algoritmo no resulta evidente y tiene una desventaja en el modo gráfico. Este segundo algoritmo avanza a trompicones, por lo que no es posible realizar una animación gráfica idónea, a no ser que lo modifiquemos ligeramente. Este tercer algoritmo que es una modificación del segundo, es más lento, pero permite ser mostrado por la pantalla.

El programa admite ficheros tanto en formato estándar RLE como un formato propio, que hemos llamado Vaca. Puedes pasarte por la wiki del juego de la vida y probar los ficheros RLE que encuentres. No obstante, hay que tener cuidado, pues algunos ficheros RLE no son del juego de la vida, sino de otros juegos con normas ligeramente modificadas.

¿En qué consiste el Juego de la Vida?

El juego de la vida es un autómata celular de dos dimensiones. También se le ha categorizado como juego para cero jugadores.

El juego tiene unas normas sencillas. Cada celda puede estar viva o muerta. En la siguiente evolución, las celdas pueden pasar a vivas o muertas siguiendo este esquema:

  • Una célula muerta con exactamente 3 células vecinas vivas “nace” (es decir, al turno siguiente estará viva).
  • Una célula viva con 2 o 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por “soledad” o “superpoblación”).

Unas condiciones de partida determinadas podrán desencaminar comportamientos complejos y emergentes muy interesantes como las pistolas de gliders.

Uso

Pantalla de inicio de Conway

Desde aquí podemos dar a Nuevo patrón o Cargar patrón. Si le damos a Nuevo Patrón tendremos una matriz vacía y limpia. Podemos hacer click con el ratón para ir activando/desactivando las casillas. Puedes usar las teclas W, A, S y D o las flechas en pantalla para moverte por el universo infinito de Conway.

Una vez lo tengamos podemos guardarlo para no tener que volver a dibujarlo. Otra opción es cargar un patrón de la lista. Este programa admite formato RLE y Vaca, pero solo guarda archivos en formato Vaca.

Para ejecutar el juego de la vida hay tres botones importantes. El primero es Ejecutar, que ejecuta el juego de la vida indefinidamente. Se para cuando pulsamos Parar (el mismo botón).

El otro es Siguiente, que nos permite avanzar de iteración en iteración manualmente, muy interesante para observar al detalle ciertos patrones. Por otro lado tenemos Iterar N veces, que permite iterar N veces y que sirve para pruebas de rendimiento. Hay que tener en cuenta que tanto Siguiente como Iterar N veces funcionan un poco distinto con el algoritmo Quadtree (el activado por defecto), ya que este algoritmo hace varias evoluciones de golpe, para ser todavía más rápido. La parte mala es que no es posible ver en detalle cada algoritmo.

Algoritmo Matriz
Algoritmo Quadtree

Línea de comandos

Es posible ejecutar el juego de la vida en línea de comandos. Este modo permite cargar un archivo Vaca o RLE y ejecutarlo N iteraciones. Al finalizar se muestran estadísticas y se permite guardar el resultado o mostrarlo por pantalla con caracteres ASCII.

Hay dos parámetros, -i para indicar el fichero de entrada y -n para indicar las iteraciones a calcular.

Algoritmo Quadtree

¿Cómo funciona el algoritmo quadtree que tanto mejora el rendimiento del juego de la vida? Siendo sinceros, no es algoritmo sencillo o evidente. Su nombre más correcto es algoritmo Hashlife y fue descrito por Bill Gosper en los laboratorios de investigación de Xerox Palo Alto.

La idea básica es que muchas veces en el juego de la vida nos encontramos con patrones que se van repitiendo periódicamente y grandes zonas vacías.

Para ello recurre a un almacén de cuadrantes. Y es que ahora el universo ya no es una matriz infinita, sino un cuadrante. Y cada cuadrante tiene cuatro cuadrantes hijos (noroeste, noreste, suroeste y sureste), así hasta llegar al cuadrante mínimo ya no tiene hijos sino que es una celda viva o muerta. Esto evidentemente pone limitaciones al tamaño del universo, que será siempre potencia de dos.

El almacén es una tabla hash, pero no una corriente tipo HashMap de Java o Dictionary de C# sino que toma 4 elementos como índice, cuatro subcuadrantes. Si existe un elemento cuyos cuatro subcuadrantes son iguales (no se comprueba la igualdad exactamente, sería muy lento), se devuelve la siguiente iteración del cuadrante del almacén que cumple esos requisitos. De este modo no hace falta calcular los cuadrantes nada más que la primera vez que el programa se encontró con ellos.

Este sistema consume más memoria, pero mejora de forma sustancial la velocidad de ejecución. El algoritmo luego tiene bastantes más detalles (el diablo está en los detalles), pero esa es la idea principal, no calcular los cuadrantes más que una sola vez.

Descargar Conway

Podéis descargar Conway desde GitHub y compilarlo en Windows y GNU/Linux (Mac no está probado pero en principio funcionaría), con .NET Core 2.0 instalado.

Conway en GitHub