Finalmente el Martes se me acabaron las vacaciones! 🙁 , y bueno … tocaba poner un post-post-vaca-cional. En general han sido unas vacaciones entretenidas :

El día 1 el «Osu, Tatakae, Sexy Pandas!» Team (si seguís el enlace podeís encontrar algún indicio de la etimología del nombre) , formado por 7 «elementos» de diversos puntos geográficos, tomamos un avion directo hacia el mismísimo corazón del vicio y las construcciones horteras, también conocido como «Las Vegas».

Nos dirigíamos a la famosa DefCon para competir en la final del conocido «Capture The Flag«, este juego organizado por la gente de Kenshoto es un wargame de seguridad informática donde ocho equipos luchan por la preciada Black Badge que da acceso eterno a la DefCon. Para llegar a la final se realizan unas pruebas clasificatorias en las que, aunque por los pelos y con momento final de película, nos clasificamos entre los siete equipos que la jugarían, siendo el octavo equipo el ganador del año anterior (1@stplace) .

(más…)

Durante la última semana me han llegado varias soluciones al reto de la suma máxima en la lista de números. El primero en enviarla fue erg0t, que escribió este algoritmo en puro y duro C. Pero cansado de este lenguaje tan vulgar, sin glamour, y con tan poca clase (bastante que tiene structs), erg0t nos deleita con otra solución en el exclusivísimo e inescrutable Haskell.

He de decir que jamás había visto en mi vida ni una línea de código en Haskell, pero como buen jurado que soy he buscado un intérprete de Haskell, unos manuales en internet, y he comprobado que funciona. Incluso he llegado a entenderlo tras unas cuantas horas de investigación. Enhorabuena a erg0t por lo exótico de su solución.

También tenemos la solución de Miguel, que se va haciendo habitual, y que en realidad son dos soluciones: el algoritmo más obvio, de orden cuadrático, y el óptimo, de orden lineal. Además las explicaciones son abundantes y podemos disfrutar de esa notación húngara que delata sus orígenes Windowseros :).

Rodrigo Marcos nos ha envíado también su solución en Python, y yo mismo, después de que erg0t despertara mi interés por los lenguajes no imperativos, he programado mi solución en Prolog.

También quiero hacer una mención especial a Ángel Alonso que se curró una solución de última hora en Perl, pero no pudo terminar de ponerla a punto por falta de tiempo. Habrá más retos en el futuro para una revancha Ángel.

Y el que se lleva la estatuilla esta vez es… tara tatá tatá… erg0t! Por la solución más curiosa y eficiente al mismo tiempo.

Para no perder el ritmo seguimos proponiendo nuevos retos en 48bits, y esta vez no se trata de ingeniería inversa, se trata de un reto de programación, porque un buen reverser tiene que ser además un buen programador. Para este reto haremos lo mismo que antes, las soluciones me las envían por correo a plusvic[at]yahoo[dot]com, y dentro de una semana más o menos publicaremos las soluciones recibidas y eligiremos la mejor. Se admite cualquier lenguaje de programación razonablemente usado en el siglo XXI, ya sabéis: C y familia, incluyendo al primo sharp, Java, Python, Perl — que sé que hay algún fan de Perl por ahí 😉 — , Pascal, Ruby, ensamblador si hay algún valiente –pero nada de MASM que Mario se pone de mala leche–, y que hostias…. el que les de la gana, a ver si hay huevos y alguien manda el programa para la máquina de Turing. Pero al grano, el problema es este:

Dada una lista de N números enteros (positivos y negativos), encontrar el mayor valor que es posible obtener sumando cualquier grupo de números consecutivos dentro de la lista. Por ejemplo, si la lista fuera: 1,-2,5,3,-4,5,0,2,-2,3,-7,5,1. La mayor suma que se puede obtener es 12, resultado de sumar los valores 5,3,-4,5,0,2,-2,3. No hay otra suma de números consecutivos dentro de la lista que sea mayor que 12. El programa naturalmente recibirá como entrada una lista con una cantidad arbitraria de números (en un fichero, por teclado, o como se prefiera) y retornará el valor de la suma máxima, y si es posible, también la secuencia de números que forman parte de la suma. Se valorará la eficiencia en cuanto a tiempo de ejecución para valores grandes de N.

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.

Ya en otra ocasion se me habia revelado un secreto que hicieron tambalearse los aparentemente solidos cimientos sobre los que se asientan mis convicciones, los cimientos que dotan de sentido mi existencia, esos axiomas inquebrantables e inmutables, tan evidentemente ciertos que no pueden ser puestos en tela de juicio. ¿O si pueden?… La revelacion a la que me refiero no es otra que la existencia de un clon de Mario en Microsoft. Y ahora, nuevos datos de gran importancia han llegado a mis manos. Como los
he conseguido o quien me los ha dado son cuestiones que carecen de importancia. Lo cierto es que obran en mi poder. Me veo obligado, en pro del bien comun, a hacer publica esta información.

(más…)