Tuenti Challenge 6 (tercera parte)

Viene de aquí.

Challenge 8 – Labyrinth

Nuevamente un problema sin enunciado, pero con un título que da una pista de por dónde van los tiros. De nuevo se nos proporciona una IP, a la que no podemos acceder desde el navegador, pero sí por telnet. Lo que vemos es más o menos lo que esperábamos: una sección de un laberinto, del que presuntamente habría que salir. Lo primero que tenemos que hacer es intentar descubrir los comandos para moverse. Pruebo unos cuantos al azar y no obtengo respuesta, así que volveremos a hacer un programa en Python que use el módulo de telnet para enviar soluciones. Pruebo con todas las letras minúsculas del abecedario y parece que hay movimiento. Revisando se puede ver que las teclas de movimiento son u, d, l, r, es decir, Up, Down, Left, Right. Sin embargo volviéndolo a probar desde la consola esos comandos no permiten el movimiento. El servicio debe detectar cuando se accede por consola y en ese caso rechaza los comandos, o bien hay algún detalle técnico que se me escapa. Pero da igual, probablemente la solución esperada no sea hacerse el laberinto a mano, así que ya va bien que con un programa en Python funcione.

En los problemas de laberintos, una forma de salir consiste, conceptualmente, en avanzar con la mano derecha (o izquierda) siempre pegada a la pared. Traducido a código, eso significa guardar en todo momento la dirección a la que nos dirigimos, y a la hora de avanzar intentar ir a la derecha. Si no es posible al frente, si tampoco es posible a la izquierda, y si tampoco es posible es que hemos llegado a un callejón sin salida y tenemos que volver atrás. Esta estrategia funciona si no hay casos patológicos, como por ejemplo un ciclo. Parece que no es el caso y que siguiendo esa secuencia de movimientos conseguimos recorrernos el laberinto poco a poco.

Sin embargo, tras un buen rato de ejecución, parece que no conseguimos salir nunca. Para saber qué pasa lo mejor es guardar la posición en la que estamos en cada momento, e ir reconstruyendo el laberinto, para finalmente imprimirlo. Después de unos minutos el mapa se completa, y vemos lo que aparece en esta imagen (recortada por motivos de espacio):

laberinto

¡Hay un código en el exterior! De hecho el laberinto no tiene salida, por lo que la respuesta al problema consiste en escribir dicho código, empezando en e0 y acabando en 59. La estrategia de la mano en la pared completa el mapa en pocos minutos, bastantes menos de 13, y permite obtener todo el código para pasar al siguiente nivel.

Challenge 9 – 0-1 Immiscible numbers

En este problema te dan un número, y tienes que calcular el menor múltiplo de ese número de la forma 11…1100..00. El problema tiene dos partes diferenciadas: encontrar el número de ceros, y encontrar el número de unos.

Encontrar el número de ceros es sencillo. Denotamos como u(k) el número compuesto por k unos, es decir, u(k)=(10^k-1)/9. Entonces el número formado por k unos seguidos de m ceros será u(k)\cdot 10^m. Como u(k) no es múltiplo de 2 ni de 5, entonces todos los factores de 2 y de 5 tendrán que estar en 10^m. Por tanto, si el número de la entrada es n = q 2^a5^b donde q no es múltiplo ni de 2 ni de 5, entonces el número de ceros será necesariamente \max(a,b). Con menos no es posible, ya que u(k) no tiene factores 2 ni 5. Y más no son necesarios, ya que 10^m ya es múltiplo de 2^m y de 5^m. Además podemos eliminar todos los factores 2 y 5 del número de la entrada a la hora de calcular el número de unos.

Por tanto el problema se reduce a lo siguiente: dado un número n que no es múltiplo de 2 ni de 5, calcular el mínimo k tal que u(k) es múltiplo de n. Para calcularlo, la solución trivial consiste en probar con todos los números formados por unos hasta que uno de ellos sea múltiplo de n. Como el número de unos necesario puede ser grande, es posible que haya que trabajar con números enormes, por lo que esa solución tardará mucho. La optimización que hice, y que he visto en varias soluciones, consiste en trabajar con aritmética modular. Lo que queremos es buscar un k tal que u(k) sea múltiplo de n. En otras palabras, buscamos un k tal que u(k)\equiv 0 (\mod n). Dado u(k) (\mod n) se puede calcular u(k+1) (\mod n) simplemente multiplicando por 10 y sumando 1. Al trabajar módulo n nos ahorramos tener que utilizar enteros de miles de millones de cifras, lo que acelera el código. ¿Cuánto?

Se puede demostrar que para todo n que no sea múltiplo de 2 ni de 5 existe un k\leq n tal que u(k)\equiv 0 (\mod n). La demostración es la siguiente. Consideramos la función f:Z_{n}\rightarrow Z_{n} tal que f(x)=10\cdot x + 1. Dicha función tiene inversa, ya que 10 es coprimo con n y por tanto tiene inversa módulo n. Por tanto tenemos una aplicación biyectiva de un conjunto finito en sí mismo, es decir, una permutación finita. Como es bien sabido, las permutaciones finitas se descomponen en ciclos, por lo que el elemento 0 pertenecerá a un ciclo, que lógicamente tiene que tener tamaño menor o igual al tamaño del conjunto, es decir, n.

Esto demuestra que el algoritmo que utilizamos da la respuesta al número n en tiempo O(n), es decir, en tiempo exponencial respecto al tamaño de la entrada (al número de cifras de n). Sin embargo, n puede ser menor o igual a 2^{31} (como muy amablemente se encargó de recordarme el corrector al rechazarme un programa que funcionaba para enteros menores estrictos2^{31}). Eso quiere decir que en caso peor el algoritmo podría tardar demasiado, y de hecho nuestras soluciones que utilizan aritmética modular tardan del orden de medio minuto aun compilando con la opción O3.

Una vez finalizado el concurso, y sin la presión de la cuenta atrás, de todos los problemas que quedan por resolver y del poco tiempo que queda, me ha dado por volver a pensar el problema a ver si existía una solución mejor. Y aparentemente existe. El truco está en multiplicar por 9. En lugar de calcular el menor número compuesto por unos múltiplo de n, lo que calcularemos será el menor número compuesto por nueves múltiplo de 9n, que evidentemente tendrá el mismo tamaño. ¿Y eso para qué sirve? Bueno, el caso es que el número 99…99 es más fácil de expresar que 11…11, ya que es simplemente 10^k-1. Por lo tanto, cuando aplicamos aritmética modular, en lugar de buscar un k tal que u(k)\equiv 0 (\mod n) buscaremos un k tal que 10^k-1\equiv 0 (\mod 9n), o lo que es lo mismo, 10^k\equiv 1 (\mod 9n).

Dicho número se conoce en teoría de números como el orden de 10 en Z_{9n}. Y por lo visto hay algoritmos eficientes para calcular el orden si conocemos la factorización de n. La factorización es un problema difícil, pero hay algoritmos triviales que tardan del orden de O(\sqrt{n}) en descomponer un número en factores primos. Y en nuestro caso eso es más que suficiente, ya que la raíz cuadrada de 2^{31} es de poco menos de 50.000. Yo he utilizado el algoritmo que he encontrado en esta página. Lo he implementado en Python y me ejecuta el caso de submit en menos de medio segundo, y la solución coincide con la oficial. He subido el código a mi repositorio, con el nombre de 9alternative.py, por si alguien quiere echarle un vistazo.

Challenge 10 – Container madness

En este problema nos dan un archivo contenido en un .zip, y nos piden encontrar un cierto número de claves. Como se da a entender tan gráficamente con las matrioskas, el secreto consiste en ir extrayendo los archivos contenidos los unos en los otros, ya sea como archivos comprimidos, como adjuntos, ¡o incluso como subtítulos! Los diferentes archivos tienen escondidas unas claves también en lugares diversos, como el título, los metadatos, u otros archivos adjuntos. He aquí una guía para encontrar todas las claves:

  1. El primer archivo es el container.zip que se descarga de la página del enunciado. La primera clave está en un comentario al que se puede acceder de diversas formas. Por ejemplo con un editor hexadecimal, o abriéndolo con un editor de texto, o mediante el módulo zipfile de Python, y la instrucción getinfo(‘container.zip’).comment.
  2. El segundo archivo es un doc llamado tuenti.docx que se obtiene al descomprimir el container.zip. La segunda clave se obtiene a partir de la información .xml asociada al documento. Una forma de acceder a ella es descomprimiendo el archivo .docx como si de un .zip se tratara, y en una de las carpetas que aparecen hay un archivo llamado core.xml que contiene la solución.
  3. El tercer archivo es un mp3 llamado tuenti.mp3 que se obtiene al descomprimir el tuenti.docx. La tercera clave está contenida en los metadatos del mp3, en particular en el campo Lyrics. Se puede acceder a ellos de diversas formas, de nuevo con editores hexadecimales o de texto, o bien mediante el módulo eyed3 de Python.
  4. El cuarto archivo es un png llamado tuenti.png que está guardado como la carátula del tuenti.mp3. Hay muchos programas que permiten extraer la carátula de un archivo de sonido. Yo he usado el módulo mutagen de Python. La cuarta clave está guardada en el título del PNG, al cual se puede acceder mediante las propiedades del archivo. Yo he usado el módulo PIL de Python.
  5. El quinto archivo es un pdf llamado tuenti.pdf guardado como base64 en los metadatos del png, en un campo llamado NextLevel. La quinta clave es el asunto del pdf, al que se puede acceder mediante las propiedades del archivo, o mediante el módulo pdfminer de Python.
  6. El sexto archivo es un vídeo que aparece como archivo adjunto del pdf llamado tuenti.mkv, curiosa y adecuadamente en formato Matroska. Se puede extraer mediante varias aplicaciones, como por ejemplo pdfdetach. Para ver la sexta clave hay que abrir el vídeo y copiar los subtítulos a mano.
  7. El séptimo archivo es un archivo adjunto del vídeo .mkv llamado tuenti.txt, que se puede extraer mediante varios programas, como por ejemplo mkvextract. La séptima clave viene al inicio del archivo de texto.
  8. El octavo archivo viene codificado con UUencode en el archivo tuenti.txt. Se trata de un archivo comprimido llamado ramdisk.cpio.gz. Para obtener la octava clave hay que descomprimir el archivo, y uno de los ficheros resultantes tiene como título dicha clave.
  9. El noveno archivo es el otro de los ficheros comprimidos en ramdisk.cpio.gz. Se trata de un gpg llamado LastLevel.txt.gpg que necesita una contraseña para descifrarse. La contraseña se puede encontrar dentro del archivo cuyo título es la octava clave. La novena clave se obtiene al descifrar el archivo.

Sigue aquí.