Pues sí, el ganador en la categoría de mejor reverser de la segunda edición de los 48bits Academy Awards ha sido nuestro amigo Miguel, con esta solución.

En efecto, como se puede ver en la solución de Miguel, el fichero de licencia comienza con un byte de control, seguido de un entero de 32 bits, y a continuación un array de 511 bytes. Estos 511 bytes son los nodos de un árbol binario perfecto de profundidad 8. Recordemos que un árbol binario es aquel en el que cada nodo puede tener 0, 1 o 2 dos hijos, y es perfecto cuando no hay ningún nodo que tenga un solo hijo, y todas las hojas están en el mismo nivel de profundidad. Los 511 nodos están dispuestos según el recorrido inorder del árbol, que consiste en hacer el recorrido del subárbol izquierdo, procesar el nodo actual, y luego recorrer el subárbol derecho. El array resultante parece ser una representación aplastada del árbol, como se muestra en la figura. Además, al tratarse de un árbol perfecto, la raíz del árbol cae justo en el centro del array.

El algoritmo de verficación consiste en recorrer el árbol comenzando por la raíz, hasta una de sus hojas, usando los bits del byte de control para decidir en cada nivel si descendemos por la rama izquierda o derecha del nodo actual. Si el bit es 0 vamos por la izquierda, si es 1 por la derecha. Naturalmente el árbol tiene 8 niveles (o 9 se cuenta la raíz) porque el byte de control tiene 8 bits, y se usa un bit para tomar la decisión «izquierda o derecha» en cada nivel. Al hacer el recorrido se van sumando los valores de los nodos por lo que se pasa, y al final este valor tiene que ser igual al entero de 32 bits que sigue al byte de control.

Como ven el algoritmo es muy sencillo, pero es un buen ejercicio para refrescar algunos conceptos básicos relacionados con la recursividad y los recorridos de árboles. Además vale la pena echarle una ojeada a la solución de Miguel, que aprovecha las características del árbol y su recorrido para hacer una implementación iterativa del algoritmo.