May 29 2008
HackIt! Nivel 11: backtracking
Después del dolor del nivel 10 (un nivel genial no quita que no pueda ser doloroso ;-) llegamos al nivel 11 un tanto “acongojados”, porque asumimos que, como la dificultad vaya en aumento, nos pueden dar las uvas.
Sin embargo, tras leer el enunciado, yo creo que este nivel no debería de haber ocupado el puesto número 11, sino alguno inferior, pues es resoluble incluso por “fuerza bruta visual”, es decir, cogemos lápiz, cogemos papel y se puede resolver (no es trivial, pero se puede hacer con algo de tiempo y paciencia). Pero me estoy adelantando; la prueba pide que, en el siguiente tablero, encontremos un camino tal que el número de baldosas de cada color que atravesemos sea el mismo. Por ejemplo, 2 verdes, 2 azules y dos amarillas. El blanco no cuenta (casillas inicial y final). Se sobreentiende que no se puede pisar 2 veces la misma casilla (no lo dice el enunciado pero es una asunción que hago):
Aquellos de vosotros que habéis estudiado algoritmos de backtracking en el pasado (y os acordáis de algo ;-) me imagino que os estaréis frotando las manos, porque efectivamente, es resoluble por backtracking. Por cierto, cómo cambia la carrera de informática… hoy en día, en mi facultad, la asignatura de “Estructuras de datos y algoritmos” en Ingenieros Técnicos en Informática (que por cierto me tocó impartir este año), no se incluía la parte de backtracking por distintas cuestiones que mejor me ahorro comentar (y no son todas por “culpa de los profesores”). No me parece bien. Así que, el año que viene (y si los hados me designan a Donostia otra vez) pienso dar la tabarra hasta que encaje, como antaño, esta parte de la asignatura en el temario. Tal vez tenga que pedir también que nos pongan una máquina de café más cerca del aula… ;-)
Ahora que estamos en temporada de exámenes, sé que cualquier excusa es buena para dejar de estudiar (como dice mi blog-colega txipi, “incluso os enrolaríais en un carguero uzbeko” con tal de no hincar los codos ;-) …. esta prueba de HackIt tiene su cosita: es probable que aprendáis (aprender de verdad) más de recursividad y algoritmos de backtracking resolviéndola por vuestra cuenta que estudiando la teoría correspondiente. Os pasaré mi propuesta de solución en Java en unos días… aunque ahora que lo pienso, igual la guardo como ejercicio para el año que viene };-)
Curioso lo del barco uzbeko porque Uzbekistan carece de flota, si exceptuamos los barcos oxidados varados a kilómetros del actual Mar de Aral…
txipi habla de carguero en lugar de barco:
http://blog.txipinet.com/2008/05/24/call-for-levelz/
He corregido el post para reflejar las palabras exactas.
De todas formas, me imagino que precisamente porque tal cosa (“carguero uzbeko”) no existe es por lo que esta expresión tiene su fuerza ;-)
La verdad es que con un par de pruebas lo resolví “a la pasatiempos” sin problemas (yo creo que no es demasiado complicado)
Y el programa de backtracking como comentas si has hecho alguno no tiene demasiada dificultad (por cierto yo lo he hecho en C, me debo estar haciendo grande ;-)
Lo de ordenar los niveles tiene su miga, porque no estoy tan seguro de que haya que ordenarlos por dificultad estrictamente creciente. Es importante intercalar diferentes temáticas, para que cada nuevo nivel te obligue a pensar de forma diferente. Si ponemos todos los de reversing al final, se trataría de un concurso de reversing con unas cuantas pruebas molestas al principio. De todas formas, creía que el de los romanos era hiperfacil y que el de los cuadrados obligaría a darle al backtracking, pero me equivoqué en los dos O;-D
Flipo con que le deis vueltas a lo del carguero uzbeko :-DDD ¡Estáis fatal!
¡Juanan! Apareces en Linux+ en las páginas recomendadas. Llevo un par de semanas con la revista y me doy cuenta ahora de que estas en la cara interna de la contraportada.
Es un poco rebuscado, pero apareces.
@txipi: esas dos pruebas , cifrado César (la 5) y Backtracking (la 11) las intercambiaría. El resto bien. Pero agua pasada no mueve molinos. Por cierto, ¿habrá molinos en Uzbekistán?
@x510: pues sí, desde hace tiempo. Por cierto, en el screenshot sigue saliendo la vieja versión de diariolinux.com..
Puede el carguero cruzar el mar del tablero en diagonal?
XDDDDDDD …. no, no se puede (jajaja….)
La verdad es que es una pena de nivel. En 5 minutos se saca la contraseña por pura lógica (sin necesidad de algoritmos). Quizás una solución factible para forzar el uso de código/algoritmos sería hacer un tablero de 16×16. Sería interesante hacer un programita que creara tableros de n x n con una sola solución (un poco más de Backtrack).
PD: lucha por ello Juanan! en la superior si que se da ese tema :)
hola: acabo de encontrar este sitio y comienzo a sumergirme en el mundo linux y sus derivados, bueno lo que me interesa es cual es el objetivo de ete mini tuto el cual se ma hace interesante y como no encontre la primera parte no comprendo y quisiera saber si me podrias pasar el documento completo para verlo con mas detalle y tranquilidad
ojala me puedan ayudar saludos
evilpachan: pincha en la categoría “hackit” (del menú de la izquierda de DiarioLinux) para ver todos los artículos relacionados con este concurso de seguridad informática. De hecho, te facilito la URL directa –> http://diariolinux.com/category/hackit/
muy buena la página de hack it, y tú blog también jeje
lo resolví mirandolo fijamente jeje, creo que no merece el nivel 12 ;) ya que digamos que como no sabía que el md5 se podiía descifrar tán fácilmente me costó mas el nivel 2 que este jajaja … mira que lo estaba intentando tirar por fuerza bruta… ah… y antes de que me dira cuenta que era md5 no veas el lio con el codigo too lioso… que si aumentamos los caracteres, que si intercambiamos variables, que si mezcalmos más cosas por aquí y unas cuantas por ahí jaja
xAUU