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.

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

 

La perlificación de Python

You know, FOX turned into a hardcore sex channel so gradually I didn’t even notice

Marge Simpson, Los Simpson

Recientemente ha salido Python 3.7, con interesantes novedades. También han salido los primeros artículos hablando de las novedades que podrá traer Python 3.8. Como muchos ya conoceréis, y si no es así explico, Python funciona a base de PEPs (Python Enhancement Proposal). Cualquier persona puede abrir un PEP, que es un documento que describe la funcionalidad que se quiere añadir/modificar/eliminar. Estas PEPs se discuten y finalmente Guido, creador de Python, las aprueba y se codifican.

Dentro de las PEP relacionadas con Python 3.8 hay algunas bastante controvertidas que han hecho saltar la voz de alarma. No ha faltado gente que ha opinado que cada vez Python se parece más a Perl. Este proceso habría empezado con Python 3 pero se habría ido haciendo más evidente hasta llegar a hoy. Cada vez con más sintaxis poco utilizada, con más elementos, más cómodo de escribir para el experimentado aunque menos legible si no dominas el lenguaje.

Y resulta curioso, porque Python es en parte una respuesta a la excesiva complejidad que podían tener los programas hechos en Perl. Su popularidad se debe a que es fácil de aprender y eso parece que ya no está tan claro.

Con la introducción de operadores como := o ?? o anotaciones como @dataclass se va, en cierta medida, perdiendo el espíritu original de Python. Y es cierto que otros lenguajes tienen algo similar, pero precisamente Python había sido muy selecto en incluir un conjunto bastante reducido de características, que todo el mundo pudiese dominar. Al final se sacrifica legibilidad y facilidad de aprendizaje por una ergonomía que beneficia a unos pocos en unos casos concretos.

Lenguajes de programación barrocos

Universidad de Valladolid, ejemplo de barroco civil. Foto: https://artevalladolid.blogspot.com

Python lleva un tiempo entrando en un proceso de perlificación pero en mi opinión no es el único lenguaje que ha entrado en una espiral parecida. Cada vez más lenguajes han pasado del renacimiento, donde se buscaba la consistencia, la simetría, la sencillez sin perder la funcionalidad, hacia el barroco, donde los lenguajes son más recargados, con más elementos sintácticos, que cubren mejor casos concretos, pero que de por sí no son tan esenciales, no cambian aspectos fundamentales del lenguaje y normalmente introducen diversas formas de hacer algo en un mismo lenguaje.

Veamos más ejemplos: en C++20 se propuso añadir funcionalidad de dibujado 2D a la librería estándar (propuesta que fue rechazada en una historia bastante larga para este post) y se han propuesto conceptos, módulos, comparación de tres vías, reflexión, metaclases,… En C# 8.0 se han propuesto también bastantes cosas como records, tipos non-nullable, interfaces con métodos ya implementados (traits) y rangos. Y eso sin contar con las características que estos dos lenguajes ya tienen, que son bastante más extensos que Python.

Retablo lateral de la Iglesia de San Miguel y San Julián (Valladolid). Barroco puro. Foto: https://commons.wikimedia.org/wiki/File:San_Miguel_-_retablo_relicario.jpg

Hay un horror vacui, horror al vacío, a funcionalidades. Siempre se añade y casi nunca se elimina. ¿Pero es realmente necesario? Es evidente que durante mucho tiempo, los lenguajes evolucionaban de forma muy lenta y muchos de los cambios que han hecho eran necesarios. Desde hace unos años, se ha aumentado la velocidad de los cambios, pero esto no puede seguir así eternamente, porque el ritmo que llevan muchas veces es superior al de los avances en lenguajes de programación y la retrocompatibilidad impide ir quitando cosas al mismo ritmo que se añaden. De este modo, todos los lenguajes que entran en esta espiral crecen y crecen. No se llegan a pulir, simplemente crecen.

La perfección no se alcanza cuando no hay nada más que añadir, sino cuando no hay nada más que quitar

Antoine de SaintExupéry

Uno podría comparar esto con lenguajes naturales, como el español o el inglés. En estos idiomas, pese a existir reglas, existen numerosas excepciones. Es posible que lenguajes como Python se estén viendo influenciados por las mismas mecánicas humanas que rigen los lenguajes naturales y que han hecho que existan excepciones. Tendría bastante sentido que ocurriese así. Pero personalmente, me gustaría que aprender Python no costase tanto como aprender alemán o francés.

Los procesos comunitarios

Para mí, gran parte de esta sobrecarga viene dada por los procesos comunitarios. En un proceso comunitario como PEP, comité de C++ o similares es mucho más fácil añadir que eliminar. En C++ la situación ha llegado a un punto en el que Bjarne Stroustrup, creador de C++, ha pedido que se relajen con las propuestas en Remember the Vasa!, en honor a un bonito barco sueco que se hundió por exceso de carga. No tanto por su peso, sino por su disposición y las reformas que hubo que hacer para que todo encajase.

El Vasa fue recuperado después de su naufragio y se expone en Estocolmo. Foto: https://rachelannsblog.wordpress.com/2016/08/03/set-sail-set-at-the-bottom-of-the-sea/

Es por ello que las personas encargadas de elegir que se añade al lenguaje o no deben de ser muy conscientes de lo que supone, ya que una vez se introduzca, va a ser casi imposible eliminarlo.

No estoy en contra de añadir nuevas características (¡al contrario!) pero se debe respetar la visión de conjunto del lenguaje, que todo cuadre y esté cohesionado. No siempre tener más es mejor.

¿Te ha gustado el artículo?

Si es así, puedes ayudar al blog. Dentro de unos días es el Amazon Prime Day. Como muchos de vosotros seguro que os compraréis algo, no quiero dejar la oportunidad de deciros que este blog tiene enlace de referidos y que por cada cosa que compréis con el enlace, me llevo una pequeña parte (a vosotros no os va a costar más caro).

Enlace Amazon.es

Será muy bien recibido

 

Fabric, automatiza tareas en remoto

En la medida de lo posible tenemos que automatizar todo lo posible. No solo reducimos tiempo sino que reducimos errores, y a la vez, estamos documentando un proceso. Muchas de estas ideas ya las dejé claras en ¡Haz scripts! Sin embargo, hay situaciones donde es más complicada esta situación, como por ejemplo, trabajar con máquinas remotas. Aquí entra Fabric en acción, una librería para Python que permite automatizar procesos en remoto a través de SSH.

Originalmente Fabric, compatible únicamente con Python 2, funcionaba a través de unos archivos llamados Fabfile que se ejecutaban con el comando fab. Este mecanismo ha sido transformado por completo en Fabric 2, que ha salido hace nada. Yo ya he hecho la transición y puedo decir que el nuevo sistema, más enfocado a ser una librería sin más, es mucho más práctico y útil que el anterior.

Instalando Fabric

Voy a usar Pipenv, que es la manera recomendada de gestionar proyectos en Python actualmente.

Y accedemos al virtualenv con:

Conexiones

El elemento fundamental de Fabric a partir de la versión 2 son las conexiones. Estos objetos representan la conexión con otra máquina y podemos:

  • ejecutar comandos en el shell de la otra máquina, run, sudo.
  • descargar archivos desde la máquina remota a local, get
  • subir archivos de local a remoto, put
  • hacer forwarding, forward_local, forward_remote.

Para iniciar una conexión necesitamos la dirección de la máquina y alguna manera de identificarnos. En todo el tema de la autenticación Fabric delega el trabajo en Paramiko, que soporta gran variedad de opciones, incluida la opción de usar gateways.

Vamos a mostrar un ejemplo, en este caso, de autenticación con contraseña:

El objeto creado con Connection ya lo podemos usar. Habitualmente no es necesario cerrar la conexión aunque en casos extremos puede ser necesario, una manera es llamando a close, otra es con un bloque with.

Tareas

Una vez que ya tenemos la conexión podemos pasárselo a diferentes funciones, cada una con una tarea distinta. Veamos algunos ejemplos.

Actualizar con apt

Los comandos que necesiten sudo pueden necesitar una pseudo-terminal para preguntar la contraseña (si es que la piden, no todos los servidores SSH piden contraseña al hacer sudo). En ese caso añadimos, pty=True.

 

Backup de Mysql/Mariadb y cifrado con gpg

Requiere que MySQL/MariaDB esté configurado con la opción de autenticación POSIX (modo por defecto en el último Ubuntu)

Como véis, usar Fabric es muy sencillo, ya que apenas se diferencia de un script local.

Si queremos obtener el resultado del comando, podemos simplemente asignar a una variable la evaluación de los comandos run/sudo.

Grupos

Fabric es muy potente, pero en cuanto tengamos muchas máquinas vamos a hacer muchas veces las mismas tareas. Podemos usar un simple bucle for, pero Fabric nos trae una abstracción llamada Group. Básicamente podemos juntar conexiones en un único grupo y este ejecutas las acciones que pidamos. Existen dos tipos de grupo, SerialGroup, que ejecuta las operaciones secuencialmente y ThreadGroup que las ejecuta en paralelo.

O si tienes ya objetos de conexión creados:

Con esto ya deberías saber lo básico para manejar Fabric, una fantástica librería para la automatización en remoto. Yo la uso para este blog y otras webs. Existen alternativas como Ansible, aunque a mí nunca me ha terminado de gustar su manera de hacer las cosas, que requiere mucho más aprendizaje.

Natural Language Understanding con Snips NLU en Python

Uno de los campos más importantes de la inteligencia artificial es el del tratamiento del lenguaje natural. Ya en 1955, en el primer evento sobre Inteligencia Artificial, y promovido entre otros por John McCarthy (creador de Lisp) y Claude Shannon (padre de la teoría de la información y promotor del uso del álgebra de boole para la electrónica), estas cuestiones entraron en el listado de temas.

En aquella época se era bastante optimista con las posibilidades de describir el lenguaje natural (inglés, español, …) de forma precisa con un conjunto de reglas de forma similar a las matemáticas. Luego se comprobó que esto no era una tarea tan sencilla.

Hoy día, es un campo donde se avanza mucho todos los días, aprovechando las técnicas de machine learning combinadas con heurísticas propias de cada lenguaje.

Natural Language Understanding nos permite saber qué quiere decir una frase que pronuncia o escribe un usuario. Existen diversos servicios que provee de esta funcionalidad: IBM Watson, Microsoft LUIS y también existe software libre, como Snips NLU.

Snips NLU es una librería hecha en Rust y con interfaz en Python que funciona analizando el texto con datos entrenados gracias a machine learning y da como resultado un intent, o significado de la frase y el valor de los slots, que son variables dentro de la frase.

¿Qué tiempo hará mañana en Molina de Aragón?

Y Snips NLU nos devuelve:

  • intent: obtenerTiempo
  • slots:
    • cuando: mañana
    • donde: Molina de Aragón

Pero para esto, antes hay que hacer un par de cosas.

Instalar Snips NLU

Instala Snips NLU con Pipenv (recomendado) o Pip:

 

Datos de entrenamiento

En primer lugar vamos a crear un listado de frases que todas expresen la intención de obtener el tiempo y lo guardamos en un fichero llamado obtenerTiempo.txt. Así definimos un intent:

La sintaxis es muy sencilla. Cada frase en una línea. Cuando una palabra forme parte de un slot, se usa la sintaxis [NOMBRE SLOT:TIPO](texto). En el caso de [donde:localidad](Frías). Donde es el nombre del slot, localidad es el tipo de dato que va y Frías es el texto original de la frase. En el caso del slot cuando, hemos configurado el tipo como snips/time que es uno de los predefinidos por Snips NLU.

Creamos también un fichero llamado localidad.txt, con los posibles valores que puede tener localidad. Esto no quiere decir que no capture valores fuera de esta lista, como veremos después, pero tienen prioridad si hubiese más tipos. También se puede configurar a que no admita otros valores, pero no lo vamos a ver aquí.

Ahora generamos un fichero JSON listo para ser entrenado con el comando generate-dataset.

Entrenamiento

Ya estamos listos para el entrenamiento. Creamos un fichero Python como este y lo ejecutamos:

El entrenamiento se produce en fit, y esta tarea puede tardar dependiendo del número de datos que metamos. Una vez finalizado, generama un fichero trained.json con el entrenamiento ya realizado.

Hacer preguntas

Ha llegado el momento de hacer preguntas, cargando el fichero de los datos entrenados.

Ahora sería tarea del programador usar el valor del intent y de los slots para dar una respuesta inteligente.

Te animo a que te descargues el proyecto o lo hagas en casa e intentes hacerle preguntas con datos retorcidos a ver qué pasa y si guarda en los slots el valor correcto.