Tuenti Challenge 6 (sexta parte)

Viene de aquí.

Challenge 18 – Decipher the message

Faltaba el problema de criptografía. En este problema te dan un mensaje cifrado y tienes que descifrarlo. Fácil. No solo eso, sino que te dan el programa con el que se cifró. Más fácil… ¿o no?

La primera observación es que técnicamente no estamos ante un cifrado, ya que no es algo que tenga una clave y que con ella se puede descifrar. En realidad se parece más a una función de hash, aunque tampoco lo es exactamente, ya que el conjunto de imagen es infinito. Sea como sea, es un programa que te traduce un texto de n caracteres en otro texto con el mismo número de bytes. La correspondencia no es inequívoca: todos los textos de la misma longitud formados por la misma letra tienen como imagen la cadena compuesta por ceros. Por tanto no podemos estar seguros de que haya un único texto que se cifre de la misma forma. Habrá que suponer que la solución sí, o bien que es la única posibilidad en la que el resultado es un texto normal y corriente formado mayoritariamente por letras. Ahora veremos.

En primer lugar analizaremos el algoritmo de cifrado. El funcionamiento es sencillo, empezando por el principio, aplicamos la operación XOR de todos los caracteres a otros caracteres que también estén en el texto. ¿A cuales? Pues tenemos un puntero que empieza apuntando al medio. A continuación, dependiendo del módulo 3 del carácter que codificamos, o bien avanzamos a la derecha, o bien a la izquierda, o bien volvemos al carácter del medio. Esto es particularmente inseguro, ya que de media al menos un tercio de las letras se codifican haciendo XOR con el mismo carácter. A ver cómo podemos explotarlo. El texto codificado en cuestión viene dado por la siguiente secuencia de bytes:

3f171c1d10181112591003591e1d1614591f1f064f1a020d000d1650545d5416025414131a421c5917160459435b73

Supongo que la solución esperada consiste en hacer un programa que haga un backtracking aprovechando ciertas propiedades del algoritmo o del texto para recortar. Pero a mí me gusta atacar estos problemas como si fuera un crucigrama o un sudoku: a mano, haciendo suposiciones, comprobándolas y llegando a conclusiones, hasta que tenga tantas que o bien pueda descifrar el texto o bien pueda hacer un backtracking más podado. A ver qué propiedades podemos sacar del texto y del algoritmo.

Parece que todos los caracteres del texto son ASCII. En efecto, el resultado de hacer XOR entre cualquier par de símbolos siempre es menor que 0x80, y si hubiera caracteres no ASCII, es decir, que empezaran por 1, se tendría que dar la tremenda casualidad de que se hicieran XOR entre ellos y con nadie más, cosa que parece muy improbable.

Una vez que suponemos que todos son caracteres ASCII, es decir, entre 0x00 y 0x7F, parece que podemos dividirlos en cuatro grupos, según su inicio. El primer bit en binario siempre es 0, pero los dos siguientes pueden ser 00, 01, 10 y 11, y representan respectivamente caracteres de control, caracteres especiales, letras mayúsculas y letras minúsculas. También hay algún carácter especial que empieza por 010 y 011, así que habrá que tener cuidado. Esto también clasifica los XOR posibles: si un byte empieza por 0 o 1 es que es el XOR de dos caracteres del mismo tipo (por ejemplo, dos minúsculas). Si empieza por 2 o 3 puede ser una minúscula con una mayúscula, o un carácter de control con uno especial, lo cual es bastante improbable. El primer byte codificado empieza por 3, y luego hay varios que empiezan por 1. Eso es indicativo de que la primera letra es mayúscula, las siguientes minúsculas, y hacemos el XOR con letras minúsculas. Si empieza por 4 o 5 puede ser una mayúscula con un carácter de control, improbable, o una minúscula con uno especial, más probable. Si empieza por 6 o 7 puede ser un carácter de control con una minúscula, o un carácter especial con una mayúscula. Ambas opciones son improbables, pero sólo existe un byte que empieza por 7: el último. Tal vez sea un carácter de final de string, o de final de línea… Ahora lo veremos.

Analizando el texto vemos que casi todos los bytes empiezan por 0 o 1. Hay algunos que empiezan por 4 o 5, y el primero empieza por 3 y el último por 7. Supondremos que la mayoría de caracteres cerca del centro (que son los más comunes a la hora de hacer XOR) son en su mayoría minúsculas, que el primer carácter es una mayúscula, y el último uno de control. El resto serán minúsculas y caracteres especiales.

Además el carácter del centro debe ser una minúscula. ¿Por qué? Hemos supuesto que el primero es una mayúscula, y empieza por 3. Para que una mayúscula pase a empezar por 3 tenemos que hacer XOR con una minúscula. Desde luego parece la opción más probable. A continuación, ¿cuál es el carácter especial más común? Probablemente el espacio. Como además el carácter con el que haremos XOR será el central durante, por lo menos, un tercio de las veces, parece que el byte más común que empiece por 4 o 5 será el XOR de un espacio y el carácter central. Dicho byte es 59, que aparece en 5 ocasiones. Si suponemos que 59 es el XOR de un espacio (código 0x20) y el carácter central, entonces dicho carácter tiene que ser el 0x79, es decir la letra ‘y’ minúscula.

Si esto es así ya podemos sacar más información. La letra inicial tiene que ser una F, que cuadra. Aunque como el código de F módulo 3 es 1 significa que a continuación moveremos el puntero a la derecha y no sabremos cuál es la segunda letra. Sin embargo, el código ASCII del espacio es 32, que equivale a 2 módulo 3. Eso quiere decir que después de un espacio siempre hacemos XOR con la letra central, con la ‘y’. Esto nos dice directamente cuáles deben ser los cinco caracteres que hay después de los cinco espacios que hemos detectado: ‘i’, ‘g’, ‘f’, ‘n’, ‘:’. Todos son bastante probables. Los dos puntos llaman la atención. Están al final, y el siguiente carácter también es especial. ¿Será un emoticono? Pero puede ser feliz porque lo hayamos resulto o triste porque hayamos roto su cifrado. Tendremos que esperar.

Volvamos al centro. Parece que en algún momento el puntero se cruzará con el carácter que estamos considerando y tendremos una XOR de 00. La lógica diría que esto se produciría en el carácter central, que es el más común, pero parece que no, que se produce justo en el de la derecha. Hay dos opciones: o estábamos en el carácter central y lo hemos movido a la derecha, o estábamos en el de dos a la derecha y lo hemos movido a la izquierda. La primera opción es imposible, ya que de producirse implicaría que el carácter central también tendría XOR 0. Por tanto estábamos en el carácter de dos a la derecha y lo hemos movido a la izquierda. Eso quiere decir que el carácter central codificado, 0d, tiene que ser el XOR del carácter central y el carácter de dos a la derecha. Como sabemos que el carácter central es ‘y’, el de dos a la derecha tiene que ser ‘t’. ¡Ya tenemos dos! el centro es algo así como y.t, donde el punto es algo que no conocemos. Pero también sabemos que después de codificar lo que haya en el punto nos hemos movido a la izquierda, porque la codificación de la t es también 0d, por lo que sea cual sea el carácter no puede ser múltiplo de 3. No es mucha información pero bueno.

Volvamos a los espacios. Los primeros 59 están a distancia 3, por lo que si realmente son espacios tiene que haber una palabra de dos letras entre ellos. La primera es ‘i’. Además, i es múltiplo de 3, por lo que después de leerla avanzaremos el puntero a la derecha. Si supiéramos cuál es la otra letra descubriríamos cuál es la letra a la derecha de la ‘y’. No hay tantas palabras de dos letras que empiecen por i. Que se me ocurran, in, is, it. Sea cual sea, su XOR con la letra entre la ‘y’ y la ‘t’ tiene que ser 03. Por tanto, los centros correspondientes a in, is, it serían respectivamente ‘ymt’, ‘ypt’, ‘ywt’. Mirando el diccionario del problema 5, hay 30 palabras que contienen ypt, pero ninguna que contenga ymt o ywt. Por un lado tenemos Apocalyptic, Egypt, Eucalyptus, Krypton… y más de una veintena de palabras derivadas de Crypt: encrypt, cryptography, crpytic… ¿Cuál de estas opciones es más probable en un problema de criptografía? 🙂

Como ya era de madrugada, decidí que la información que tenía era suficiente. Si suponemos que en el centro está la secuencia ‘crypt’, eso nos da para decodificar la mayoría de caracteres, ya que es raro que nos vayamos mucho del centro. Haciendo un programa que hiciera backtracking si le faltaba una letra concreta se obtenía la respuesta en unos instantes.

Challenge 19 – Bricks and Bridges

Este es otro problema algorítmico interesante. Tenemos un grafo no dirigido, donde las aristas tienen peso, y una lista de enteros. Tu objetivo es dar un camino euleriano donde en cada paso eliges un entero de la lista, y al final la suma de los enteros elegidos por cada arista es exactamente su peso. Además tienes que recorrer todos los vértices.

Normalmente un grafo tiene un camino euleriano si es conexo y todos los vértices tienen grado par, excepto posiblemente dos que pueden tener grado impar, y que serían el inicio y el final del camino. En este problema se pide algo más que un camino euleriano, ya que puedes recorrer todas las aristas varias veces, pero al final la suma de la fuerza de los pasos que das tiene que ser exactamente igual que la resistencia de la arista. Sin embargo la condición de conexión parece que es idéntica. Comprobamos al principio que el grafo sea conexo, y si no lo es ya sabemos que no es posible recorrerlo. Si es conexo ya lo será para siempre: para nuestro algoritmo es posible que quitemos aristas, pero sólo necesitamos que sea conexo al principio.

La primera observación es que en realidad sólo hace falta saber si podemos recorrer cada arista un número par y/o impar de veces. Como sólo nos interesa la paridad de los grados de los vértices, da igual que recorramos una arista 4, 6 o 40 veces. Eso reduce los 1.000 tipos de aristas a solo 4: o bien no se puede recorrer (y en ese caso no hay solución al problema), o bien se puede recorrer únicamente un número par de veces, o bien únicamente un número impar, o bien se puede recorrer tanto un número par como un número impar de veces.

Dicha clasificación depende únicamente de la resistencia del puente, por lo que podemos calcular a priori por cada resistencia entre 1 y 1.000 (o hasta la resistencia mayor), si se puede atravesar un número par e impar de veces. Podemos hacerlo mediante programación dinámica. Un supuesto puente de resistencia 0 se puede atravesar únicamente un número par de veces (0). A continuación, para cada resistencia r, si la podemos atravesar un número par de veces, entonces las resistencias r+s las podremos atravesar un número impar de veces, para todos los valores de paso s. Análogamente si la podemos atravesar un número impar de veces.

Ahora que hemos clasificado las aristas vamos a definir un nuevo grafo. El nuevo grafo será también un multigrafo, pero las aristas no tendrán peso. En cambio los vértices pueden ser blancos o negros. El grafo lo definimos así: Inicialmente todos los vértices son blancos. A continuación, por cada arista del grafo antiguo, si no podemos recorrerla un número par ni impar de veces entonces no hace falta que sigamos, ya que el problema no tiene solución. Si podemos recorrerla un número par de veces, pero no un número impar de veces entonces la desechamos. Si podemos recorrerla un número impar de veces pero no un número par entonces la desechamos pero cambiamos el color de los dos vértices que une. Finalmente, si podemos recorrerla tanto un número par como un número impar de veces entonces la añadimos al nuevo grafo.

Aquí viene lo interesante. Existirá un ciclo euleriano en el grafo antiguo si existe un subconjunto de aristas del grafo nuevo tal que todos los vértices negros son adyacentes a un número impar de esas aristas, y todos los vértices blancos son adyacentes a un número par, excepto posiblemente dos que pueden no ser así. Es evidente que podemos construir el ciclo euleriano a través de la información obtenida: si añadimos las aristas del subconjunto un número impar de veces y el resto un número par, y volvemos a añadir las aristas desechadas que sólo se podían recorrer un número par o impar de veces, entonces el grafo resultante es conexo, y todos los vértices tienen grado par, excepto posiblemente los dos que eran o bien blancos adyacentes a un número impar de nuevas aristas, o bien negros adyacentes a un número par de nuevas aristas.

Falta entonces detectar si existe dicho subconjunto. Pues bien, utilizaremos el siguiente teorema: existe un subconjunto que cumpla dichas propiedades si y solo si en toda componente conexa del nuevo grafo hay un número par de vértices negros, o bien si hay exactamente dos componentes conexas con un número impar de vértices negros. El número total de vértices negros es par, por lo que no puede haber una única componente conexa con un número impar de vértices negros.

¿Cómo lo demostramos? Es sencillo. Suponemos que en una componente conexa hay un número par de vértices negros. Consideremos cualquier aparejamiento entre ellos. Ahora consideremos cualquier camino que una cada una de las parejas. Si consideramos la unión de todos los caminos es evidente que los vértices negros serán incidentes a un número impar de aristas, y los blancos a un número par. El problema es que puede que consideremos una arista demasiadas veces. Pero eso no es un problema. Si una arista aparece v veces en los diferentes caminos, si v es par entonces no la consideraremos en el subconjunto final, y si es impar sí que la consideraremos. El conjunto final será entonces un subconjunto de las aristas tal que todos los vértices negros serán incidentes a un número impar de aristas, y los blancos a un número par.

¿Y si hay un número impar de vértices negros? Bueno, entonces podemos ver que es posible encontrar un subconjunto de aristas tales que todos los vértices negros son incidentes a un número impar de aristas, y todos los blancos son incidentes a un número par, excepto uno, es decir, o bien un negro incidente a un número par de aristas o bien un blanco incidente a un número impar. El procedimiento es el mismo: si queremos que haya un vértices blanco incidente a un número par de aristas entonces lo emparejamos con un vértice negro, emparejamos el resto de vértices negros, y hacemos el mismo procedimiento que antes. Si preferimos que un vértice negro sea incidente a un número par de aristas entonces no lo emparejamos, y emparejamos el resto de vértices negros.

Falta dar la respuesta, es decir, los índices mínimos tales que podamos entrar en uno de ellos y salir por el otro. Si todas las componentes conexas del nuevo grafo tienen un número par de vértices negros entonces existe un ciclo euleriano. Eso quiere decir que podemos entrar y salir por el mismo vértice, así que elegiremos el de menor índice. Si en cambio hay dos componentes conexas del nuevo grafo que tienen un número impar de vértices negros entonces no existe un ciclo euleriano, pero sí camino euleriano. Tenemos que elegir por qué vértice entramos y por cuál salimos. Según la propiedad anterior, podemos entrar por cualquier vértice de una de esas dos componentes conexas, sea blanco o negro, y podemos salir por cualquiera de la otra componente conexa. Por tanto buscaremos el vértice de menor índice de cada una de las componentes conexas, y entraremos por el menor y saldremos por el mayor.

En cuanto al coste, por un lado tenemos que precalcular la paridad de las diferentes resistencias. Esto se puede calcular en tiempo SxT, donde S es el número de pasos diferentes, y T la máxima resistencia de las aristas. Por otro lado tenemos que construir el nuevo grafo, detectar las componentes conexas, y detectar el número de vértices negros en cada una de ellas. Todo eso se puede hacer en tiempo lineal con respecto al número B de puentes. Por tanto el coste final será O(S\cdot T + B). Como S \leq 50T \leq 1000 y B\leq25000, mi programa calcula la respuesta correcta en menos de medio segundo.

Challenge 20 – Tuenti star

Para que nadie acabara todos los problemas, este año el último problema era de optimización. Es decir, tienes que dar la mejor solución posible a un problema, pero calcular el óptimo absoluto es probablemente NP-difícil, por lo que no se espera que nadie lo dé. En su lugar, cada solución tiene una puntuación objetiva, y tienes que ir mejorándola para obtener cuantos más puntos mejor. Esto es una garantía de que todos los participantes tendrán algo que hacer hasta el final, ya que siempre es posible mejorar la solución un poquito.

El problema consiste en lo siguiente. Hay una serie de antenas, y una lista de llamadas. Tienes que asignar las llamadas a las diferentes antenas, con una hora de inicio determinada. Tienes la restricción de que cada antena tiene un límite de llamadas que puede atender a la vez, por lo que no es posible asignar una llamada a una antena que alcance ese límite hasta que no finalice alguna llamada y se libere. Una vez finalizada cada llamada, el usuario asigna una puntuación. Esa puntuación depende de la distancia a la antena y de lo que haya tenido que esperar. También se pueden rechazar llamadas, en cuyo caso la puntuación es 0.

De los cuatro participantes que enviamos una solución válida, la mía solo obtuvo la tercera más alta, por lo que tal vez prefieras echar un vistazo a las soluciones de los otros participantes. Yo he venido a hablar de mi libro, así que os contaré la mía.

En primer lugar utilicé un algoritmo greedy para asignar las llamadas a las antenas. El algoritmo era sencillo: en primer lugar ordenaba las llamadas por tiempo de inicio, y a continuación las iba asignado a las antenas. Si una antena estaba ocupada no había problema: asignaba la llamada al momento en el que la antena quedaría libre. Para elegir la antena el criterio también era simple: calculaba el número de estrellas que me daría cada una, según la distancia y el tiempo que le haría esperar, y me quedaba con la mayor.

Esta solución daba una puntuación relativamente baja, alrededor de 25.000. Como hay 10.000 llamadas quiere decir que cada uno daba dos estrellas y media de media. Seguro que se puede mejorar. Algunas mejoras que hice fueron, en primer lugar, no aceptar una llamada si daría menos de N estrellas, para diferentes valores de N (por ejemplo 1). Después también decidí no aceptar llamadas largas, pero luego decidí aceptar las que daban muchas estrellas. Finalmente encontré el compromiso ideal en aceptar las llamadas tales que su duración fuera menor que una cierta constante M por el cubo del número de estrellas que obtendrían. Para N=1 y M=10 conseguí mejorar la puntuación hasta cerca de 30.000. Ya era un avance.

Aquí fue donde se me ocurrió sacar a relucir los algoritmos aprendidos en la clase de Inteligencia Artificial, hace años. Podría empezar por un Hill Climbing. Pero no parece que haya una forma de modificar “ligeramente” la solución para obtener otra. Así que decidí crear un vector de booleanos que indicarían las llamadas a considerar. Es decir, tomamos el subconjunto de llamadas tales que en el vector están a cierto, y aplicamos el algoritmo greedy de antes. Para modificar una solución cambio una posición del vector de válidos, y lo ejecuto hasta que no se pueda mejorar. Este algoritmo empezaba a dar buenos resultados, y llegué a superar los 31.000 puntos. ¿Qué más se podía hacer?

Como era evidente que se podía hacer mejor, probé con otro de los algoritmos que recuerdo: el algoritmo genético. Nuevamente las soluciones están basadas en un vector de booleanos que se comporta igual, y la única diferencia con el Hill Climbing es la forma de obtener nuevas soluciones, es decir, nuevos vectores de booleanos. Ahora me guardo una población, de por ejemplo 30 vectores, y los voy apareando entre ellos. Por ejemplo, si una posición es cierta en los dos progenitores, será cierta en el hijo. Si es falsa será falsa, y si hay discrepancia tiro una moneda. Además añado mutaciones aleatorias para que la solución no se estanque tan rápido. Y finalmente me quedo a cada paso con los 30 mejores entre los progenitores y los descendientes. Este algoritmo va más rápido que el Hill Climbing y en seguida supera sus soluciones. En un momento me planté en 32.000, y tras dejarlo un buen rato llegué a 33.000. Pero se empezaba a estancar ahí.

Por probar, me dio por hacer la versión diploide de los algoritmos genéticos. Aquí una solución no es un vector, sino dos, que representan dos alelos. Decidí que la característica de ser válido sería dominante, por lo que bastaba con que fuera cierto en uno de los dos para que lo consideráramos. A la hora de calcular el descendiente tiraba una moneda para ver si el primer alelo de cada posición lo recibía de un progenitor o de otro, y el segundo lo recibiría del contrario. Ejecuté el algoritmo, pero los resultados eran bastante similares a los del algoritmo genético normal. Como no eran peores dejé ejecutándose la última versión. Tras un día de ejecución llegué a la solución que envié: 33.302. Sin embargo, después lo dejé un par de días ejecutándose y cada pocas horas iba apareciendo una mutación beneficiosa que permitía mejorar la solución. Cuando lo corté estaba alrededor de los 33.333, pero ya casi no avanzaba.

Seguramente el techo de mi algoritmo estaba en el greedy. El espacio de soluciones no es completo, ya que yo sólo considero por cada llamada si entra o no, pero no permito cambiar el orden relativo de las llamadas, y es posible que una llamada que obtenga una mejor puntuación, o que dura menos, deba empezar antes que otra, sin necesidad de descartar la otra, que puede entrar más tarde. Como prueba desesperada intenté ordenar por final en lugar de por inicio, pasando antes una llamada si teóricamente acabaría antes. Pero los resultados eran peores, así que abandoné la búsqueda. 33.302 ya está bastante bien.