Ikasten.IO
Learning, Aprendiendo

HackIt! Nivel 11: backtracking 29 mayo, 2008

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 };-)

  • etxekalte dice:

    Curioso lo del barco uzbeko porque Uzbekistan carece de flota, si exceptuamos los barcos oxidados varados a kilómetros del actual Mar de Aral…

  • admin dice:

    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 😉

  • xavier Sala dice:

    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 😉

  • txipi dice:

    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!

  • x510 dice:

    ¡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.

  • admin dice:

    @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..

  • anonimous dice:

    Puede el carguero cruzar el mar del tablero en diagonal?

  • admin dice:

    XDDDDDDD …. no, no se puede (jajaja….)

  • ToMaSuLo dice:

    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 🙂

  • evilpachan dice:

    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

  • admin dice:

    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/

  • CrazyBoSS dice:

    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

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *