EDAMAZE: Práctica final de PS (Programación de Sistemas) ----------------------------------------------- Por: Daniel Clemente Laboreo Francesc Xavier Morales Pascual Descargable desde http://www.danielclemente.com/apuntes/ps/programa/ Cuatrimestre de otoño: septiembre 2004 - enero 2005 FIB (Facultad de Informática de Barcelona), UPC (Universidad Politécnica de Cataluña) Introducción (en el enunciado se explica mejor) ------------ Esta práctica va de generar y resolver laberintos. Hay que producir laberintos perfectos (sin ciclos) pero poder resolverlos todos, encontrando siempre el camino más corto. Aquí se ve un ejemplo: se genera uno perfecto de 7x15, y luego se resuelve desde 1,1 hasta 7,15. Como el laberinto es perfecto, el camino es único y es "el más corto". dc@tup:~/ps/ult/pack-Linux$ ./test1 7 15 ******************************* * * * * * * * * * * * * * * * *** *** * * * ***** * * * * * * * * * * * * *** * ********* * * * *** * * * * * * * * * * * ***** * * * ********* *** * * * * * * * * * * * * ***** * * * * * *** *** * ***** * * * * * * * * * * *** ******* * * * * ***** * * * * * * * * * * * *** * ********* *** *** * * * * * * * * * * ******************************* Solució de 29 passos: 1, 1 2, 1 2, 2 3, 2 3, 3 3, 4 4, 4 4, 5 3, 5 3, 6 4, 6 4, 7 5, 7 6, 7 6, 8 6, 9 6, 10 5, 10 5, 11 6, 11 7, 11 7, 12 7, 13 6, 13 6, 14 5, 14 5, 15 6, 15 7, 15 [0/0] Contenido --------- edamaze/ : la práctica, en código fuente (C++) edamaze.tar.gz : lo mismo, pero comprimido enunciat-Q1-0405.ps.gz : enunciado completo y especificación driver_maze.gz : el ejecutable compilado guia-normas-c++.2.ps.gz : pautas a seguir en esta asignatura pack-pruebas-linux.tgz : librería EDA para Linux y juegos de pruebas pack-pruebas-solaris.tgz : librería EDA para Solaris y juegos de pruebas Implementación -------------- El programa está hecho en C++ usando las librerías propias de la asignatura: libeda, que sirven para control de errores, gestión de memoria dinámica, generación de números aleatorios, y juegos de pruebas automáticos. No son imprescindibles. No hay documentación, pero el código está muy comentado (en catalán). Con el enunciado nos daban todos los ficheros .hpp, y está prohibido modificarlos. Nosotros hemos escrito los: .rep: parte privada de cada clase .cpp: implementación de métodos públicos y privados de cada clase .t: implementación de las clases genéricas (las que van con templates) Compilación ----------- Se ha hecho bastante complicado porque no tenemos el código fuente de la libeda; se nos dio compilada para usar con g++-2.95. No se pueden usar compiladores mejores (g++-3.4), ya que el código que nos han dado en los .hpp tiene errores de diseño no aceptados por la especificación C++, en concreto la inicialización de miembros static cuando son de tipo no integral. Aún así, a nosotros nos obligaban a compilar con los flags -ansi -Wall :-) Esto nos ha dado muuuchos errores y horas perdidas probando cosas a ciegas, hasta que descubrí la solución: en vez de pasarle la opción -leda a gcc para que compile usando libeda.a, hay que extraer los objetos .o del archivo .a (man nm) y enlazarlos junto con los demás .o (siempre que hagan falta, claro). Eso, y tener suerte para que el compilador acepte los errores de los .hpp. Si no hay suerte, ignorará las declaraciones y se quejará de "undefined reference to...". En general, para compilar: 1. Compilar (no enlazar) laberint.cpp, cambra.cpp, teseus.cpp, dedalus.cpp, driver_maze.cpp 2. Enlazarlos todos ellos junto con error.o, mem_din.o, util.o, gen_driver.o (que son los de libeda.a) y junto con check.o y driver_maze.o si se quiere usar el juego de pruebas. 3. No tiene que dar ningún error. Ejecutar. Juegos de pruebas ----------------- En los pack-Linux y pack-Solaris hay información sobre cómo probar automáticamente el programa. Desgraciadamente, se cuelga al llegar a la función chequea_camino_minimo del check.o, y al no tener el código no sabemos por qué es. Junto con el juego.in está la salida esperada. Un diff con la salida actual no debería dar diferencias, aunque se dejaron algún acento y eso hace que las salidas no coincidan :-( Además del juego de pruebas público están los privados, que no tenemos. Funcionamiento interno ---------------------- El laberinto se graba como una matriz dinámica de punteros a modelos de sala. Eso es más eficiente que una matriz de salas; mira en el laberint.rep para más detalles. Las rutinas de entrada y salida transforman el dibujo (con asteriscos) en la representación interna de salas con paredes. El algoritmo de resolución es el Breadth First Search (búsqueda en paralelo), que garantiza el camino mínimo. Se implementa con un árbol, una lista, y una matriz de booleanos. El algoritmo de generación es parecido al de Kruskal, y excava túneles al azar hasta que todas las salas quedan unidas. Usa la clase particio, que maneja conjuntos con representante. Según unas pruebas que hicimos con un profiler (gmon), particio es la más lenta de todas. Su implementación (con una lista enlazada simple) puede mejorarse mucho haciendo una lista de listas. Licencia -------- Nuestro programa tiene licencia "haz lo que quieras", o sea, sin licencia. Úsalo como quieras, sobre todo para aprender. La librería libeda es del departamento de LSI y se supone que es sólo para alumnos de sus asignaturas. Me han dejado ponerla en mi web para bajar (la versión compilada, que usábamos nosotros). Si eres de una academia que busca exámenes y prácticas con su solución para dar los cursos intensivos, mejor háztelos tú. A los profesores no les gusta publicar el material en Internet porque temen que los profesores de academia los usen sin tener que esforzarse mucho. Pero mi opinión es: usa el material para lo que quieras: aprender, enseñar, resolver problemas, ... Cuanto más útil te sea, mejor. Nota ---- Nos pusieron un 10, aunque falló algunos juegos de pruebas (me imagino que los que hacían laberintos muy grandes, porque no dio mucho tiempo a probarlo y me parece que se colgaba). Ningún alumno consiguió pasar todos los juegos de prueba... Menudos informáticos que estamos hechos :-) --- Feb 2005 http://www.danielclemente.com/ --- EOF