Tuenti Challenge 6 (segunda parte)

Viene de aquí.

Challenge 5 – Hangman

En este reto se proporciona una dirección IP y un diccionario. Pese a que no hay descripción de lo que hay que hacer, parece evidente que hay que ganar al juego del ahorcado. Sin embargo, al acceder a la dirección IP desde el navegador no se obtiene el resultado esperado: la página se queda cargando durante cerca de un minuto, y a continuación da un mensaje diciendo que se ha acabado el tiempo y no se ha acertado la palabra. Tal vez haya que seguir otros métodos.

Si se accede a la página desde telnet (por ejemplo, desde la línea de comandos de Linux, telnet 52.49.91.111 9988), entonces sí que se puede jugar interactivamente. Podemos ver que hay que acertar una palabra de cuatro letras, y que al cometer seis errores el ahorcado se completa y perdemos. Así que parece que la solución consiste en hacer un programa que juegue al ahorcado, y que se comunique con la IP, ya sea mediante telnet o abriendo un socket TCP. La mayoría de lenguajes de programación tienen módulos que implementan dichos protocolos. Yo usé el módulo telnet de Python.

Para jugar al ahorcado mi solución consiste en mantener una lista de palabras posibles, y en cada momento responder con la letra que aparece en más palabras posibles y que no se haya dicho ya. Las palabras posibles son las que tienen el número de letras que toca, que no contienen ninguna letra incorrecta, y que tienen las letras correctas en las posiciones que tocan. Parece que esta estrategia es óptima: si una letra aparece en la palabra entonces tarde o temprano tenemos que decirla, y además no perdemos turno. Si en cambio no aparece hemos descartado el mayor número posible de palabras. De hecho esta estrategia resuelve el juego si no a la primera en muy pocas partidas.

Para conseguir la clave del caso Test es necesario completar el primer nivel, consistente en palabras de cuatro letras. Para el caso Submit es necesario completar todos los niveles, pero si no se consigue resolver una palabra hay que volver a empezar.

Challenge 6 – Through the Looking-Glass

Empiezan los problemas sin enunciado claro. Aquí la solución es sencilla una vez que descubres lo que tienes que hacer. Pero descubrirlo no es fácil, así que voy a tratar de explicar cómo llegué a la solución. Si no te interesa puedes acceder a la solución directamente desde aquí.

En principio toda la información que te dan es un código QR, aunque extrañamente coloreado. Sin embargo un lector QR típico es capaz de leerlo, y contiene un enlace a la página de la wikipedia de Piet Mondrian. Cualquiera que esté familiarizado con lenguajes esotéricos habrá deducido inmediatamente a qué se refiere la pista. Pero como no era mi caso no tuve más remedio que seguir investigando.

La página de la wikipedia dice que Piet Mondrian fue uno de los mayores exponentes del movimiento artístico De Stijl, también llamado neoplasticismo, y que consiste en pinturas bidimensionales con colores básicos. Esto nos lleva a pensar que el código QR coloreado debe tener información sobre cómo resolver el problema. Vamos a tratar de analizarlo.

La imagen es un PNG de 175×175 píxeles, en formato colormap de 8 bits con una paleta de colores. Analizándolo podemos ver que hay alrededor de 20 colores en la paleta, y la mayoría bastante básicos: blanco, negro y diferentes intensidades de verde, rojo, azul… El código QR utiliza los más claros para representar los píxeles blancos, y los más oscuros para los negros. Los intermedios aparentemente no se utilizan para representar el código, ya que supongo que confundirían al lector óptico.

A ver qué anomalías encontramos. El código QR tiene 29 filas y 29 columnas. Sin embargo 175 no es múltiplo de 29. Pero 174 sí que lo es: tenemos 29 filas y columnas de 6 píxeles cada una, y sobra una fila y una columna. Tiene que haber una fila y columna con 7 píxeles, o tal vez algo más… Veamos… En efecto, la columna de la derecha tiene 7 píxeles, pero no parece diferente a los otros 6, simplemente la columnas es más ancha. A ver la primera fila de píxeles… ¡La primera fila de píxeles no tiene ninguna relación con la primera fila del código QR! Ahí tiene que esconderse algo, analicémoslo.

Observando los colores, vemos que los primeros píxeles están coloreados con los primeros colores de la paleta, hasta que llega un punto en el que se repiten. Sin embargo los colores de la paleta no parecen seguir ningún orden lógico. Seguramente eso quiere decir que en primer lugar se coloreó la imagen, y en segundo lugar se definió la paleta de forma que el color i-ésimo era el color i-ésimo en aparecer en la imagen. Seguramente los colores del código QR estén elegidos al azar, con la restricción de que los claros vayan a las áreas blancas y los oscuros a las negras. Una información importante que se puede sacar de aquí es que los colores importan, en el sentido de que no son intercambiables. Pero tras mucho pensar no parece haber ninguna relación lógica…

Volvamos a la wikipedia, a ver si el artículo sobre Piet Mondrian aporta alguna información. Tal vez la forma en la que usaba los colores da alguna pista. Su biografía no parece decir nada… a ver… referencias culturales… ¡Bingo! ¡Existe un lenguaje de programación llamado Piet! ¡Y está basado en imágenes! Y todo cuadra: hay 20 colores, como en la paleta del QR, y los colores son los mismos: blanco, negro, y versiones clara, oscura e intermedia de los colores básicos. La imagen tiene que ser un programa en Piet que escriba la solución. Vamos a intentar ejecutarlo.

Sin embargo algo no cuadra. Algunos intérpretes de Piet no funcionan correctamente con la imagen, y otros dan resultados ligeramente distintos. La mayoría piden un input que desconocemos, y luego entran en bucle. Alguno de ellos escribe un texto legible, que empieza por “Why it’s…” y luego se corta. Tiene que haber algo, pero también tiene que haber algo que no se hace correctamente… Un intérprete me da una pista: “Excepción: el primer píxel no puede ser negro”. ¡Pero es negro! ¿Significa que el código está equivocado? Por lo visto los píxeles negros se usan para finalizar el programa, por lo que empezar en un píxel negro es un comportamiento no esperado que cada intérprete resuelve a su forma. Falta algo, algún detalle se nos escapa…

Tras probar muchas cosas volvemos al enunciado del problema. Es muy escueto: “Alice was looking Through the Looking-Glass and The Door showed her this:”. Normalmente los enunciados suelen incluir una historia que guarda algún tipo de relación con el problema, pero una vez entendido el problema nos podemos abstraer. Sin embargo este enunciado no tiene absolutamente ningún tipo de relación con el problema que estamos resolviendo. ¿Se trata simplemente de que el problemsetter nos quiere decir cuánto le gusta Alicia en el País de las Maravillas? ¿O estamos ante una pista? Probablemente ambas respuestas sean correctas.

Buscamos en Google Through the Looking-Glass, y vemos que es la primera parte del título del libro Through the Looking-Glass, and What Alice Found There, segunda parte de Las aventuras de Alicia en el País de las Maravillas. Mirando la sinopsis se puede ver que cuando alicia atraviesa el Looking-Glass ve el mundo reflejado, como en un espejo. Según el enunciado Alicia ve el código QR a través del Looking-Glass, por lo que el verdadero código tiene que ser un reflejo del que nos dan. Efectivamente, al reflejarlo horizontalmente obtenemos un código Piet auténtico, que al ejecutarse en cualquier intérprete nos da la respuesta correcta: la frase del libro de Alicia en el País de las Maravillas “Why it’s simply impassible!”.

tl;dr, ¿La solución, por favor?

Ahora mismo. Para resolver el problema tienes que descargar el código QR proporcionado, reflejarlo horizontalmente (por ejemplo en Linux mediante la suite ImageMagick), y ejecutarlo con un intérprete del lenguaje de programación Piet (como el que puedes encontrar aquí).

Challenge 7 – Tiles

Volvemos a los problemas algorítmicos. En este caso tienes que encontrar el subrectángulo de suma máxima de una matriz que contiene números enteros entre -26 y 26. Esto sería fácil si no fuera por una pequeña particularidad: ¡la matriz es infinita! En particular te dan una patrón de tamaño hasta 1000×1000, y la matriz a considerar es la concatenación infinita horizontal y vertical de dicho patrón. Eso quiere decir que la solución puede ser también infinita, es decir, no acotada. Por ejemplo si todos los elementos del patrón son positivos. Por tanto el problema se puede dividir en dos partes: ver si la solución es infinita, y si no lo es, calcularla.

Para ver si la solución es infinita se puede usar el siguiente teorema: la solución es infinita si y sólo si existe una fila o una columna con suma estrictamente positiva. La demostración es la siguiente. Por un lado es evidente que si existe una fila o una columna con suma positiva entonces la solución es infinita: basta con concatenar dicha fila o columna tantas veces como queramos. Por otro lado, si la suma de todas las filas y columnas es un número negativo o 0, entonces la solución no puede ser infinita. Para verlo demostraremos que si el patrón es NxM siempre existe una solución óptima de tamaño menor que NxM. Supongamos que hay una matriz de tamaño mayor, por ejemplo, una matriz que tiene más de N filas. Si consideramos las N primeras obtenemos una secuencia de columnas completas. Pero todas las columas tienen suma menor o igual que 0, por tanto la secuencia también debe sumar un número no positivo. Eso significa que si eliminamos las N primeras filas obtendremos una rectángulo con suma mayor o igual. Si repetimos ese procedimiento por filas o columnas mientras podamos finalmente obtendremos una matriz de tamaño menor que NxM con suma mayor o igual que la inicial. Es decir, nunca podemos conseguir una suma mayor que la de un rectángulo de tamaño menor que NxM. Como el número de rectángulos de ese tamaño es finito, la suma máxima global tiene que estar acotada.

Ya solo falta calcular la solución si es finita. Como siempre hay una solución de tamaño menor que NxM basta con buscar el subrectángulo de suma máxima de la matriz formada por 2×2 patrones. Dicha matriz contiene necesariamente todos los rectángulos de tamaño menor que NxM, por lo que es correcto buscar únicamente ahí. El problema de encontrar el subrectángulo de suma máxima en una matriz es conocido, y hay un algoritmo que lo resuelve en tiempo O(N^2M). Dicho algoritmo consiste en conjeturar la fila en la que empieza y acaba nuestro subrectángulo, calcular la suma de cada subcolumna entre ambas filas, y reducir así el problema a una dimensión. Recordemos que el problema unidimensional tiene solución lineal conocida mediante el algoritmo de Kadane, por lo que si calculamos las subcolumnas inteligentemente a partir de lo que ya hemos calculado obtendremos un algoritmo cúbico. Existen algoritmos teóricos subcúbicos, como este que tiene tiempo de ejecución O(N^3(\log\log N / \log N)^{1/2}), pero la diferencia es tan imperceptible que a no ser que la matriz sea montruosamente grande perderemos más tiempo en los detalles de la implementación de lo que ahorraremos en coste asintótico.

Como el patrón puede tener tamaño 1000×1000, el algoritmo en caso peor puede tardar bastante. Se pueden hacer algunas pequeñas mejoras a bajo nivel, pero aun así mi solución en C++ compilada con O3 tarda 17 segundos en resolver el caso de submit. Algunas mejoras consisten en no calcular la matriz consistente en 2×2 patrones explícitamente, ya que se puede deducir del patrón haciendo módulo. Además no es necesario que consideremos todos los subrectángulos de la matriz 2×2, sino sólo aquellos que tienen tamaño menor que NxM. Por otro lado, si el número de filas es mayor que el número de columnas podemos transponer el patrón, ya que el coste es de O(N^2M). Sin embargo estas optimizaciones parecen no ser suficientes en este problema, y las soluciones que he visto tardan un tiempo parecido, que dudo que se pueda mejorar mucho en caso peor.

Sigue aquí.