Tuenti Challenge 6 (cuarta parte)

Viene de aquí.

Challenge 11 – Toast

En este problema empezamos con N pilas con M tostadas cada una, y tenemos dos operaciones: duplicar el número de tostadas de una pila, o replicar una pila. Tenemos que calcular el mínimo número de operaciones para acabar con K tostadas.

La primera observación es que cada operación aumenta el número de tostadas en un múltiplo de M. Esto implica necesariamente que K tiene que ser múltiplo de M, y si no es imposible. Si es así podemos dividir K entre M y el problema se reduce a calcular el mínimo número de operaciones necesarias para obtener L=K/M partiendo de pilas de una sola tostada.

Supongamos entonces que todas nuestras pilas tienen una tostada y tenemos que sumar L. Es evidente que si hay más de L pilas no habrá solución. También es evidente que si hay un número menor o igual a L de pilas siempre habrá solución: por ejemplo, replicando una pila hasta tener L. Así que supondremos a partir de ahora que el número de pilas es menor o igual a L. Pero hay que obtener la solución que necesite el menor número posible de movimientos. Segunda observación: siempre hay una solución óptima en la que todas las operaciones se realizan en una pila. Es decir, que al final habrá N-1 pilas con una tostada a las que no habremos aplicado ninguna de las dos operaciones.

La demostración de la segunda observación es un poco enrevesada. Vamos a ver que sea cual sea la secuencia de operaciones, siempre podemos encontrar otra secuencia de operaciones que dé el mismo número final de tostadas y que sólo se apliquen a una pila. En primer lugar es evidente que toda operación aumentará el número de tostadas en una potencia de 2. Además, si existe una operación que aumenta el número de tostadas en 2^n para n\geq 1 entonces tiene que haber una operación anterior en la que se haya aumentado el número de tostadas en 2^{n-1}. Esto es así porque para que una operación aumente el número de tostadas en 2^n la tenemos que aplicar sobre una pila de tamaño 2^n, y dicha pila sólo la hemos podido obtener duplicando el número de tostadas de una pila de tamaño 2^{n-1}, lo que es una operación que aumenta el número de tostadas en 2^{n-1}. Por lo tanto cualquier secuencia de operaciones contiene al menos una operación en la que se ha aumentado el número de tostadas en 2^n, para todos los n entre 0 y un cierto valor dado, y ninguna para los n mayores que ese valor. Es evidente entonces que podemos obtener una secuencia equivalente, con operaciones que aumenten el mismo número de tostadas, aunque en otro orden, si partimos de una sola tostada: en primer lugar la replicamos tantas veces como operaciones haya habido que creen una tostada nueva. En segundo lugar duplicamos la pila, y a continuación repetimos el proceso hasta que generemos todos los movimientos. Al final obtendremos obviamente el mismo número de tostadas.

Por tanto el problema se puede reducir a lo siguiente: dada una pila con una tostada, obtener L-N+1 tostadas mediante dos operaciones: duplicar el número de tostadas de una pila, o replicar una pila. Se puede ver fácilmente que el siguiente algoritmo es óptimo: obtenemos la representación binaria de L-N+1, y empezando desde el bit menos representativo, por cada 0 duplicamos la pila, y por cada 1 la replicamos y luego la duplicamos, hasta que tengamos el número de tostadas necesario. Es decir, la solución final es la longitud en binario de L-N+1, más el número de unos, menos uno.

Challenge 12 – Pika Virus

En este problema se pide calcular si dos árboles enraizados son equivalentes, según una cierta definición de equivalencia. Decimos que dos árboles enraizados son equivalentes si existe una correspondencia biyectiva entre ellos tal que a cada nodo de un árbol le corresponde un nodo equivalente del segundo árbol. Dos nodos son equivalentes si están en el mismo nivel y los subárboles generados correspondientes son isomorfos, es decir, si existe un isomorfismo de grafos entre ellos que haga corresponder las respectivas raíces, o equivalentemente si existe un isomorfismo de grafos tal que la imagen del antecesor de un nodo sea el antecesor de la imagen.

Es fácil ver que dos árboles son equivalentes según la definición si y sólo si son isomorfos como grafos enraizados. Por un lado, si son equivalentes entonces las raíces tienen que ser equivalentes, ya que son los únicos nodos de nivel 0, y según la definición eso implica que los grafos tienen que ser isomorfos. Por otro lado, si los árboles son isomorfos existe un isomorfismo, y es fácil de ver que cualquier isomorfismo hace corresponder necesariamente nodos equivalentes. Sin embargo es posible que dos nodos sean equivalentes y no exista ningún isomorfismo que a uno le haga corresponder el otro, como por ejemplo los nodos rojos de la siguiente imagen:

isomorfismo

En el problema se pide calcular si dos árboles son equivalentes (es decir, isomorfos), y si lo son, dar una equivalencia entre sus nodos. Cualquier isomorfismo es una equivalencia, pero además se pide que se respete el orden relativo de los nodos. Dicho de otra forma, la equivalencia f tiene que cumplir que no existan dos nodos a, b del primer árbol, con a<b, y dos nodos c, d del segundo árbol, con c<d, tales que a, b, c y d sean todos equivalentes, pero f(a)=d y f(b)=c. Es decir, si existen nodos a1<a2<…<an equivalentes a b1<b2<…<bn entonces la equivalencia tiene que ser f(a1)=b1,…,f(an)=bn. Es posible que dicha equivalencia no sea un isomorfismo, como en el ejemplo siguiente:

equivalencia

En el ejemplo la equivalencia buscada hace corresponder a cada letra de la izquierda la misma letra de la derecha, pero dicha equivalencia no es un isomorfismo, ya que B y D son adyacentes a la izquierda y no lo son a la derecha.

Calcular si dos grafos son isomorfos es en general un problema difícil. Sin embargo, en el caso particular de árboles enraizados sí que existen algoritmos eficientes que lo calculan, como el que se describe en esta página. Dicho algoritmo consiste en calcular, para cada nodo, un hash que identifique inequívocamente la clase de equivalencia a la que pertenece el subárbol generado por dicho nodo. Una forma de calcularlo es obtener la lista ordenada de hashes de los nodos hijos, y calcular el hash del resultado. Finalmente dos árboles son isomorfos, y por tanto equivalentes, si sus raíces tienen el mismo hash. El proceso tarda tiempo lineal en ejecutarse.

La ventaja del algoritmo es que también da una manera eficiente de dar la equivalencia entre dos árboles. En primer lugar calculamos los hashes correspondientes a los nodos de cada nivel, empezando por el último nivel. Para que los árboles sean equivalentes en cada nivel tiene que haber el mismo número de nodos con cada hash. Una vez comprobado que esto es así, la equivalencia se obtiene de manera sencilla: si hay n nodos con el mismo hash a cada lado, entonces al menor en orden lexicográfico de la izquierda le asignamos el menor de la derecha, al segundo menor de la izquierda el segundo menor de la derecha, y así sucesivamente, lo que da la respuesta buscada.

Challenge 13 – Legacy code

En este problema se te da un código en lenguaje máquina para procesadores Zilog Z80, y tienes que descubrir el mensaje secreto que se esconde en él. Como desgraciadamente no programo habitualmente lenguaje a máquina para dicho procesador, el primer paso parece ser buscar software existen que lo desensamble y que lo ejecute. Por lo visto el código contiene una secuencia de caracteres que se escribe en algún lugar de la memoria. Dicha secuencia se puede obtener de un editor hexadecimal, y es:

<<B~<B~|BBf@BB@B@BZ|BB|BN~B@BB@|BBB@B$@D<BB~<.~B

Donde el punto en realidad no es un punto, sino el carácter ASCII número 24, o 0x18. Esta secuencia tiene 48 caracteres, y tras interpretar el código y ver cómo se ejecuta, parece que se copia a una determinada posición de la memoria. Más concretamente, se divide en 6 trozos de 8 caracteres cada uno, y se sitúan en posiciones de memoria separadas, a una distancia de 32 bytes la una de la otra. Pero no consigo descubrir a qué corresponde esa sección de la memoria, ni cuál se supone que es la clave. Tratemos de analizar el mensaje.

Es evidente que el mensaje no es totalmente aleatorio. Si lo dividimos en 6 filas y 8 columnas, parece que la primera y la última fila son bastante diferentes que las otras. Veamos los códigos ASCII. Son todos pares. No puede ser casualidad. Veamos cómo son los códigos en binario. Es curioso, casi todos son simétricos y los que no lo son es por poco. Además tienen muchos unos y ceros consecutivos. No son caracteres al azar, su representación binaria tiene que tener algo que ver… ¿Y si las imprimimos en 6 filas y 8 columnas, como hace el código? Entonces obtenemos esto:

gameover

¡GAMEOVER! ¿Será esa la respuesta? El corrector me dice que sí. Pero no tiene mucho sentido… ¿Qué tiene que ver eso con un procesador de Spectrum? ¿Para qué nos dan el código si lo único interesante es el texto del final? ¿Sirve únicamente para saber que hay que dividirlo en 6 filas y 8 columnas? Bueno, sea como sea, la respuesta es correcta y quedan muchos problemas y pocos días. Las respuestas a estas preguntas tendrán que esperar. Lo envío y punto.

Una vez finalizado el concurso y viendo las soluciones de otros participantes todo empieza a cuadrar. ¡Es la pantalla! Los bits de esas posiciones de memoria se corresponden con los píxeles en blanco y negro de una pantalla, por lo que ese fragmento de código lo que hará será imprimir GAMEOVER por pantalla, en letras blancas sobre fondo negro. La pantalla muestra las posiciones de memoria entre la 0x4000 y la 0x5800. Es de 256×192 píxeles, es decir, 192 filas de 32 bytes cada una. El programa empieza escribiendo en la posición 0x482c, es decir, hacia un tercio de pantalla. Una vez finalizado la pantalla quedará así:

pantalla

Posiblemente se pueda obtener el mismo resultado usando un emulador que también imprima la pantalla.

Challenge 14 – SpeedRunner

Vuelven los problemas algorítmicos. En este caso nos dan un mapa bidimensional, y tenemos que conseguir llegar al final habiendo recogido una serie de llaves por el camino. Como nos piden además llegar en el mínimo tiempo posible parece que habrá que aplicar algún algoritmo de distancia en grafos.

La primera observación es que tu estado actual depende únicamente de tu posición. Que te puedas mover a izquierda o derecha, o bajar, no depende de como acabas de moverte ni de si estás cayendo. Eso quiere decir que el número de estados es lineal con respecto al tamaño de la entrada. Así que lo primero que haremos será calcular la distancia entre todas las llaves, y entre las coordenadas de entrada y de salida. Esto lo podemos hacer ejecutando un único BFS en cada uno de dichos puntos (llaves, entrada, salida), lo que tardará un tiempo proporcional al producto del tamaño de la entrada y el número de puntos (18 como máximo). Bastante asumible. Hay que tener en cuenta que hay unos determinados criterios para elegir entre varias soluciones que tardan lo mismo: en primer lugar haber presionado menos teclas (haber caído más veces), y si hay empate, que el orden de teclas pulsadas sea lexicográficamente menor. No es difícil adaptar el BFS para que además calcule cuál es dicha secuencia de teclas por cada par de puntos.

Una vez que tenemos todas las distancias, el problema consiste en ir de un punto a otro pasando por varios puntos intermedios. Es decir, resolver el problema del viajante de comercio. La solución trivial tarda tiempo O(n!), lo que puede ser mucho dado que el número de llaves es 16. En su lugar, usaremos el algoritmo de Held-Karp, que tarda tiempo O(2^nn^2), que para n=18 es más que suficiente. También hay que calcular cuál es la mejor secuencia de teclas para llegar, pero por suerte para ir de A a C pasando por B, la mejor secuencia consiste en la concatenación de las mejores secuencias entre A y B, y entre B y C, y como dichas secuencias ya están calculadas resultará fácil adaptar el algoritmo para que devuelva dicha secuencia. Mi implementación en C++ tarda cerca de medio minuto, incluso compilándolo con O3, pero todas las soluciones que he visto tardan un tiempo parecido. Tal vez se pueda hacer alguna modificación a bajo nivel, como no calcular explícitamente la secuencia hasta el final, pero dudo que se pueda hacer mucho más rápido, ya que estamos ante un problema NP-difícil.

Sigue aquí.