Feliz Navidad 2018

¡Feliz Navidad a todos! Que los problemas de vuestra rutina no os amarguen el carbón de azúcar que os merecéis.

Estas fechas además son apropiadas para hacer un repaso de lo que ha sido el blog durante 2018. Así que voy a abrir Google Analytics y veamos que ha ocurrido.

Usuarios

Este año hemos batido récord, con 39.328 usuarios únicos contabilizados, en 51.731 sesiones. Esto es casi el doble que el año pasado en ambas métricas.

Respecto a vuestra edad, cada vez sois más jóvenes. Ha habido un crecimiento relativo importante en la categoría 18-24 y un retroceso en los otros grupos de edad, pero en general todos los grupos tienen más lectores. Respecto a vuestro sexo, este año ha habido un 18,65% de mujeres, respecto al año anterior de 12,3%. Recordad que todos estos datos demográficos no son nada precisos y es una estimación que hace Google Analytics.

En cuanto a vuestros intereses, bastante similar a otros años, usuarios tecnológicos, bastante más software. Las categorías que más han crecido este año son Enterprise Software y Science/Mathematics, curioso.

La mayoría tenéis configurado como idioma el inglés o el castellano, con el tercer idioma siendo el francés (pero a mucha distancia).

En cuanto a vuestra ubicación, la mayoría seguís siendo de España, aunque latinoamérica ha subido este año bastante, algo que me ha alegrado mucho. El país que más ha aumentado su porcentaje de visitas respecto al año pasado a sido Nueva España México. Destacar que aunque en Venezuela y Estados Unidos ha aumentado el número de lectores, lo ha hecho a un ritmo tan bajo, que su porcentaje de lectores ha bajado, ¿tendrá que ver la situación política? Del Top 15 también señalar que Reino Unido es el único país donde ha bajado el número de lectores. Y este año se han recibido visitas desde 114 territorios diferentes del mundo.

En cuanto a ciudades, la mayoría venís de la ciudad con el mejor agua del mundo, los mejores atascos, las mejores cervezas y las mejores catedrales: Madrid. Le sigue Barcelona y en tercer lugar, Santiago de Chile. El top 10 lo completan: Bogotá, Ciudad de México, Buenos Aires, Valencia, La Victoria, Medellín y Sevilla. Esta vez, mi propia ciudad, Valladolid, no está en el top 10.

Se confirma la tendencia de que Chrome es el navegador más usado. El segundo es Firefox y el tercero es Safari. Como cosas curiosas, Edge ha superado a Internet Explorer y hay más usuarios de Opera que de Edge.

En cuanto a sistemas operativos se vuelve a ver una dominancia de Windows y Android. Por otro lado me gustaría conocer a los que han entrado desde BeOS y desde Tizen.

¿Cómo llegáis a este blog?

Ahora vamos a ver como accedéis a este blog. La gran mayoría llegáis a través de un buscador, principalmente Google aunque también Yahoo, Ecosia, Bing, Ask, DuckDuckGo y Yandex.

De los que llegáis a través de otras páginas, la mayoría venís de Menéame, que este año se ha portado muy bien con el blog. La siguiente web es GitHub, ya que enlaza al blog en varios sitios (tutoriales de Rust, repos muy curiosos, ¡e incluso desde issues!). Mención especial a las tres instancias de Moodle de las que tengo constancia que enlazan a mi blog (una de un instituto de la República Checa, muy curioso). Bastantes visitas tambien desde Reddit.

También hay quién nos sigue desde el canal de Telegram, un lector RSS, redes sociales y el correo (podéis encontrar más información en la barra lateral).

Lo más visto

Finalmente, lo mejor para el final, ¿qué contenido es el más popular del blog?

He de decir que esto ha sido una total sorpresa, se trata de un artículo que no tuvo apenas repercusión cuando lo publiqué, pero parece que muchísima gente ha llegado a él a través de Google. Se trata de…

Estadística en Python: media, mediana, varianza, percentiles (Parte III)

La verdad es que me ha sorprendido mucho, pero al parecer mucha gente desea hacer estadística en Python, pero curiosamente no es el primer artículo de la serie que hice.

El segundo artículo ha sido: IPFS, el futuro de la web descentralizada, que tuvo bastante repercusión e interés por vuestra parte desde el principio.

El tercer artículo con más visitas ha sido: Estadística en Python: Parte 1 Como véis, la estadística ha tenido bastante éxito en el blog.

Sin nada más, me despido. ¡Muchas gracias a todos los que seguís el blog! Este año cada vez sois más, y estáis más presentes. Yo me voy a ver ¡Qué bello es vivir! otra vez, que es una película que me gusta mucho.

Algoritmos genéticos: un caso práctico

Existen muchos tipos de algoritmos. Hoy vamos a hablar de un tipo de algoritmo no demasiado conocido, los algoritmos genéticos, que son de la familia de los algoritmos evolutivos. Además veremos su aplicación práctica en el vectorizado de imágenes con un programa que he realizado en Rust.

¿Qué es un algoritmo genético?

Un algoritmo genético es un algoritmo inspirado en el mecanismo de la naturaleza de la evolución biológica, descrita por Darwin allá por 1859 en el libro El Origen de las Especies. La idea es tener un conjunto de individuos (posibles soluciones). Estos individuos son evaluados para ver qué tan buenos son. Quedarnos con los mejores y proceder a la creación de nuevos individuos como resultados de la recombinación genética de dos individuos (como en la reproducción sexual). Posteriormente añadir alguna mutación genética para explorar nuevas posibilidades ligeramente diferentes. Proceder de nuevo a la selección natural hasta que tengamos individuos lo suficientemente buenos para nosotros.

Normalmente no son los algoritmos más eficientes ni tienen por qué dar un resultado óptimo, pero pueden servir para dar aproximaciones bastante buenas al resultado óptimo. Existen estrategias para mejorar los algoritmos genéticos como la gestión de la antigüedad de los individuos, para evitar máximos locales; la conservación de individuos con mal desempeño, para conservar mayor variedad genética; …

Como veremos más adelante, uno de los elementos más importante de estos algoritmos es la función de evaluación, que muchas veces es más complicada de programar de lo que parece.

Un caso práctico: vectorizado de imágenes

Para ver como estos conceptos teóricos funcionan en la práctica, vamos a hacer un programa que vectorice imágenes. ¿Esto qué es? Digamos que hay dos tipos de imágenes en informática. Por un lado tenemos las imágenes que almacenan los colores en píxeles (rasterizadas) y por otro lado aquellas que almacenan la imagen como fórmulas matemáticas, que se aplican cuando se quiere ver la imagen (vectoriales). Los formatos más comunes de imágenes rasterizadas son JPEG, PNG, GIF y WEBP. Los formatos más comunes de imágenes vectoriales son SVG y AI.

A las imágenes rasterizadas no se les puede hacer zoom hasta el infinito, se ven borrosas
A las imágenes vectoriales se les puede hacer zoom infinito, no pierden calidad

Pasar de una imagen vectorial a una rasterizada es trivial, pero el proceso inverso no lo es, y es justo donde vamos a aplicar el algoritmo genético.

En nuestro caso, vamos a tomar siluetas, negras sobre fondo blanco y tratar de vectorizarlas con curvas de Bézier.


Ejemplo de ejecución en la versión final de Mendel Vectorizer. La curva azul es la imagen vectorial generada.

Curvas de Bézier

En los años 60, Pierre Bézier, que trabajaba para Renault, diseñó un tipo de curva para el diseño asistido por ordenador (CAD). Estas son las conocidas como curvas de Bézier. Nuestro algoritmo tratará de encontrar la curva de Bézier más similar a la curva de la imagen rasterizada. Para ello necesitamos un punto de inicio, un punto final y dos puntos de control.

Curva cúbica de Bézier

En nuestro algoritmo, las curvas serán los individuos, y las coordenadas de los puntos de control serán los genes (habrá 4 genes por tanto).

Este es el código que he usado para definir las curvas de Bézier en Rust.

Encontrar puntos iniciales

El primer paso de nuestro algoritmo es buscar los puntos iniciales (y finales) de las curvas. En definitiva esto es un problema de búsqueda de esquinas.

Ejemplo de aplicación de FAST9 a una imagen

Existen varios algoritmos de búsqueda de esquinas: Harris, FAST9, FAST12, … No obstante, no tuve muy buenos resultados en las imágenes con las que trabajaba. Así que esta parte del algoritmo se la dejo al humano. El humano se encargará de poner los puntos, en orden, que tiene que tratar de unir el algoritmo con curvas de Bézier.

Función de evaluación

Muchas veces la función de evaluación es el punto más delicado de estos algoritmos. En este caso la idea fundamental es identificar si la curva de Bézier está encima de la curva original. Para ello tomamos 100 puntos equidistantes de la curva de Bézier (con la ecuación paramétrica de la curva es muy sencillo).

\(\mathbf{B}(t)=\mathbf{P}_0(1-t)^3+3\mathbf{P}_1t(1-t)^2+3\mathbf{P}_2t^2(1-t)+\mathbf{P}_3t^3 \mbox{ , } t \in [0,1].\)

Estos puntos se comparan con la imagen real, si ahí en la imagen original había una línea no pasa nada, si no, se resta 100. De este modo se penaliza gravemente salirse de la curva. Esto se hace así ya que la otra opción evidente (bonificar el estar sobre en la línea) podría dar lugar a resultados inesperados.

Ejemplificación de la función de evaluación. Los puntos amarillos están dentro de la línea. Los puntos verdes están fuera de la línea, penalizando a la curva en su “adaptación al medio”.

Pongamos como ejemplo una función de evaluación que bonifique por estar sobre la línea y no penalice por salirse de esta. Una línea bien adaptada a estas condiciones podría recorrerse toda la imagen, cruzando todas las líneas posibles, generando un garabato totalmente inútil pero muy bueno según esta función. Por ello, nuestra función de evaluación se basa en penalizar las salidas de la línea.

La función de evaluación presentada no es perfecta, ya que puede pasar de largo el punto final y dar la vuelta. Esta curva es más larga que la óptima, pero al estar completamente dentro de la línea negra original, la función de evaluación no la puede clasificar como peor que otras alternativas. Para solventar este problema una idea es que la longitud de la curva tenga una implicación en la función. No obstante, el cálculo de la longitud de una curva de Bezier es demasiado complejo y no lo he codificado. También podría aproximarse a través de segmentos rectos entre los 100 puntos calculados anteriormente.

Ejemplo de curva con puntuación máxima pero no óptima desde el punto de vista humano

Selección natural

La función de selección natural deja únicamente las 500 mejores curvas, de acuerdo a la función de evaluación, es decir, las mejor adaptadas de momento. Para la ordenación, Rust usa un algoritmo denominado Timsort, con coste O(nlogn). Sin embargo, en todo el algoritmo trabajamos con poblciones finitas, por lo que puede asimilarse a una constante, con coste O(1). 

Población inicial

La población inicial se forma con 1000 curvas generadas con parámetros totalmente aleatorios. Los valores de cada coordenada, eso sí, están comprendidos entre -d y d siendo d la distancia en línea recta entre los puntos de inicio y final.

Recombinado

El proceso de recombinación permite mezclar los mejores especímenes tratando de conseguir uno mejor. Este algoritmo genético es de tipo RCGA (Real Coded Genetic Algorithm) ya que los genes son números reales, en contraposición a los típicos genes binarios.
Para estos algoritmos existen distintas variantes, aquí se usa el sistema de blend. El sistema de blend implica que de entre los dos padres se toman los valores mínimos y máximos para cada coordenada. Posteriormente se elige un nuevo valor de forma aleatoria con la condición de que esté dentro del rango de mínimo y máximo definido anteriormente.

Mutación

La fase de mutación permite generar pequeñas variaciones aleatorias respecto a la población. Afecta al 10% de la población aunque solo afecta a una coordenada a la vez.

Al ser un algoritmo RCGA, no vale simplemente con cambiar el valor de un bit. El enfoque utilizado en este algoritmo es el de una distribución normal de cambios de media 0. La distribución tiene la forma N(0,d/2). Esto implica que en la mayoría de las ocasiones la variación (tanto positiva como negativa) en la coordenada será bastante pequeña.

Distribución normal, aunque esta no es de media 0

El programa: Mendel Vectorizer

El programa definitivo, Mendel Vectorizer, disponible en GitHub, tiene más detalles. La interfaz gráfica está hecha usando GTK, la interfaz de línea de comandos usa Clap y el algoritmo se ejecuta en paralelo usando paso de mensajes entre los hilos. El programa genera un fichero SVG resultado que puede ser abierto en programas como Inkscape o Adobe Illustrator.

El fichero generado por Mendel Vectorizer en Inkscape

Para usar Mendel Vectorizer en tu ordenador, sigue los siguientes pasos.

Descárgate una copia del código con Git. Compila con Rust (una edición que soporte la edición 2018, mínimo la 1.31) y ejecútalo.

También podéis descargaros la memoria en PDF del programa.

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.

Las mejores librerías gratuitas para gráficas en PHP

“Los datos son el nuevo petróleo” es algo que dicen muchas personas y que parece confirmarse si se leen noticias tecnológicas. Y en efecto, actualmente podemos generar una cantidad de datos inmensa de los que podemos extraer una información muy valiosa. Y ahí esta la clave, en “extraer”. Los datos como tal no sirven para nada. Al igual que el petróleo, no lo queremos en bruto, sino refinado, tratado. Con los datos pasa lo mismo. Para representar esta información desde hace muchos años estadística ha ido diseñando métodos para representar datos y extraer información de ellos.

Antiguamente estas gráficas se realizaban a mano y su creación era muy costosa. Hoy en día, como seguro que sabrás si sigues las noticias tecnológicas actuales, podemos usar herramientas para generar estas gráficas de forma sencilla, directamente en un servidor. En este artículo vamos a ver las mejores librerías para generar gráficas en PHP.

phpChart

La primera librería de la lista es phpChart. Se trata de una librería de pago, pero con muchas opciones para las gráficas. Desafortunadamente, solo las versiones más caras soportan gráficos que no sean de barras, de líneas y de sectores. La librería funciona generando código JavaScript para el cliente que le permite dibujar la gráfica usando Canvas. Esta gráfica es interactiva, pudiendo el usuario hacer zoom, cambiar de modo de gráfico y permitiendonos hacer animaciones.

pChart

Otra opción es generar imágenes para las gráficas en el servidor. Esto es precisamente lo que hace pChart. Originalmente era un mero wrapper sobre la librería estándar de gráficos de PHP (GD) para añadir anti-alising, pero con el tiempo se enfocó a las gráficas estadísticas. Sus principales cualidades son una gran calidad en las visualizaciones y un rendimiento óptimo. pChart es gratuita si nuestra aplicación es software libre y de pago si no lo es. Requiere las extensiones GD y FreeType para funcionar correctamente. pChart soporta gran cantidad de gráficas y es usado por empresas como Intel o Airbus e instituciones como la NASA y el CERN. La librería tiene capacidades interactivas, aunque algo más reducidas que otras soluciones.

JpGraph

Otra librería que permite renderizar en el servidor es JpGraph. Esta librería, gratuita para usos no-comerciales, está diseñada con orientación a objetos. Tiene una gran variedad de gráficas disponibles, de buena calidad y como ellos promocionan: ligeros. Existe una versión PRO con todavía más tipos de gráficos, aunque son bastante específicos y normalmente no harán falta. La librería necesita que GD esté instalado y es compatible con PHP7.

D3.js

Para acabar, una de mis personalmente favoritas, D3.js. D3 no es una librería para generar gráficas y tampoco es PHP. Se trata de una librería JavaScript con utilidades para los documentos basados en datos, la idea es incluir esta librería y usarla donde quieras mostrar las gráficas. La ventaja de D3 es que te permite hacer lo que quieras y tiene una gran comunidad. Es open-source, y aunque es algo más difícil de usar, genera unos resultados excelentes, usando SVG de por medio. De hecho, D3 no generará código visual, sino que nos ayudará a hacerlo nosotros mismos. He ahí la dificultad y a su vez, su gran flexibilidad.

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í.