Vida de un Programador

Experiencias, ideas y programas

Challenge 17 – Silence on the wire: Identificando luces con CRC32

Descripción del reto

Descripción del reto

En este reto la descripción era corta. Primero, en el título se incluye el libro Silence on the wire, y una referencia al capítulo 5 Blinkenlights. Para quien no tenga ese libro, el capítulo empezaba hablando sobre NRZ, una codificación para enviar mensajes binarios entre ordenadores con relojes no sincronizados. Terminaba hablando sobre el escape de información de los dispositivos antiguos con lucecitas, y métodos para limitar ese escape.

También se incluía un vídeo, comprimido en 7Z, y se descomprimía en un AVI de 4.95GB. Mi primera reacción fue encodearlo en un tamaño mas pequeño (aunque luego no usé), que he subido para que tengais algo de contexto😉

Avanzando cuadro por cuadro en VirtualDub

Avanzando cuadro por cuadro en VirtualDub


Tras abrirlo con VLC y ver unos segundos, siguiente paso fue abrirlo con VirtualDub y ver los cuadros de forma individual. Avanzando, ya tenia la idea en mente de 0 y 1 como los valores para los fotogramas.
Siguiendo el consejo del libro, implementé NRZ, y probé a alimentarle los primeros “bits” del vídeo. Eso no dio resultado, así que probé a pasarlo directamente a bytes… Bingo!

GET / HT

Eso es parte de una petición HTTP, así que… a pasar todos los bits!

Había 3424 bits, pero empecé a pasarlos a mano. Cuando iba por el ~400, pensé en extraer todos los cuadros a PNG y comprobar su CRC para ver si eran similares. Tras extraerlas con VirtualDub, acabe con miles de imágenes, que en total, ocupaban 1.39GB (¡menos que el vídeo!). Tras comprobar varios 1s y 0s, el CRC se mantenían. Por lo que:
48618FB8 = 0
84A854B9 = 1

Ahora solo quedaba escribir el programa que lo leería, (comentado en mi solución), que escribió en pantalla (lentamente):

GET / HTTP/1.1
Host: silence.contest.tuenti.net
Connection: keep-alive
Cache-Control: max-age=0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.43 Safari/537.31
Accept-Encoding: gzip,deflate,sdch
Accept-Language: en-US,en;q=0.8
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3
Cookie: adminsession=true

Entonces, solo había que navegar a silence.contest.tuenti.net. Como la pagina estaba prohibida, comprobé de nuevo la petición, vi la cookie “adminsession”, la edité en el navegador, y obtuve finalmente lo que había que realizar en el problema.
For each input N return the sum of digits of N!

Bueno, hay que encontrar la suma de los digitos del factorial de N!. Aquí, ya que es un cálculo bastante lento, se puede optimizar dadas las condiciones especiales.

Primero, los ceros no nos interesan. No añaden nada a la suma. Por lo que primero preparamos el conjunto de números que necesitamos multiplicar, y los dividimos por 2 y 5 hasta que no sean exactos.

Con los 2 y 5 que quedaban “flotando”, eliminaba el menor de ellos y añadía al conjunto de los números la diferencia (en cantidad) del otro, ya que esa parte si que era relevante para el resultado.

Entonces, únicamente había que multiplicar todos estos números entre sí y sumar todos los dígitos.

La parte interesante de este problema, primero, era encontrar una manera de pasar todas las imágenes a binario rápidamente, y el otro, realizar el calculo del factorial óptimamente para este caso.

5 Respuestas a “Challenge 17 – Silence on the wire: Identificando luces con CRC32

  1. Pingback:Tuenti Challenge 3 finalizado + Soluciones | Vida de un Programador

  2. Oleg (@colega) 09/05/2013 en 10:43

    Muy buen artículo🙂
    Aquí tienes la solución que había propuesto yo para este problema sin usar ninguna librería externa a Python: https://github.com/colega/tuentichallenge2013/tree/master/17-silenceonthewire

    • shoghicp 09/05/2013 en 11:54

      Muchas gracias por compartirlo!

      Añadí la solución en “Otros enlaces”, en el post con la lista de soluciones.

      Implementaste un lector del formato AVI sin compresión, cierto?
      Aunque la parte del factorial podía optimizarse, eliminando ceros😉

  3. Oleg (@colega) 09/05/2013 en 12:25

    Realmente creo que costaría casi más eliminar los ceros que sumarlos.

    • shoghicp 09/05/2013 en 12:31

      Bueno, se eliminan antes de multiplicarlos, por lo que luego se tarda menos. En el caso de 100000!, de multiplicar todos esos numeros, solo tuvo que multiplicar 26667 en total. La limpieza se realizo en 0.2 segundos😉

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: