Vida de un Programador

Experiencias, ideas y programas

Challenge 19: Find the algorithm

Este reto era un verdadero quebradero de cabeza, porque debias darte cuenta de diferentes cosas que ocurrian al transformar una cadena en la otra.

Esta fue la pista que dieron por Twitter:

Como vi mas adelante, la pista, si sabes que buscar, es bastante útil. Ahora veremos como convertir la entrada en la salida, y el proceso que yo seguí.

Si decodificamos la entrada mediante base64 nos aparecen una serie de caracteres hexadecimales que parecen seguir cierto patrón, en grupos de 8 caracteres (4 bytes al transformar).

bc79f103bc79f101bc79f0fcbc79f0fbbc79f0eabc79f0f7bc79f10abc79f105bc79f101...

Lo primero que pensé es que esos bytes eran los pixeles de alguna imagen, pero tras pintar un rato de todas las formas posibles caí en la cuenta de que eran muy pocos pixeles.

Entonces empece a analizar la salida, tambien codificada con base64. Entonces aparece una cadena “aparentemente” mexclada de caracteres hexadecimales, pero que luego contenia tambien patrones.

de3cf881bcdbfbc79f0ea3778f3e214db87ef1e7c48378f3e26073dbc79f129418de3cf89...

Eso si, los patrones se repetían de forma impar, por lo que en algún momento se produciría desplazamiento de bits.
Esto me llevo a analizar la entrada/salida en binario.

Os acordáis de la pista que puso @TuentiEng?
“let the Words see the light” => “Word” son 2 o 4 bytes (depende de donde se mire), y pueden formar un numero. Al pasar de hexadecimal a decimal (y solucionar unos problemas con la “endianness”, vi que todos los números estaban muy próximos.
” look how different they are” => si te fijas, las difererencias de un numero tras otro es muy pequeña.

La pista que acompañaba el reto la vi un poco tarde, pero me ayudo a terminar de comprender que no tenia que eliminar información, sino comprimirla.

This input is pretty compresshensible, isn’t it?😉

“compresshensible” indica que tienes que comprimir la entrada. Siempre jugando con nosotros xD

No comentare los pasos que di a partir de aqui, ya que son mas o menos 9 horas por la noche (con algunos razonamientos absurdos que deseche). A las 4:30 del 6 de mayo conseguí la estructura del archivo comprimido. Con esto ya podría crear un compresor y enviar el reto!

–Estructura de un bloque–

1 => bit de inicio
10111100011110011111000100000011 => número inicial del bloque
011110 -|
011011  |-=> números de 5 bits con complemento a 2 + un 0 inicial
011111 -|

A continuación se repiten los bloques hasta el final del archivo, que se rellena con 0’s para que la longitud total sea divisible entre 8. Los números de 5 bits pueden ser 0 o mas (ahora explico como funciona)

–Compresión–

La compresión se realiza de la siguiente manera:

  • Consigo un numero de la entrada (4 bytes)
  • Si la diferencia con el numero anterior es mayor que 15 o menor que -16, se añade a la salida su representacion binaria con un 1 al principio
  • En otro caso, se añade el numero resultante de la diferencia en binario (numero de 5 bits) con un 0 delante
  • Se continua esto con todos los números
  • Se añaden los 8’s finales para que la longitud sea divisible entre 8
  • Se convierte a hexadecimal
  • Se codifica en base64 y se le eliminan los simbolos “=” del final de la cadena

Este reto lo entregué aproximadamente a las 5, así que debido al sueño arrastrado intente un poco el reto 20, pero luego descansé.

Os dejo la estructura completa de la salida (hecha a mano)

–Estructura completa–

1 10111100011110011111000100000011 011110 011011 011111
1 10111100011110011111000011101010 001101
1 10111100011110011111000100001010 011011 011100 001111
1 10111100011110011111000100100000
1 10111100011110011111000100110000 001110 011110
1 10111100011110011111000100101001 010000 011000
1 10111100011110011111000100100100 010000 001000 000001 000111 011101 011101 011101 011001 000110
1 10111100011110011111000100001001 001010 000011
1 10111100011110011111000100000010 000110 001101 010000 010101 001111 001101 001011 001111
1 10111100011110011111000101000010 011010 011110 001100
1 10111100011110011111000100110010 010100 011111 011101
1 10111100011110011111000100010000 001011 011001 011001 000100 011101 000010
1 10111100011110011111000011111110
1 10111100011110011111000011101100
1 10111100011110011111000011011001 011011 001101 011010 001001 000111 010011 000110 000011 001011
1 10111100011110011111000011011110
1 10111100011110011111000011001011 000010 011111 010010 000111 000000 000000 010000 000011 010111 001111 011111 001000 000000
1 10111100011110011111000011011001 010111 001101 011101 011001 001110 011111 000011 000000
1 10111100011110011111000011010010 001001
1 10111100011110011111000011101110
1 10111100011110011111000011011100 011111 010010 000110
1 10111100011110011111000011100111
1 10111100011110011111000011111000 000101 000010 010110 001110 010110 011010 000011
1 10111100011110011111000011100101 000001 001100 011100 000000 000101 011111 001111 000110 011000 010100 000010 010010
1 10111100011110011111000011111000
1 10111100011110011111000100001010 001101 001010
1 10111100011110011111000100110001 011010
1 10111100011110011111000100111111 001011 000100 001110 011010
1 10111100011110011111000101000101 000110 011001
1 10111100011110011111000101011000
1 10111100011110011111000101000110 001000 010100 011011 010011 010001 011100 010110 010001 011111 001111 010111 000110
1 10111100011110011111000011111100 010011 000001 000010 011101 011101 000001 010011 000011
1 10111100011110011111000011110101 001001 000000 001111 010001 010011 000101 000000 001011 011111 010011 000001 001110 010101
1 10111100011110011111000100001000 000000 001001
1 10111100011110011111000011111111 011011 010011 000011
1 10111100011110011111000100000100 011000
1 10111100011110011111000100001101
1 10111100011110011111000011111011 001010 010001 011110 001101 000001 000101
1 10111100011110011111000100011001
1 10111100011110011111000100101101 010000 010110 011010 000010
1 10111100011110011111000011111101 010010 010010 011001 010001 000001 001000 010000 010011 011110
1 10111100011110011111000011001000 011011
1 10111100011110011111000011010100
1 10111100011110011111000011000001 010001 011111 010100 001011 010101 001010
1 10111100011110011111000010011101 000111
1 10111100011110011111000010010010 001100 000101
1 10111100011110011111000010001111 010111 010100 001001
1 10111100011110011111000010010110
1 10111100011110011111000010100110 011011 000001 010011 001001 010001 000000 011110 011100 010011 011001
0

5 Respuestas a “Challenge 19: Find the algorithm

  1. Jacob Strauss (@jacob_strauss) 08/05/2012 en 19:49

    En este problema es donde me quedé yo, y las pistas que dieron por Twitter no me ayudaron en nada. Si que llegué a que se repetían trozos de la entrada en la salida, y estaba comparando la entrada y la salida en binario después de decodificarla en Base64, pero no conseguí ver la relación. Enhorabuena por verlo.

    • shoghicp 08/05/2012 en 19:56

      Costo mucho, por poco no lo paso. Muchos al principio optaron por crear imagenes, asi que les daba la pista “no colorees”, para ahorrar eso. Pero no mas😉

  2. Miguel Angel Julian (@djthar) 09/05/2012 en 08:37

    Llegué a éste problema muy tarde. Pude ver la entrada y la salida descodificada y en binario, y sabía que la salida era una compresión de algún tipo de la entrada, pero no fui capaz de encontrar el algoritmo de compresión. Aun así, ahora que lo veo resuelto, el algoritmo me recuerda a la compresión temporal de MPEG2. Era complicado, enhorabuena por descifrarlo. Todos los que pasasteis de éste sois unos verdaderos cracks

    • shoghicp 09/05/2012 en 12:34

      Si, busque muchos algoritmos ya implementados, y los que empecé a probar eran compresores de números enteros positivos

  3. Rober Morales (@robermorales) 09/05/2012 en 12:00

    Yo llegué a ver los números en binario, pero no vi cuál era la relación. Llegué a dibujar códigos de barras con los unos y ceros para intentar escanearlos después (sin éxito). Probé algoritmos de compresión conocidos Huffman, deflate, zlib, bz2, y algunos otros. Probé a crear imágenes y guardarlas como PNG o JPG (tanto RGB y RGBA como CYMK guardado en tiff) para ver si la información comprimida tenía algo que ver con la salida (sin éxito también, claro, aunque había una configuración que conseguía un tamaño en la salida muy similar al esperado, pero no coincidía nada). Probé a hacer un excel con todos los números de 4bytes en 4bytes y graficarlos, así como sus diferencias, y sus módulos con todos los números hasta el 32 y algunas potencias de dos. Nada de nada: aleatoriedad total. Bueno, sí, en la entrada de ejemplo la diferencia entre el número mínimo y el máximo era menor de 255, pero este offset no conformaba una salida en ascii ni nada parecido: la distribución de frecuencias era bastante normal, no parecía haber datos ni mensajes ahí. Además, clusterizé los bytes para hacer un histograma tomando diferentes tamaños. Nada de nada. Era un problema de tener suerte y que se te ocurriera cuál era el enunciado. Con esto no te quiero quitar mérito, que lo tienes: ¡¡¡Enhorabuena!!!

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: