Tuenti Challenge 10: niveles 15-17

Modificar animales genéticamente, planear la construcción de baños en un edificio gigante y encontrar el misterio escondido tras el póster de una película. Estos son los retos de este penúltimo post de la serie sobre el Tuenti Challenge 10. En mi repositorio de Github está el código de las soluciones que describo a continuación.

Nivel 15: The internsheep

En este nivel recibimos como entrada un archivo comprimido tarball de 11KB, que al ser descomprimido contiene el genoma de unos 100 animales, cada uno en un archivo de hasta 200GB. Lo primero que uno piensa al ver este archivo es que ante un ratio de compresión tan extremo tiene que haber gato encerrado, y no me refiero a su genoma.

Dediqué un precioso viernes a aprender cómo funcionaba DEFLATE, LZ2, los árboles de Huffman y hasta la vida y obra de Mark Adler, sólo para darme cuenta de que estos supuestos genomas son archivos cuyos bytes están todos a cero. No obstante, aprovecharé este conocimiento en futuros posts.

El problema nos pedía que introdujéramos ciertas modificaciones en el genoma de uno de los animales. Estas modificaciones venían definidas como un par (p, b), donde la p indica la posición en el archivo en la que debemos insertar el byte b.

Como no podemos enviar un archivo de 200GB, el problema nos pedía calcular el CRC32 del archivo resultante. El CRC32 es una cadena de control —algo así como la letra del DNI— que se calcula a partir de una secuencia de bytes como un archivo. Es muy frecuente que las descargas online vayan acompañadas de un CRC32 como medida de seguridad.

Así, una vez descargado un archivo podemos calcular su CRC32 byte a byte, y compararlo con el que nos dice la web para saber si ha habido algún error durante la descarga, ya que hasta el menor cambio en un archivo produce una alteración grande en el CRC32.

A primera vista parece un problema fácil: podemos mirar los metadatos del archivo comprimido para saber cuál es la longitud del archivo que quedemos modificar (y por tanto la secuencia de ceros que representa ese genoma), realizar las alteraciones que nos piden y calcular el CRC. Sin embargo, calcular el CRC32 de una cadena tan larga requiere semanas de cómputo en un ordenador convencional.

Por suerte, la librería zlib incluye una función llamada crc32_combine que aprovecha las propiedades de este algoritmo para calcular rápidamente el CRC32 de la concatenación de dos cadenas a partir del CRC32 de sus partes:

crc_combine(crc(A), crc(B), len(B)) = crc(concatenate(A, B))

Así, para calcular el CRC de una lista de 1024 ceros, sólo tendríamos que calcular el CRC de un único cero, usar esta función para calcular el de una secuencia de dos ceros, volverla a usar para calcular una de cuatro… y en definitiva, reducir el orden de este cálculo de forma logarítmica.

De este modo, sabiendo que todos los bytes de los archivos están a cero, podemos ver el tamaño de las secuencias genómicas en los metadatos del archivo comprimido e ir actualizando el CRC32 conforme intercalamos secuencias de ceros con los bytes que debemos insertar.

Nivel 16: The new office

Este problema nos sitúa en una oficina en un gran edificio de hasta 2000 plantas (el Burj Khalifa tiene 163) en el que trabajan muchos empleados. Hay un problema de salubridad importante: el edificio no tiene baños.

Tenemos que calcular el mínimo número de baños a construir, sabiendo que debe haber el mismo número de baños en cada planta, y que todos los empleados deben ser capaces de acceder al baño al mismo tiempo.

Los empleados están organizados en grupos: un empleado pertenece a un único grupo y cada grupo sólo tiene acceso a ciertas plantas. Dado que puede haber hasta 400 grupos de 2000 empleados en el edificio, realizar este cálculo mediante fuerza bruta no es una opción.

Siempre que veo un problema de este tipo, en el que hay muchos elementos distintos (plantas, grupos, empleados) que tienen cierta relación entre sí, algo me dice que usar grafos puede ser la solución. En este caso, el problema se puede resolver mediante grafos de flujo.

Estos grafos se usan habitualmente para modelar redes por las que un flujo recorre una serie de tuberías de una cierta capacidad, como en redes de transporte, circuitos eléctricos o sistemas de fluidos. En este problema, queremos medir el flujo de personas, asegurando que todas las personas que fluyen desde cierto grupo de empleados hacia las plantas autorizadas puedan usar los baños.

Red de flujo del problema

La imagen de arriba representa este problema. Hay tres grupos de empleados: G1, que puede ir a las plantas 2 y 3; G2, que puede ir a las plantas 0, 1 y 3; y G3, que sólo puede ir a la planta 0. Además, G1 está formado por 3 empleados, G2 por 5 y G3 por 1. Esto significa que el flujo de personas que llega a cada grupo es de 3, 5 y 1 respectivamente.

A continuación, estas personas se distribuyen lo mejor que pueden, como si de un fluido se tratase, entre los baños de cada planta; de ahí que las aristas que van de un grupo de empleados a una planta no tengan un límite en su capacidad.

Una vez modelado el problema, resolverlo se reduce a encontrar el menor número de baños posible w, que se corresponde con la capacidad de las aristas de salida en nuestro grafo.

Al diseñar este grafo con el problema original, e ir aumentando w hasta que el flujo que llega a t sea igual al número de empleados, mi ordenador tarda aproximadamente 2 horas en resolver algunos problemas. Pero todavía queda una optimización posible.

Como sabemos que w está en el rango (0, num_empleados), podemos calcular el flujo de salida en el punto medio p = num_empleados / 2. Si p es igual al número de empleados, existe la posibilidad de que podamos encontrar un w menor, por lo que w está en el rango (0, p). En caso contrario sabemos que w está en el rango (p, num_empleados).

Podemos seguir reduciendo el rango hasta encontrar una solución mucho más rápido, concretamente, en un máximo de log2(num_empleados) pasos. Este método se conoce como el método de la bisección.

Nivel 17: Zatoichi

De nuevo, este nivel no tiene más enunciado que una imagen.

Póster desordenado de Zatoichi.

Esta imagen es el póster de la película de 2003 Zatōichi, que cuenta la historia de un espadachín ciego interpretado por Takeshi Kitano. Esto nos puede dar una pista de por dónde puede ir la solución.

Además, la imagen esté desordenada y seguramente reordenarla sea el primer paso para resolver este problema. Para hacer esto tendremos que trabajar con los propios píxeles de la imagen y guardarla de nuevo, por lo que toda la meta-información que pueda estar oculta se perderá.

Teniendo esto en cuenta, es probable que no haya metainformación oculta y la clave del problema esté en los propios píxeles de la imagen. Los trucos para esconder información en un archivo se conocen como esteganografía, y una de los más conocidos consiste en esconder información en el bit menos significativo de cada canal de color.

El truco es bastante sencillo. Al representar un color en una imagen, cada pixel se suele representar como un conjunto de 3 bytes, que codifican los valores del rojo, verde y azul entre 0 y 255. Como en la práctica nadie va a notar que un pixel rojo tenga valor 136 o 137, podemos usar ese último bit de cada byte para esconder información.

Animación de imágenes creadas por cada bit del póster

Si observamos el plano que se crea al usar todos los bits en cierta posición, vemos que los que están en la posición 0 crean una imagen muy estructurada que no tiene nada que ver con la imagen original. Durante el concurso dediqué mucho tiempo a hacer pruebas con este plano: analizarlo, desplazarlo, convertirlo a texto y hasta transformar el XOR de sus tres canales de color en un pentagrama y tocarlo con el piano.

Sin embargo la respuesta era mucho más sencilla: si leemos todos esos bits de arriba a abajo y de izquierda a derecha, extraeremos una cadena que se repite muchas veces.

CONGRATULATIONS, YOU FOUND THE HIDDEN MESSAGE, WILL YOU BE ABLE TO DECODE IT?
E2A089E2A095E2A09DE2A09BE2A097E2A081E2A09EE2A0A5E2A087E2A081E2A09EE2A08AE2A095E2A09DE2A08E20E2A0BDE2A095E2A0A520E2A099E2A091E2A089E2A095E2A099E2A091E2A09920E2A09EE2A093E2A09120E2A08DE2A091E2A08EE2A08EE2A081E2A09BE2A09120E2A09EE2A093E2A09120E2A08FE2A081E2A08EE2A08EE2A0BAE2A095E2A097E2A09920E2A08AE2A08E20E2A09EE2A093E2A09120E2A08BE2A095E2A087E2A087E2A095E2A0BAE2A08AE2A09DE2A09B20E2A0BAE2A095E2A097E2A09920E2A08AE2A09D20E2A0A5E2A08FE2A08FE2A091E2A097E2A089E2A081E2A08EE2A09120E2A09EE2A081E2A085E2A091E2A08EE2A093E2A08AE2A085E2A08AE2A09EE2A081E2A09DE2A095E2A083E2A08AE2A09EE2A095E2A09EE2A081E2A085E2A091E2A08EE2A093E2A08AE2A093E2A0A5E2A08DE2A095E2A097E2A081E2A08DE2A081E2A097E2A08AE2A087E2A087E2A095E2A0BCE2A083E2A0BCE2A09AE2A0BCE2A083E2A0BCE2A09AE2A09EE2A0A5E2A091E2A09DE2A09EE2A08AE2A089E2A093E2A081E2A087E2A087E2A091E2A09DE2A09BE2A091E2A0BCE2A081E2A0BCE2A09A

Un último obstáculo antes de llegar al final. La cadena cifrada está formada por muchos códigos de seis letras que empiezan por E2A0. Una búsqueda en la web del primero de ellos nos revelará que son códigos unicode de caracteres braille.

Por ahí iba la pista de Zatōichi. Si descriframos cada uno de estos caracteres y los traducimos usando el braille inglés (sí, cada idioma usa un braille ligeramente distinto) encontraremos la solución.

Y este fue el último nivel que resolví con éxito durante el concurso. Sin embargo, he dedicado algún tiempo para conseguir resolver el submit del siguiente nivel (sólo conseguí resolver el test) y lo contaré en el próximo post.

Sé el primero en comentar

Recibir un mail

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.