Diffchecker: comparando secuencias

Si alguna vez has programado alguna vez usando un repositorio, habrás usado una herramienta de diff para comparar el código antiguo y el nuevo, y detectar qué fragmentos han cambiado y qué fragmentos son comunes a ambos.

Ejemplo de diff checking

Este algoritmo parece sencillo hasta que nos paramos a pensar en su funcionamiento un rato. Por ejemplo, si queremos comparar las palabras schwarzenegger y chuarcheneger, obtenemos el siguiente resultado:

  ANTES:  s c h w a r z . e n e g g e r
DESPUES:  . c h u a r c h e n e g . e r
CAMBIOS:  - = = / = = / + = = = = - = =

En el cambio hemos eliminado 2 letras, modificado 2 letras y añadido una letra. Este análisis, que no es tan simple de realizar con nuestra inteligencia natural, tampoco tiene una solución algorítmica trivial.

Subsecuencia común más larga (LCS)

En algoritmia, este problema se conoce como LCS. El objetivo de LCS es, dadas dos secuencias, encontrar la subsecuencia más larga que ambas tienen en común.

Como las herramientas de diff sólo comparan entre sí dos cadenas, existe una solución mediante un algoritmo divide y vencerás, que va reduciendo el problema a otros problemas más pequeños. Así, se puede definir el problema de la siguiente forma:

def LCS(X, Y):
    if len(X) == 0 or len(Y) == 0:
        return []
    if X[-1] == Y[-1]:
        return LCS(X[:-1], Y[:-1]) + [X[-1]]
    else:
        return longest(LCS(X, Y[:-1]), LCS(X[:-1], Y))

Donde longest es una función que sencillamente devuelve la cadena más larga:

def longest(X, Y):
 return X if len(X) > len(Y) else Y

Teniendo el algoritmo LCS (que podéis probar en Python), es fácil averiguar qué se ha añadido, eliminado, o modificado al comparar dos cadenas. Sin embargo, es un algoritmo muy lento. Basta con que pongamos dos cadenas algo más largas (como arn. schwarzenegger y ar. chuarcheneger) para que el tiempo de ejecución se dispare.

Por eso es necesario el uso de una memoria que almacene los resultados, a fin de no tener que computarlos más de una vez. Haz la prueba:

Esta es la base de este algoritmo, aunque hay que detallar ciertos matices para que funcione correctamente; convertir el algoritmo recursivo en uno iterativo para evitar exceder el límite de recursión, utilizar estructuras de datos que permitan un cálculo más eficiente, o tokenizar las secuencias para considerar que cada elemento puede ser una fila de código o una palabra en lugar de un caracter.

No hay comentarios

Python Challenge

Python Challenge es una web con pequeños retos que sólo pueden ser resueltos programando. Estos retos están organizados en niveles que se van desbloqueando conforme resolvemos el anterior.

Los niveles tienen cierto halo de misterio sobre qué debemos hacer, que invitan al pensamiento lateral y lo hacen muy adictivo. Aunque se pueden resolver usando otros lenguajes, las pistas y las soluciones están muy orientadas hacia Python, para motivar a aprender un poco más sus las librerías y funcionalidades específicas.

En este post describo las soluciones a los primeros 20 niveles de este challenge que he conseguido resolver, con un enlace a cada nivel en el título. Puedes encontrar el código de las soluciones en Github.

Nivel 0: Warming up

Este es un nivel introductorio en el que sólo tendrás que calcular la potencia que se muestra en la imagen, y sustituir en la URL el 0 por el valor de esta. Este método de navegación reemplazando partes de la URL es muy común en los Riddle games.

Nivel 1: What about making trans?

De nuevo, un nivel muy sencillo, en el que el propio título de la página nos dice qué hacer. Nos dan un texto cifrado por rotación y nos dicen qué rotación tenemos que hacer, usando maketrans para solucionarlo. Al hacerlo, obtenemos este texto:

i hope you didnt translate it by hand. thats what computers are for. doing it in by hand is inefficient and that's why this text is so long. using string.maketrans() is recommended. now apply on the url.

Haciendo el mismo maketrans sobre la URL llegamos al siguiente nivel.

Nivel 2: OCR

El propio nivel nos dice que miremos el código fuente. Al mirarlo encontramos dos comentarios, el primero de ellos:

find rare characters in the mess below:

Seguido de una cadena de caracteres sin sentido. Al quedarnos sólo con las letras de la cadena obtenemos la clave para el siguiente nivel.

Nivel 3: Re

La pista nos sugiere que busquemos una letra minúscula rodeada de exactamente 3 letras mayúsculas a cada lado. Utilizando expresiones regulares hacemos la búsqueda [^A-Z][A-Z]{3}([a-z])[A-Z]{3}[^A-Z] y encontramos unas cuantas letras que juntas forman la solución a este nivel.

Nivel 4: Follow the chain

Al hacer click en la imagen, llegamos a una página terminada en ?nothing=12345 con el siguiente texto:

and the next nothing is 44827

Al cambiar el número en la URL llegamos a otra página igual, que de nuevo apunta a otro número distinto. Parece que podríamos llevarnos así todo el día, por lo que habrá que hacer uso de una librería de peticiones HTTP, como es el caso de urllib (incluida en Python) o requests.

Por medio de la navegación nos encontraremos una excepción: un nivel en el que hay que dividir entre 2 uno de los códigos. Quitando esto el nivel no tiene mayor complicación, seguimos 250 páginas y llegaremos al enlace al siguiente nivel.

Nivel 5: Peak hell

La pista en este caso es el título del nivel, que suena sospechosamente parecido a Pickle, la librería de serialización de objetos en Python.

En el código fuente encontramos un archivo pickle. Al importarlo y examinarlo un poco, se ve que es una lista de líneas de un texto. Cada línea, en vez de ser una lista de caracteres, es una lista de pares (carácter, repeticiones). Al reconstruir el texto, obtenemos un bonito ASCII art:

ASCII art solución al nivel 5 del Python Challenge

Nivel 6: Now there are pairs

Este nivel es bastante parecido al 4º. Nos muestran una imagen de una cremallera (zip en inglés), y al cambiar la extensión de la imagen de png a zip, encontramos un archivo comprimido con muchos archivos txt y un readme, que reza:

welcome to my zipped list.

hint1: start from 90052

hint2: answer is inside the zip

Si navegamos por los archivos del mismo modo que en el nivel 4, esta vez usando la librería zipfile para llegar hasta el final encontraremos el texto "collect the comments". Sin embargo, este texto no es la solución al problema.

Como en los archivos zip existe un campo de comentarios para los archivos, vamos guardando los comentarios de cada uno conforme navegamos. Al juntarlos todos, de nuevo obtenemos un mensaje en ASCII art.

En este caso, el ASCII art está pensado para despistar. La palabra que forma no es relevante, pero sí lo son los caracteres que forman las letras.

Nivel 7: Smarty

Este nivel nos muestra una imagen con un extraño patrón de tonos de gris. Al leer la intensidad de gris de cada uno de los cuadrados, obtenemos la siguiente serie: 105 110 116 101 103 114 105 116 121 Si transformamos cada uno de estos números en un caracter ASCII, obtenemos la palabra integrity, clave para el siguiente nivel.

Nivel 8: Working hard?

En el código fuente de este nivel vamos un username y un password que están comprimidos mediante bzip2. Usando la librería bz2 de Python, obtenemos el username (huge) y el password (file). Al hacer click en la imagen, nos pide un usuario y una contraseña, que son los que acabamos de averiguar, y nos lleva al siguiente nivel.

Nivel 9: Connect the dots

De nuevo, al observar el código fuente, encontramos dos cadenas, en este caso dos secuencias de números. Tras analizarlas un poco, descubrimos que los números pares son cercanos entre sí y los impares también en ambas secuencias. Considerando cada secuencia una lista de pares de números podemos usar el módulo ImageDraw de la librería PIL para construir una figura que nos dará la clave del siguiente nivel.

Vaca solución al nivel 9 del Python Challenge

Por cierto, si ponemos ''cow'' como solución nos dirá que nos hemos equivocado de sexo, una guía muy acertada para no despistar al jugador que lo ha resuelto.

Y hasta aquí he llegado. En el siguiente post hablo de los niveles 10-17.

Nivel 10: What are you looking at?

En este nivel encontramos una imagen con un enlace a una secuencia de números. Como es una secuencia de enteros, podemos hacer una búsqueda en OEIS para ver si es conocida, y efectivamente. Es la secuencia Look and Say, que consiste en describir con números el anterior número.

La serie funciona así:

Nivel 11: Odd even

Observamos una imagen con un efecto extraño, como esas imágenes de Whatsapp que tienen una miniatura y al abrirlas son otra cosa distinta. Fijándonos un poco más vemos que son dos imágenes intercaladas, y al quedarnos con los píxeles con coordenadas impares obtenemos la clave para el siguiente nivel.

Solución al nivel 11 del Python Challenge

Nivel 12: Dealing evil

De nuevo una imagen con un efecto extraño en sus píxeles. Confieso que me llevé bastante tiempo en este nivel. Tras adquirir cierta experiencia con este tipo de retos, sospeché cuando vi que la imagen del nivel se llamaba evil1.jpg, así que probé a poner evil2.jpg y ¡bingo! la imagen nos explica que debemos cambiar la extensión a gfx.

Como curiosidad, al probar evil3.jpg nos topamos con el texto "no more evils…", y al probar evil4.jpg encontramos una imagen que en realidad es un archivo de texto que dice: "Bert is evil! go back!".

Tras mucha desesperación, decidí abrir la imagen con un editor hexadecimal, y me encontré la clave para solucionar el nivel, la etiqueta ÿOÿà que identifica el inicio de un archivo jpeg.

Imagen del nivel 12 abierta con un editor hexadecimal

La etiqueta aparece de forma discontínua varias veces, al igual que la etiqueta GIF8. Si tomamos uno de cada 5 píxeles y lo convertimos en 5 imágenes, obtendremos la clave para el siguiente nivel: disproportional.

Nivel 13: Call him

Observando el código fuente encontramos un enlace a un servidor XML-RPC. Al hacer listMethods() en él, encontramos un único método definido, phone. Ya que la pista del nivel es "phone that evil", y sabemos que Bert es evil por el nivel anterior, llamamos a Bert, y obtenemos la solución del nivel.

A estas alturas, los niveles se complican hasta un nivel bastante poco intuitivo. Perdí muchas horas porque llamar a bert no daba ningún resultado si la B no era mayúscula.

Nivel 14: Walk around

Este nivel es bastante sencillo en comparación con el anterior: nos encontramos una imagen de una ensaimada (en forma de espiral) y abajo, una imagen que al abrirla sólo tiene 1px de altura.

Al enrollarla en forma de espiral, obtenemos la imagen de un gato. Ponemos cat en la URL, y nos enseña el gato, cuyo nombre es Uzi. Ponemos Uzi en la URL, y llegamos al siguiente nivel.

Nivel 15: Whom?

Encontramos una imagen peculiar, de un calendario del año 1XX6, en el que febrero tuvo 29 días, y el lunes fué día 26. La pista en este caso está en el código fuente, y es "buy flowers for tomorrow ". Ya que la pregunta es whom?, una simple búsqueda en Wikipedia del día 27 de enero nos da una gran lista de personas que nacieron ese día. Si limitamos la búsqueda a años que sigan el patrón 1XX6, y que cayera en lunes, obtenemos un único resultado: el nacimiento de Wolfgang Amadeus Mozart.

Nivel 16: Let me get this straight

Tras varios niveles de este estilo, es bastante intuitivo de resolver. Si unimos toda la imagen en una única cadena de 1px de altura, y vamos introduciendo un salto por cada secuencia repetitiva de píxeles blancos y rosas que encontremos, obtenemos la clave del nivel:

Solución al nivel 16 del Python Challenge

Nivel 17: Eat?

Nos encontramos con una imagen de galletas (pista por excelencia sobre cookies) con una pequeña imagen que hace referencia al nivel 4.

Volviendo a este nivel observamos que una cookie nos dice "you should have followed busynothing". Ya que las urls de este nivel eran del tipo ?nothing=..., cambiamos la primera de ellas por ?busynothing=... y empezamos a seguir la cadena, mientras guardamos la información que nos va dando la cookie info. Obtenemos la siguiente frase:

is it the 26th already? call his father and inform him that "the flowers are on their way". he'll understand.

Una rápida búsqueda y descubrimos que su padre era Leopold Mozart. Ya que nos dice que le llamemos, usamos el teléfono del nivel 13 para llamar a Leopold, que nos dice 555-VIOLIN. Reemplazamos la URL por VIOLIN, lo que nos lleva a la página de Leopold, que nos pregunta qué queremos.

Desgraciadamente, aun no he conseguido avanzar más allá de este punto. Si sigo avanzando iré publicando actualizaciones a este post.

2 comentarios

El cifrado XOR

Hace algún tiempo pensé que sería interesante diseñar un ruido reversible, en el que la función f para encriptar y desencriptar fuera la misma, de manera que f(texto, contraseña) = f(cifrado, contraseña).

XorCrypt

Sigue leyendo si quieres saber cómo funciona.

Cifrado ROT-13

Los cifrados recíprocos existen desde hace mucho. Un buen ejemplo es el Cifrado ROT-13, que consiste en coger una letra del alfabeto, y rotarla 13 posiciones. Como el alfabeto (sin ñ) tiene 26 posiciones, si realizamos esta operación dos veces volvemos a la letra anterior: A -> N y N -> A.

Dial de cifrado ROT13

Cifrado XOR

Mi intención es disponer de un cifrado algo más seguro, que necesite una contraseña para encriptar/desencriptar. Y ahí es donde entra en juego el Cifrado XOR. Se basa en la operación lógica XOR (⊕), eXclusive OR:

ABA⊕B
000
011
101
110

Podemos realizar esta operación con un número si se la aplicamos a cada uno de sus bits. Por ejemplo, 220 ⊕ 153 = 69.

La magia del operador XOR es su reciprocidad: del mismo modo que 220 ⊕ 153 = 69, podemos observar que 220 ⊕ 69 = 153. Dado cualquier número A, la operación A ⊕ P = B y B ⊕ P = A. De este modo, podemos definir una contraseña P, que nos permita encriptar de forma reversible cualquier cadena, asignando un número a cada letra.

Así, si nuestra cadena es "HOLA MUNDO", nuestra constraseña es "CONTRASEÑA", y asignamos a cada letra la posición que ocupa en el abecedario reservando el 0 para el espacio; obtendremos la cadena encriptada "K BSRLBKKP".

Aplicando la operación de nuevo, con la contraseña "CONTRASEÑA" y la cadena "K BSRLBKKP", obtendríamos nuestra cadena tal y como queremos. Sin embargo, seguimos teniendo dos problemas:

Cadenas de distinta longitud

Una solución bastante simple es rellenar la contraseña con espacios hasta que tenga la longitud del texto. Sin embargo, esto no cambiaría nada, ya que A ⊕ 0 = A. Por ejemplo, con el texto "HOLA MUNDO ESTO ES UNA PRUEBA", la cadena que obtenemos es "K BSRLBKKP ESTO ES UNA PRUEBA".

Otra opción es rellenar la contraseña con algún símbolo que no sea un espacio. O para que sea menos predecible, repetir la contraseña en bucle. De este modo, para el texto anterior, usamos como contraseña "CONTRASEÑACONTRASEÑ", y el resultado de la encriptación es "K BSRLBKKPCTY CAPPÑ".

Gráfico de barras de la frecuencia (%) de las letras en castellano

Sin embargo, esta solución tampoco es segura, ya que al encriptar textos largos, sería fácil ver combinaciones de letras que se repiten mucho, y adivinar la contraseña mediante análisis de frecuencia. Pero todavía nos queda un recurso.

Funciones de hashing

En criptografía, las funciones de hashing son técnicas que permiten encriptar una cadena con un bajo coste, pero un coste altísimo de desencriptación, en ocasiones de milenios.

Este es el caso de la función SHA-256. Mediante esta función, podemos encriptar la contraseña y usarla para aplicar el cifrado XOR de forma segura. Para tener una contraseña más larga, tendremos una lista de salts que aplicaremos a la contraseña. No voy a entrar en detalle en esto último para que no quede un post demasiado largo, pero si tenéis interés podéis preguntar más en los comentarios.

Conclusiones

Después de todo esto hemos conseguido un cifrado recíproco medianamente seguro, y sobre todo, aprender un poco sobre criptografía.

Si lo deseas, puedes probar tú mismo este cifrado en esta página. Es una versión a la que he añadido un mayor número de caracteres.

1 comentario

Palabras encadenadas

Seguramente todos conocéis este juego. El otro día pensé cuál sería la cadena más larga de palabras encadenadas posible. En este post voy a intentar encontrarla.

Existen muchas variantes de este juego, así que mejor definimos un conjunto cerrado de reglas antes de empezar:

  1. El primer jugador dice una palabra cualquiera.
  2. Los siguientes jugadores deben decir una palabra que empiece por la última sílaba de la palabra anterior, ignorando los acentos.
  3. No se puede repetir una misma palabra 2 veces.
  4. Sólo son válidas palabras que figuren en la 23ª edición del diccionario de la RAE. Aunque figuren en el diccionario, nombres propios, siglas y monosílabos tampoco son válidos.
  5. Al encadenar las palabras, se ignoran sus acentos.

Datos

En primer lugar, necesitamos obtener todas las palabras del diccionario de la lengua española. Aunque la RAE no proporciona un listado completo de palabras, Giusseppe Domínguez nos lo facilita.

Tras esto, necesitamos la descomposición silábica de todas las palabras del diccionario. Puede parecer trivial, pero es una tarea bastante compleja, ya que hay un gran número de reglas y excepciones. Por suerte, la librería Pyphen hace ese trabajo decentemente por nosotros.

Finalmente, tenemos una lista de 86993 palabras válidas separadas por sílabas.

Palabras por número de sílabas en español

Secuencia más larga

Para calcular la mayor secuencia posible, construimos un grafo dirigido cuyos nodos son las palabras en cuestión, y las aristas comunican dos palabras que puedan ser encadenadas.

Ejemplo de grafo de palabras encadenadas

De esta manera, el problema se reduce a encontrar el camino dirigido más largo de este grafo. A diferencia del camino más corto, encontrar el camino más largo en un grafo es un problema NP-completo. Con un grafo de 86993 nodos y 43053416 aristas, tardaríamos 1.82 × 101012 años en encontrar la solución perfecta a este problema, así que debemos probar soluciones aproximadas.

Camino aleatorio

Escogiendo caminos de forma aleatoria, el camino más largo obtenido es de tan sólo 92 palabras:

sopa -> pantalla -> llaneza -> […] -> ramuja -> jagüel -> güeldrés

Esto se debe a que es fácil llegar a un sumidero, es decir, una palabra a la que es posible llegar, pero no es posible salir de ella, como es el caso de güeldrés.

Otras aproximaciones

Existen otras formas de resolver este problema, como:

¿Se te ocurren más formas de resolver este problema? ¿Cuál es la cadena más larga que has sido capaz de encontrar? Si lo deseas, puedes dejar un comentario con tus resultados.

3 comentarios

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y mejorar su calidad. Más información aquí.

4d8cd43bbbfbbd2b7aed08d9a2b0ef251cebfd3e2603b74b710a2d38b7f8ec39