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

 

Conclusiones de la visita de Richard Stallman a Valladolid

Richard Stallman, el padre del software libre, vino a visitarnos a la ciudad de Valladolid. La oportunidad de conocer a tal personaje en primera persona era única, así que no dudé en asistir, con la suerte que tuve de poder estar en primera fila durante la conferencia.

La conferencia no contaba nada nuevo, nada que no supiese cualquier persona que haya leído un poco sobre la idea del software libre, pero se hizo amena. Stallman explica muy bien y las diapositivas están muy bien hechas. Tiene bastantes chistes precocinados pero que causan buen impacto en la audiencia.

Pero Stallman es un personaje. Hablando con la gente que cenó con él el día anterior, algunos me contaban que había sido bastante irrespetuoso, sacando el portátil durante la cena para hacer sus cosas y gritar de vez en cuando que no escuchaba bien.

Durante la charla ha estado bebiendo de su té, descalzo y hasta el momento de empezar ha seguido mandando correos. Le noté bastante envejecido, caminaba medio cojo y se le notaba la marca de la operación en el brazo. Para empezar a puesto su famosa versión de Guantanamera.

La presentación ha seguido explicando las cuatro libertades del software libre, de forma bastante extensa, explicando para todos los públicos por qué son importantes.

Durante la charla también ha hablado del software malévolo, no confundir con privativo. Según él, son dos cosas distintas, pero relacionado. Puede haber software honesto privativo y software malévolo libre, pero son minorías en la práctica. También ha hablado del software privado, que es perfectamente ético, y que hasta él programa software privado. La diferencia es que el software privado nunca se distribuye fuera del propio autor u organización. Bastante parte de la charla se ha centrado en esta parte, tocando el tema de la privacidad a fondo. Para Stallman la recolección de datos personales debería estar prohibida.

Para ilustrar este punto, ha puesto como ejemplo algo que le ha horrorizado, el sistema de parquímetros de Valladolid. Según él son horribles, no porque haya que pagar, que es algo a lo que está dispuesto, sino porque hay que poner la matrícula del vehículo. Poner la matrícula en el parquímetro lo que sirve es para rastrear a la gente. Este tipo de acciones nos acercan cada vez más a la dictadura y a la destrucción de los derechos humanos.

Personalmente el ejemplo me parece bastante exagerado y aunque veo su punto, creo que la recolección de datos personales puede ser necesario en ciertas situaciones, siempre que se traten de forma adecuada.

También ha habido tiempo para hablar de historia. Habló de la historia de GNU, como Linux al principio tenía una licencia no libre (se impedía su redistribución comercial), pero que al poco cambió a GPL 2, siendo el candidato perfecto para el proyecto GNU. Ha comentado que Hurd tiene un diseño muy elegante, moderno pero quizá fue demasiado complicado y que en perspectiva fue un error diseñarlo de esa forma. Ha dicho que Hurd no es usable para nada práctico ahora mismo.

Ha insistido mucho en que el sistema operativo se llama GNU con Linux.

También ha hablado del open source. Y cuando le proclaman padre del open source afirma: “si soy el padre es porque han hecho la reproducción invitro con semen mío robado”. Afirma que la gente del open source tiene otra ideología, mucho más pragmática, pero incompleta, ya que no preserva las libertades.

Ha hablado de licencias libres: débiles y la GPL. De entre las débiles recomienda la Apache, aunque por supuesto la mejor es la GPL, en sus distintas versiones. Ha confirmado que nadie está trabajando en la GPL4. Aquí ha aprovechado para criticar a GitHub que ha seguido una muy mala costumbre de no prestar atención a las licencias del software que aleja. Además indica que es necesario poner un comentario en cada archivo con la licencia que sigue. Eso de poner un archivo con la licencia en la carpeta raíz no es suficiente según Stallman.

Esto lo ha enlazado con LibreJS, el complemento que detecta si el código JavaScript de una página es libre o no y lo bloquea o no según esto. Stallman no ha criticado en ningún momento JavaScript, simplemente que tiene que respetar los mismos criterios de los programas nativos para ser software libre.

También ha hablado de distros libres, metiéndose con Ubuntu bastante. Reconoce que estos usuarios están más cerca de la libertad que si usasen Windows o macOS pero que todavía les falta un poco. Y lo peor para Stallman es que mucha gente cree que sistemas como Ubuntu son libres y la gente se queda en ellos.

Por último ha hablado del software libre en la educación, también ha recomendado a la universidad tener una asignatura de ingeniería inversa (o retroingeniería como él lo llama).

Después de esto ha proseguido con el momento más cómico de la charla, se puso su túnica y su aureola y empezó a hablar de la religión de Emacs.

Nos bendijo nuestros ordenadores, y habló de como formar parte de la Iglesia del tan importante Emacs. No es necesario guardar celibato para ser santo pero hay varias cosas, como el peregrinaje de Emacs (saberse todas las combinaciones de teclado de memoria) o los cismas actuales (¿cuál es la tecla más importante en Emacs?). También ha dedicado palabras a los Vimeros como yo. Usar Vi no es pecado, es una penitencia. Y eso a pesar de que VIVIVI es el número de la bestia. También contó como en China le intentaron atacar unos seguidores de Vi, pero tenía sentido porque la violencia empieza por vi.

Después ha subastado un ñu, poniendo caras para que no dejásemos al ñu solo. Además de incidir en que no puede haber pingüinos solos, tiene que haber ñus acompañándolos.

Por último la ronda de preguntas. Mi pregunta ha sido ¿Las redes neuronales pueden ser software libre? Su respuesta ha sido que existen herramientas para alterar los valores numéricos de estas redes, mucho más fácil que la ingeniería inversa. Por tanto no sería técnicamente lo mismo. Creo que lo ha puesto al nivel de una fotografía o un vídeo, donde la edición es más sencilla y no tiene sentido hablar de fotografía libre.

También se ha preguntado por Microsoft y su deriva open source. Stallman celebra que publique cosas con licencias de software libre, pero eso no quita que siga teniendo software privativo que espía como Windows.

Le han preguntado por un teléfono que respete la privacidad. Según él es imposible, aunque se está intentando con un interruptor que permita desconectar la conexión móvil de forma física. El problema es de la tecnología móvil (no importa que sean smartphones o no), que para enrutar los paquetes guarda la ubicación de los dispositivos. El propósito era muy inocente pero se puede usar para espiar. Eso sí, él ha usado teléfonos móviles, siempre cuando necesita llamar pregunata a alguien que haya alrededor si le pueden dejar el teléfono.

Por último, sobre el hardware libre ha dicho que el concepto es erróneo. No puede existir hardware libre. El software libre existe, porque se puede copiar de forma exacta, en el mundo físico eso no pasa. Habría que hablar de hardware con diseños libres, pero ningún objeto podrá ser hardware libre o hardware privativo.

Alojando una web en IPFS

En el primer post vimos como interactuar con IPFS de forma sencilla. Ahora vamos a dar un paso más y vamos a alojar una web en IPFS, aprovechando todas las ventajas de escalabilidad y disponibilidad que nos ofrece la red. Para ello usaremos además otro protocolo llamado IPNS, que sería similar a DNS pero en la red IPFS.

Las páginas ideales para IPFS actualmente son las que siguen el JAMstack, es decir, uso extensivo de JavaScript en el cliente, que podrá conectarse a APIs para obtener/actualizar información. Las APIs no tienen por qué ser centralizadas, ya que JavaScript con WebRTC puede buscar peers, posibilitando APIs descentralizadas.

Generando el contenido estático

El primer paso será generar el contenido estático de la web. Para ello existen herramientas muy conocidas como Jekyll, Hugo o Pelican.

No nos vamos a alargar más en esto, ya que cada herramienta tiene sus pasos. El resultado final será una carpeta con ficheros HTML, CSS, fuentes, imágenes y JavaScript.

Subir a IPFS

Teniendo el nodo IPFS en funcionamiento, subimos la carpeta del modo habitual, en mi caso, voy a subir la página que está en http://adrianistan.eu .

Y anotamos el último hash.

Comprobamos que la web es accesible, tanto desde la gateway del nodo, como una externa:

Tanto en el nodo local como en uno externo, la web carga perfectamente con el hash

IPFS tiene direccionamiento por contenido

En el post anterior mencionamos que IPFS direcciona por contenido gracias a los hashes. Esto tiene unas consecuencias interesantes. Por ejemplo, si se añade un archivo duplicado a IPFS, este tiene exactamente la misma dirección, ya que comparten hash. Por otro lado, los documentos no se pueden actualizar, porque entonces su hash cambia. Sin embargo en una web queremos cambiar contenido, ahí entra en acción IPNS.

IPNS, gestión de nombres para IPFS

IPNS es un protocolo parecido en intenciones a DNS que redirige un ID única al hash correspondiente en ese momento. Registramos el hash de la web actual en IPNS.

Ahora sí, el hash IPNS puede publicarse por la red, ya que siempre apuntará a la última versión de la web.

Para acceder a recursos a través de IPNS tenemos que cambiar de protocolo, en vez de /ipfs/HASH, tenemos que poner /ipns/HASH. Vale tanto para comandos como para las gateways HTTP.

https://cloudflare-ipfs.com/ipns/QmYDVeoadAzk9ZW6zwJK3E3KHrA1LWLveEdqUv4XAcCjKa/

En cualquier momento podemos comprobar a que dirección IPFS apunta el hash IPNS:

Para actualizar el contenido simplemente se vuelve a repetir el paso de ipfs name publish. IPFS automáticamente modificará la redirección de IPNS.

Los contenidos antiguos no desaparecen, pero pueden no ser accesibles ya que ningún nodo tenga copia de ellos.

DNSLink

Aún así, ir dándole a la gente un hash IPNS es demasiado complicado. Afortunadamente, podemos usar el DNS tradicional para indicar una ruta IPNS y así, como veremos, facilitar bastante las cosas.

Para ello añadimos un campo TXT en los DNS de nuestro dominio. El contenido es el siguiente:

Con esto podremos usar /ipns/dominio.com en la red IPFS. Pero todavía hace falta un cliente IPFS.

Afortunadamente, podemos redirigir mediante CNAME a una gateway HTTP de confianza y ¡la web funcionará correctamente! Para ello hay que crear un campo TXT en el subdominio _dnslink con el mismo contenido que el anterior.

Todas las gateways de IPFS soportan DNSLink para que la transición a IPFS sea lo más transparente posible.

Así, finalmente la página carga con un dominio normal y corriente en un navegador normal y corriente.

Fijaos en la URL

De hecho, vosotros mismos podéis acceder:

http://adrianistan.yayeyo.ga

IPFS Companion

Si usamos mucho IPFS, puede que nos interese una extensión que maneje el protocolo ipfs:// . Tanto en Firefox como en Chrome existe IPFS Companion, una extensión que nos permite acceder a contenido IPFS de forma sencilla.

Servicio systemd

Por último, quiero dejar el servicio de systemd necesario para tener el nodo IPFS funcionando constantemente en nuestro ordenador. En este caso, IPFS lo instalé vía Snap.

Y con esto ya tendríamos suficiente como para jugar con IPFS un buen rato.

IPFS, el futuro de la web descentralizada

Imagina la web sin servicios centralizados. Donde puedas acceder a un vídeo o a una galería de fotos y que no haya una única manera de acceder a contenido. Eso y mucho más es IPFS. IPFS son las siglas de InterPlanetary File System y se trata de una red descentralizada de intercambio de archivos. Nos puede recordar a BitTorrent y en efecto, una buena descripción para IPFS es Torrent 2.0. No obstante IPFS implementa bastantes mejoras sobre BitTorrent, mejoras que lo hacen más útil.

En un post próximo explicaré como podemos sacar partido a IPFS ahora mismo, pero antes vamos a ver algunos conceptos fundamentales de IPFS.

Siendo más técnicos, IPFS es una red P2P inspirada en BitTorrent, Git y Kademlia. El protocolo es una red de distribución de contenido (CDN) y define un sistema de archivos donde el identificador es el propio contenido (a través de su hash). En IPFS nada desaparece sino que se versiona.

Vamos a ver como usar IPFS desde la terminal. Existen varios clientes, en diferentes lenguajes, como js-ipfs (que tendrá mucha utilidad en aplicaciones web descentralizadas usando JavaScript), pero de momento el cliente más maduro es go-ipfs. Desde la web puedes descargarlo.

Iniciar IPFS

Una vez IPFS esté instalado hay que ejecutar lo siguiente:

La segunda opción es para centros de datos, ya que reduce el tráfico interno.

Este comando genera las claves RSA del nodo, necesarias para la comunicación con la red IPFS. Además se nos informa de nuestro ID de nodo. Para acceder a este ID en cualquier momento podemos escribir:

Iniciar el nodo IPFS

Para acceder al contenido IPFS necesitamos ejecutar un nodo. Este nodo se inicia con ipfs daemon. Una cosa importante es que por ejecutar el nodo no se va a descargar nada que no pidamos. IPFS es explícito, pero necesita estar activo.

Obtener archivos

Ahora vamos a descargar nuestros primeros archivos de la red IPFS.

Para obtener un archivo existen varias formas:

Podemos usar el comando cat de IPFS, que funciona de forma similar a cat de Unix.

Las URL de IPFS todavía no han sido definidas de forma definitiva pero de momento siguen el siguiente formato: /protocolo (omitible)/hash/fichero (si es una carpeta). Es el hash el que identifica el bloque de contenido y es lo que sirve para encontrar el contenido en la red IPFS. Internamente usa una DHT (Distributed Hash Table). IPFS no usa trackers como las primeras versiones de BitTorrent. En cambio usa una DHT basada en Kademlia (bastante rápida).

Para obtener un fichero binario usamos el operador de redirección de Linux.

También se puede acceder a IPFS por dos métodos más:

FUSE

Podemos montar un sistema de ficheros en Linux gracias a FUSE que es una puerta a IPFS.

Y tendrás acceso a carpetas /ipfs/hash/ integradas en tu sistema. Muy útil si lo queremos integrar en aplicaciones.

GATEWAY HTTP

Podemos usar IPFS sin tener instalado nada, usando la puerta de acceso que alguien generosamente proporcione a la red. La puerta se encargará de llevar el contenido IPFS al mundo cliente-servidor de HTTP. Existen varias, de hecho cada nodo tiene un servidor HTTP en localhost para esto mismamente, pero aquí voy a mencionar dos: la de IPFS.io y la de CloudFare.

Esto sirve para llevar IPFS a cualquier ordenador a través de un navegador web tradicional como Chrome, Firefox o Safari. También facilita la tarea de integrar IPFS en aplicaciones que no tengan desarrollada una librería específica.

Añadir archivos

Ahora vamos a poner en la red IPFS nuevos archivos. Para ello usamos ipfs add.

Esta operación genera el hash que identifica al contenido en la red y que tendremos que enviar a las personas que queramos que accedan al contenido.

La red IPFS de este modo es semi-privada, ya que sin saber el hash no podemos acceder al contenido en cuestión.

Y ya estaría, así de simple. También podemos añadir carpetas.

El último hash que se ve en la pantalla hace referencia a la carpeta entera.

Pining

Por defecto, IPFS almacena los archivos propios del nodo (los que hemos añadido con ipfs add). Pero entonces IPFS no supone ninguna ventaja respecto a HTTP. No es distribuido, solo hay una copia de los ficheros en el universo.

Cuando descargamos un fichero, IPFS guarda en caché una copia para ofrecer a la red, haciendo que sea un sistema distribuido de verdad. No obstante si estamos realmente interesados en conservar el fichero en nuestro nodo a disposición de la red IPFS tenemos que hacer pin (ipfs add). Cuando nos deje de interesar conservar el fichero a la red, podemos quitar el pin (ipfs rm).

Más cosas

Todavía nos quedan muchas cosas de IPFS que ver, como el versionado, el sistema de nombres IPNS, el sistema de enlazado semántico IPLD y como podemos usar IPFS para páginas y aplicaciones web.

 

Computación cuántica para torpes: introducción para programadores

Hace ya bastante tiempo quese viene hablando de ordenadores cuánticos. ¿Qué son? ¿En qué se diferencian de los ordenadores clásicos? ¿Son de verdad tan potente como dicen?

En este largo artículo, ideal para el verano, vamos a ver los principios fundamentales de los ordenadores cuánticos más allá de lo que la típica revista o web te podría contar. Veremos qué es un qubit y algunas puertas lógicas interesantes, así como su aplicación.

Los ordenadores cuánticos actuales requieren temperaturas de funcionamiento cercanas al cero absoluto

Notación de Dirac

Lo primero antes de entrar en materia cuántica, será adaptar nuestra notación clásica, a otra más potente. Esta notación que vamos a ver, llamada notación de Dirac o Bra-ket, nos será muy útil ya que los bits clásicos no son más que un caso concreto de qubit en esta notación.

En esta notación tenemos que representar los bits como matrices. Un conjunto de N bits se representa con una matriz de 1 columna y \(2^N\) filas. En todas las posiciones existen ceros salvo para la posición que representa la combinación que representa. Veamos algunos ejemplos sencillos:

Un bit con valor 0 se representa así

\(
| 0 \rangle = \begin{pmatrix}
1\\
0
\end{pmatrix}\)

Un bit con valor 1 se representa así:

\(
| 1 \rangle = \begin{pmatrix}
0\\
1
\end{pmatrix}\)

Aquí contamos como en informática, empezando desde cero. Como ves la posición 0 del vector solo es 1 cuando representa el bit 0. Si la posición que tiene el 1 es la segunda, representa el bit 1.

La parte que va a la izquierda del igual se llama ket. En este caso hemos representado ket 0 y ket 1.

Si tenemos más bits se puede hacer de la misma forma. Vamos a representtar ket 10. 10 en binario es 2, así que estará en la posición tercera.

\(
| 10 \rangle = \begin{pmatrix}
0\\
0\\
1\\
0
\end{pmatrix}\)

Puertas lógicas como producto de matrices

¿Recuerdas el producto de matrices de tus clases de álgebra? Resulta que todas las puertas lógicas clásicas pueden representarse como producto de matrices. Por ejemplo, la puerta lógica NOT se puede implementar con esta matriz:

\(
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\)

Y aquí la vemos en acción

\(
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}\begin{pmatrix}
1 \\
0
\end{pmatrix}
=
\begin{pmatrix}
0 \\
1
\end{pmatrix}
\)

También podría hacerse con la puerta AND que toma como entrada dos bits.

\(
\begin{pmatrix}
1 & 1 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
0 \\
0 \\
0 \\
1
\end{pmatrix}
=
\begin{pmatrix}
0 \\
1
\end{pmatrix}
\)

Un teclado con puertas cuánticas

Juntando bits

Para formar bits más grandes ya sabemos que tenemos que tener una matriz tan grande como combinaciones haya (\(2^N\) posiciones, N bits). Existe una forma de calcular automáticamente la posición que hay que marcar y es hacer el producto tensorial. Si no sabes calcularlo no importa mucho, porque apenas lo vamos a usar, pero puedes ver un ejemplo de como funciona. En este ejemplo, queremos juntar los bits 1 y 1 (3 en decimal).

\(
\begin{pmatrix}
0 \\
1
\end{pmatrix}
\otimes
\begin{pmatrix}
0 \\
1
\end{pmatrix}
=
\begin{pmatrix}
0 \\
0 \\
0 \\
1
\end{pmatrix}
\)

Qubits

Hasta ahora no hemos visto nada realmente nuevo, solo hemos preparado el terreno para dejar paso a los qubits. Personalmente desconocía que podían usarse matrices para operar con bits y aunque no es tan práctico como otros sistemas, lo cierto es que es muy explícito y elegante.

Los qubits son bits como los que hemos visto antes pero tienen un estado indeterminado. No es que tengan un valor de forma secreta y no sepamos cuál es. Podríamos decir que son los dos valores clásicos a la vez, como el gato de Schrodinger. Cuando realizamos una observación sobre el qubit, este colapsa y podemos ver uno de los dos estados. ¿Cuál vemos? No podemos saberlo a priori, pero hay probabilidades. Los bits clásicos no son más que qubits cuyas probabilidades de colapsar a 0 o 1 es del 100%, por tanto no hay duda y su valor sí que está determinado.

¿Cómo representamos los qubits y sus estados cuánticos? Con números complejos. Si recuerdas, estos eran los que tenían una parte real y una imaginaria. No obstante, voy a tomar solo los números reales para simplificar. Los números reales son números complejos válidos, pero los complejos son mucho más extensos.

La esfera de Bloch permite representar todos los estados cuánticos (números complejos)

Para calcular la probabilidad que tiene un estado cuántico de colapsar a un valor, hacemos el módulo y elevamos al cuadrado: \(|a|^2\).

Todo qubit además debe cumplir una propiedad fundamental:

\(
\begin{pmatrix}
a \\
b
\end{pmatrix}
\text{ es un qubit}
\Leftrightarrow
|a|^2 + |b|^2 = 1
\)

Y es que la probabilidad de ser 0 y de ser 1 sumadas deben equivaler al suceso seguro, es decir, 1. 100% de probabilidades de que de 0 o 1.

Con esto ya podemos definir algunos qubits.

\(
\begin{pmatrix}
\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}}
\end{pmatrix}
\)

Este es mi qubit preferido. Representa el estado de superposición cuántica. Cada valor tiene el 50% de probabilidades de salir. \(|\frac{1}{\sqrt{2}}|^2 = \frac{1}{2}\). Cuando colapsemos el qubit al observarlo será como lanzar una moneda al aire.

Otro detalle que a veces se nos pasa por alto es que los qubits pueden contener valores negativos. Estos qubits son físicamente diferentes a los positivos, pero tienen las mismas probabilidades de colapsar en los mismos valores que los positivos.

\(
\begin{pmatrix}
-1 \\
0
\end{pmatrix}
\)

Es un qubit válido, que colapsa con 100% de probilidad a 0.

¿Cómo se representan los qubits en notación de Dirac? Representando la probabilidad que tiene cada combinación de bits de aparecer. Para un qubit sería algo así:

\(
\alpha | 0 \rangle + \beta | 1 \rangle
\)

Siendo \(\alpha\) y \(\beta\) las probabilidades de colapsar a cada estado.

Puertas cuánticas

Ahora vamos a ver cuáles son las puertas lógicas más importantes del mundo cuántico.

Negación (Pauli X)

Esta es exactamente igual que en el mundo clásico, con la misma matriz que hemos visto antes. Su símbolo es el cuadrado con una X.

Aquí vemos una imagen del simulador IBM Q usando la puerta X cuántica. IBM nos deja ejecutarlo en ordenadores cuánticos reales. Veamos los resultados.

¡Terrible! La mayoría de casos, el ordenador cuántico responde 1, el valor correcto, pero un 13% de los casos no. Teóricamente había una probabilidad del 100% y en la práctica solo es del 86.3%. ¡Y solo es una puerta X! Es por ello que los procesadores cuánticos todavía necesitan mejorar mucho. Google, Microsoft e IBM están investigando de forma independiente en ordenadores cuánticos. Veremos quién consigue tener antes ordenadores cuánticos precisos (aunque hay expertos que piensan que nunca se podrá lograr).

CNOT

Esta puerta es muy interesante. Toma dos qubits, uno de control, que permanece invariable al traspasar la puerta y otro de datos. Al qubit de datos se le aplica la puerta X si el qubit de control está activo. Su matriz es la siguiente:

\(
CNOT = \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{pmatrix}
\)

Se reprensenta de esta forma:

O similar, porque los símbolos de computación cuántica no están todavía muy estandarizados. El punto grande es el qubit de control y el punto pequeño está sobre el qubit de datos.

HADAMARD

Esta puerta es quizá la más famosa del mundo cuántico. Veamos su matriz:

\(
\begin{pmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{pmatrix}
\)

Esta puerta permite poner un qubit clásico en estado de superposición cuántica. Y también deshacerlo. Es muy usada en algoritmos cuánticos. Se representa con un cuadrado y una H.

Los resultados en el ordenador cuántico real de IBM Q son:

Cuando debería de ser bastante más cercano a 50% en los dos valores.

Con esto ya tenemos las puertas más usadas. Básicamente con Hadamard, X y CNOT se pueden implementar casi todos los circuitos cuánticos. Solo nos faltarían las puertas que operan entran en números complejos para poder implementar todos los circuitos.

Algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch-Jozsa es uno de los algoritmos cuánticos más sencillos de entender y que mejoran drásticamente el rendimiento respecto a un algoritmo clásico.

El planteamiento básico es que tenemos una caja negra que aplica una función sobre un bit. Estas funciones pueden ser: set-to-0, set-to-1 (ambas constantes), identidad (no cambiar nada) y X (ambas dinámicas) . Si queremos saber que función contiene la caja negra, ¿Cuántas veces tenemos que pasar valores? En una CPU clásica tendríamos que hacerlo dos veces para poder determinar que función contiene la caja negra. En una CPU cuántica… también. No hay diferencia. Pero, si cambiamos la pregunta a ¿de qué categoría es la función de la caja negra?, la cosa cambia. En una CPU clásica seguiríamos necesitando 2 pruebas, pero en una CPU cuántica y con un circuito por el exterior, podemos aprovechar la superposición cuántica para realizar una sola prueba y determinar si en el interior hay una función constante o dinámica.

Vamos a ver estas 4 funciones de la caja negra como son:

¿Se te ocurre como puedes crear un circuito fuera de la caja negra que con una sola prueba, ya sepa si estamos ante las funciones Set-0, Set-1 o Identidad, Negación?

El circuito es el siguiente:

Tal y como está diseñado si en q[1] medimos 0, la función es de tipo constante y si medimos 1, es de tipo dinámica. Un desarrollo matemático de los productos de matrices, como el que hay en Wikipedia, te mostrará como siempre es cierto. Este también es un ejemplo de como los ordenadores cuánticos pueden dar resultados totalmente deterministas.

Esta idea, se puede generalizar y extrapolar a otros problemas, generando una colección muy interesante de algoritmos que se ejecutan en tiempo exponencialmente menor que en una CPU clásica.

Algoritmos de Shor y de Grover

Estos dos algoritmos han sido llamados los killer apps de la computación cuántica, ya que son algoritmos que mejoran sustancialmente (uno de forma exponencial, otro de forma cuadrática) los tiempos de problemas reales.

El algoritmo de Shor fue el primero en ser descubierto, en 1994 por Peter Shor. Sirve para factorizar números (es decir, sacar los números primos que multiplicados generan el número original). Lo puede hacer en \(O((\log{n})^3)\). De este modo, los algoritmos tipo RSA que se basan en la factorización de números podrían romperse en tiempo polinómico, por lo cuál RSA ya no serviría como protección. El algoritmo de Shor no da siempre los resultados correctos, pero tiene una probabilidad de éxito superior a la de fracaso, por lo que con repetir múltiples veces la ejecución podríamos estar casi seguros del resultado.

El algoritmo de Grover fue descubierto en 1996 por Lov Grover y permite buscar en una lista no ordenada de datos en \(O(\sqrt{n})\) mientras que en una computadora clásica sería \(O(n)\).

Estos dos algoritmos sin duda marcan lo que se ha llamada la supremacía cuántica y que ocurrirá cuando los ordenadores cuánticos puedan ejecutar con suficiente precisión estos algoritmos y su utilidad en el mundo real supere a la de los algoritmos clásicos.

Entrelazamiento cuántico

Ya hemos visto las bases de los circuitos cuánticos. Ahora veamos algunas consecuencias de todo lo anterior. Cosas cuánticas que parecen hasta cierto punto fuera de la lógica. ¿Qué ocurre si tenemos varios qubits en un estado como este?

\(
\begin{pmatrix}
\frac{1}{\sqrt{2}} \\
0 \\
0 \\
\frac{1}{\sqrt{2}}
\end{pmatrix}
\)

En este estado solo puede colapsar a 00 o a 11. ¿Esto qué significa? Significa que los qubits están entrelazados entre sí, uno depende de otro, si los separamos y uno colapsa a 0, el otro colapsa a 0. Si uno colapsa a 1, el otro colapsa a 1.

Es importante destacar que los qubits pueden separarse en este estados. Los qubits alejados a millones de kilómetros siguen entrelazados y el valor al que deciden colapsar se decide de forma instantánea. Esto quiere decir que se sincronizan a una velocidad superior a la de la luz. El truco es que no se transmite información, por eso el universo lo permite, pero esto permite realizar la teletransportación cuántica.

La forma de entrelazar qubits es muy sencilla, con una puerta Hadamard y una CNOT.

IBM Q todavía tiene que mejorar, pero se aprecia claramente el entrelazamiento cuántico.

Teletransportación cuántica

La teletransportación existe, al menos entre qubits. Y es instantánea (más o menos). La teletransportación cuántica la podemos provocar usando varios qubits entrelazados. Necesitamos 3 qubits. El qubit que va a ser teletransportado, un qubit del emisor y un qubit del receptor. La idea es entrelazar el emisor con el receptor (qubit de destino) y posteriormente el qubit del emisor con el qubit que va a ser transportado.

No he sido capaz de hacer que IBM Q haga una teletransportación, así que aquí viene un esquema distinto. T es el qubit a transportar, A es el emisor y B el receptor. En este ejemplo se usa la puerta Pauli Z, cuya matriz es la indicada.

El truco de la teletransportación instantánea tiene que ver con que A y B tienen que estar entrelazados, por tanto, han tenido que ser transportados a sus respectivos lugares anteriormente a velocidad inferior a la luz.

Esto teletransporta qubits pero no hace copias. Esto es debido al Teorema de No Clonación.

Lenguajes de programación

Mientras esperamos a que los ordenadores cuánticos sean lo suficientemente estables, ya existen lenguajes de programación que podemos usar en simuladores. Quizá el más conocido sea Q# de Microsoft (funciona en Linux, tranquilos), que guarda similitudes con C#. Otro bastante usado es OpenQasm de IBM, algo más parecido a ensamblador.

Este es un ejemplo de lanzar la moneda con entrelazamiento cuántico en Q#, el lenguaje cuántico de Microsoft.

Referencias

Quantum Computing for Computer Scientists
Cats, Qubits, and Teleportation: The Spooky World of Quantum Algorithms
Microsoft Quantum Development Kit: Introduction and step-by-step demo
Qubit