Descripción del problema

En 1989 la compañía británica The Assembly Line desarrolló el video juego Pipe Mania para la plataforma Amiga. Posteriormente fue distribuido a otras plataformas con el nombre de Pipe Dream. El juego inspiró a otros desarrolladores y se ha producido una cantidad numerosa de adaptaciones. Todas ellas comparten el mismo principio. El jugador debe construir o reconstruir una tubería por donde pasará un fluido, usualmente agua. La tubería se construye sobre un área matricial, donde el fluido surge de una o más fuentes y debe llegar a uno o más destinos. El jugador pasará al siguiente nivel si el camino construido logra transportar el fluido desde las fuentes hasta los destinos sin fugas.

input
Figure 1. Sesión en progreso del juego (nivel 001)

Por ejemplo, arriba se puede ver un nivel en progreso, donde el fluido surgirá de las válvulas al norte de la celda (1,1) y al este de la celda (1,4), y deberá llegar a través de la tubería al desagüe al sur de la celda (2,4). Sin embargo, el camino construido en la figura producirá dos fugas, una al sur de la celda (1,2) y otra al sur de la celda (2,2).

Por su estructura matricial, las celdas sólo pueden tener conectores en sus cuatro bordes, que en sentido antihorario son: superior (N=norte), izquierdo (W=oeste), inferior (S=sur), y derecho (E=este). Esta restricción limita la cantidad de piezas que el jugador dispone para construir las 16 tuberías listadas en la tabla Table 1.

Table 1. Los 16 tipos de tubos
Dec Hex Fig

0

0

0

1

1

1

2

2

2

3

3

3

4

4

4

5

5

5

6

6

6

7

7

7

8

8

8

9

9

9

10

A

A

11

B

B

12

C

C

13

D

D

14

E

E

15

F

F

Se quiere un programa que reciba el estado de un juego en progreso por la entrada estándar o en archivos. El contenido en la entrada estandar o en los archivos podría ser de texto o binario. El programa debe validar, resolver, o convertir el nivel que recibe de acuerdo a la elección del usuario.

Validar un nivel

Validar un nivel consiste en reportar adónde se encuentran las fugas dentro de una tubería dada. El programa debe validar cuando la acción validate es indicada en el primer argumento en la línea de comandos, como es el caso del ejemplo de invocación 1.

Ejemplo de invocación 1:

pipeleak validate -it

Ejemplo de entrada 1:

2 4 2 1

1 1 N
1 4 E
2 4 S

C 7 7 5
0 6 D 3

Ejemplo de salida 1:

leak 1 2 S
leak 2 2 S

El ejemplo de entrada 1 corresponde al nivel de la Figure 1. Este ejemplo usa una entrada de texto (más adelante se provee una entrada binaria de ejemplo). El programa debe interpretar la entrada como textual si se le provee el argumento -it. Este argumento se considera por defecto, y por tanto, el usuario podría omitirlo. Si en los argumentos de línea de comandos no se provee un nombre de archivo, el programa debe asumir que el estado del juego será provisto en la entrada estándar, como ocurre en el ejemplo de entrada 1.

La primera línea de la entrada textual recibirá cuatro números. Los dos primeros indican las dimensiones de la matriz en filas y columnas. El tercer y cuarto número indican la cantidad de fuentes de agua (hidrantes) y de destinos (desagües) respectivamente que tiene el nivel.

Tras la primera línea de la entrada textual, vendrá una línea en blanco, seguida por las ubicaciones de cada una de las fuentes de agua (hidrantes) y los destinos (desagües). La ubicación se indica con el número de fila y columna de una celda (iniciando en 1) y el punto cardinal hacia el que se encuentra el hidrante o desagüe. En el ejemplo anterior se tienen dos fuentes de agua: al norte de la celda (1,1) y al este de la celda (1,4); y un destino al sur de la celda (2,4). Puede suponer que las fuentes y destinos siempre se encuentran en el borde del nivel.

Finalmente, después de otra línea en blanco, la entrada tendrá el estado de la matriz que se quiere evaluar. Por cada celda se indica el código hexadecimal correspondiente al estado de la celda de acuerdo a la tabla Table 1.

El programa debe evaluar la tubería e indicar en el archivo de salida si hay fugas o no. Por cada fuga detectada se debe reportar una línea en formato leak R C D, donde R es la fila, C la columna, y D la dirección o punto cardinal de la celda dónde se produce la fuga. Esta información es útil para que el videojuego realice animaciones de fuga o llame la atención del jugador. Opcional: Si el archivo de salida es binario, se debe reportar cada fuga como dos enteros de 4 bytes sin signo, uno para la fila y otro para la columna, seguido de un carácter con la dirección (ver más adelante).

En caso de que no hayan fugas, el programa debe reportar el mensaje solved que indica que la tubería logra transportar el fluido desde las fuentes a los destinos sin fugas. Opcional: en caso de que la salida sea binaria y no hayan fugas, esta será vacía. El programa debe defenderse de entradas incorrectas o mal intencionadas reportando el mensaje invalid data.

Resolver un nivel

Resolver un nivel consiste en encontrar el estado de la tubería que permite al fluido desplazarse desde las fuentes hasta los destinos sin fugas. El programa debe resolver un nivel cuando la acción solve es indicada en el primer argumento en la línea de comandos como es el caso del ejemplo de invocación 2.

Ejemplo de invocación 2:

pipeleak solve -ib level001.bin

Contenido de level001/input.bin en hexadecimal:

02 00 00 00 04 00 00 00 02 00 00 00 01 00 00 00
01 00 00 00 01 00 00 00 4e 01 00 00 00 04 00 00
00 45 02 00 00 00 04 00 00 00 53 c7 75 06 d3

Ejemplo de salida 2:

2 4 2 1

1 1 N
1 4 E
2 4 S

C 7 7 5
0 C D 3

En el ejemplo de invocación 2 se usa el parámetro -ib que indica al programa interpretar la entrada estándar o los archivos en notación binaria. Esta notación es útil porque permite representar niveles grandes con menos bytes, que pueden cargarse más rápidamente en la memoria, y dificultan a un jugador adulterar los niveles del juego a su conveniencia.

En el ejemplo de invocación 2 se provee un nombre de archivo. El programa debe leer los datos del nivel desde el archivo y no de la entrada estándar. Si el usuario no hubiese provisto un nombre de archivo, el programa debe tomar el nivel en forma binaria de la entrada estándar.

Dado que no se puede mostrar el contenido binario original dentro de este documento, se incluye un "volcado" hexadecimal obtenido con el comando od -t x1 level001/input.bin. Cabe indicar que level001/input.bin corresponde al nivel de la Figure 1. En general, un nivel binario es un archivo cuyos enteros se representan en little endian y cuyos campos corresponden en orden a:

  1. Cantidad de filas (R): entero de 4 bytes sin signo.

  2. Cantidad de columnas (C): entero de 4 bytes sin signo.

  3. Cantidad de fuentes de fluido (S): entero de 4 bytes sin signo.

  4. Cantidad de destinos de fluido (T): entero de 4 bytes sin signo.

  5. S fuentes de fluido, cada uno de 9 bytes:

    1. Fila: entero de 4 bytes sin signo para la fila

    2. Columna: entero de 4 bytes sin signo para la columna

    3. Dirección: punto cardinal, carácter ASCII de 1 byte, con N=norte, W=oeste, S=sur, y E=este.

  6. T destinos de fluido, cada uno de 9 bytes:

    1. Fila: entero de 4 bytes sin signo para la fila

    2. Columna: entero de 4 bytes sin signo para la columna

    3. Dirección: punto cardinal, carácter ASCII de 1 byte, con N=norte, W=oeste, S=sur, y E=este.

  7. Estados de la matriz: R * C / 2 bytes. Cada byte contiene dos celdas de la matriz. Si la cantidad de celdas es impar, el último byte contendrá una celda sólo en los 4 bits más significativos.

Cuando la acción solve es provista, el programa debe encontrar la solución al nivel, es decir, aquella que permite al fluido desplazarse desde las fuentes a los destinos sin fugas. Su programa puede usar fuerza bruta para encontrar la solución (por ejemplo, backtracking). Se otorgarán puntos extra a soluciones más eficientes.

Para encontrar la solución a un nivel, el programa debe rotar cada pieza no nula sobre su propio centro en ángulos de 90 grados. Es decir, el programa no debe reemplazar piezas del tablero por otras ni moverlas de una celda a otra. Una vez que el programa haya encontrado la solución al nivel, debe imprimirla donde el usuario lo indique de acuerdo a los siguientes argumentos:

  1. Si se provee el argumento -ot filename, la matriz solución debe imprimirse en el archivo de texto indicado por filename, indiferentemente del formato de la entrada. Si se provee el argumento -ot pero se omite filename, se imprimirá la solución textual en la salida estándar.

  2. Si se provee el argumento -ob filename, la matriz solución debe imprimirse en el archivo binario indicado por filename, indiferentemente del formato de la entrada. Si se provee el argumento -ob pero se omite filename, se imprimirá la solución binaria en la salida estándar.

  3. Si se provee el argumento -o filename, la matriz solución debe imprimirse en el archivo indicado por filename que tendrá el mismo formato (textual o binario) que tiene la entrada. Si se provee el argumento -o pero se omite filename, se imprimirá la solución textual o binaria en la salida estándar.

  4. Si no se provee ninguno de los anteriores, se asume que la solución debe imprimirse en forma textual en la salida estándar.

En cualquier caso, la solución impresa debe ser un nivel completo. Es decir, la solución puede ser usada de entrada en otra invocación del programa. Por ejemplo, si la solución se usa como entrada con el comando validate, debería producir como respuesta solved.

Si no es posible resolver un nivel, el programa debe reportar unsolvable en la salida estándar, o si se pide que la salida esté en un archivo, las dimensiones serán 0 para las filas, 0 para las columnas, 0 para la cantidad de fuentes, y 0 para la cantidad de destinos.

Convertir

Convertir un nivel consiste en transformar su representación textual o binaria. El programa debe convertir cuando se provee la acción convert en el primer argumento. El usuario controlará la conversión con los argumentos -ib, -it, -ob, y -ot.

Evaluación

Control de versiones

El proyecto será realizado en parejas en un repositorio de control de versiones. Ambos participantes deben trabajar todas las fases del proceso (diseño, programación, documentación, pruebas) y deben dejar evidencia en el historial de commits. La nota de un participante será proporcional a la cantidad y calidad de los commits que realizó.

Por ninguna razón deben agregar archivos binarios a control de cambios o que hayan sido generados a través de un proceso automatizado, por ejemplo, archivos objeto (.o), ejecutables, bibliotecas (.so), documentación generada por Doxygen. En su lugar, deben tener un archivo .gitignore adecuado. Deben agregar a los dos profesores del curso y a los tres asistentes. Cualquier acto de plagio será sancionado severamente.

[10%] Documentación externa

Debe realizarse en el archivo ./README.md en la raíz del proyecto. Puede estar redactado en inglés o español. Debe resumir de uno a tres párrafos el problema a resolver y enlazar este documento. Debe indicar quiénes desarrollan la solución, un manual de usuario, y finalmente un manual de desarrollador.

El manual de usuario debe explicar cómo invocar el programa, qué significa cada opción, proveer varios ejemplos de ejecución, y explicar la entrada y salida en cada caso. Debe incluir un ejemplo de invocación de las ocho posibles combinaciones de: acción (validar|resolver) × entrada (textual|binaria) × salida (textual|binaria).

El manual de desarrollador debe explicar cómo compilar la solución, probarla, agregar casos de prueba, e instalar el ejecutable. Debe explicar cómo está estructurado el código fuente en el proyecto, en especial, cuáles archivos pertenecen a la biblioteca, al comando, y al programa de pruebas.

[5%] Estructura de proyecto

Los archivos del repositorio no pueden aparecer todos en la raíz, sino que deben estar distribuidos en carpetas características de un proyecto de Unix:

Recurso Descripción Versionado

bin/

Ejecutables del comando y del programa de pruebas

No

build/

Código objeto (.o) temporal

No

doc/

Documentación generada por doxygen en formato html

No

lib/

Biblioteca dinámica (.so) compartida por el comando y el programa de pruebas

No

src/

Código fuente (.h y .c)

Sí

test/

Casos de prueba propios, creados por el equipo

Sí

Makefile

Compila, prueba, instala, desinstala, genera documentación, limpia

Sí

Doxyfile

Configura Doxygen para extraer documentación del código fuente

Sí

README.md

Presenta el proyecto, incluye el manual de usuario y de desarrollador

Sí

.gitignore

Ignora los recursos que NO deben estar en control de versiones (columna Versionado)

Sí

La columna "Versionado" indica si los recursos deben estar o no en control de versiones. Note que NO puede haber redundancia de código entre el comando y el programa de pruebas. El código común debe estar alojado en la biblioteca dinámica.

Comando

Se debe desarrollar un comando que permita al usuario validar y resolver niveles del juego. El código fuente del comando debe estar en la carpeta src/cli/ del proyecto (CLI=Command Line Interface). Debe además estar modularizado en tripletas de archivos: el algoritmo (ej.: module.alg o module.md), encabezado (ej.: module.h), e implementación (ej.: module.c). Se evaluará:

  1. [10%] El diseño de la solución. El problema debe solucionarse usando algoritmos y escribirse en archivos de texto simple con extensión .alg o archivos en Markdown con extensión .md, al menos uno por cada módulo que se describe en los siguientes puntos. Los algoritmos deben usar los 8 tipos de instrucciones vistos en clase, y no deben tener comentarios de un lenguaje de programación (no iniciar con //).

  2. [10%] Argumentos en línea de comandos. El manejo de argumentos debe hacerse en su propio módulo (tripleta de archivos .alg, .h, .c). El comando debe satisfacer las restricciones ya planteadas en el enunciado del problema y las siguientes:

    1. El comando debe invocarse con una acción en el primer argumento. En caso contrario, o si se provee una acción desconocida, debe proveer ayuda al usuario.

    2. Si el usuario pide ayuda con el argumento --help, el comando la provee indiferentemente de otros argumentos que se hayan provisto.

    3. Las opciones (que inician con guión) pueden combinarse en cualquier orden, por ejemplo pipe_leak convert -ob file1.bin -it file1.txt tiene el mismo efecto que pipe_leak convert -it file1.txt -ob file1.bin.

    4. Si el usuario especifica una opción desconocida, el comando debe reportar error en el error estándar y terminar su ejecución.

    5. Si un archivo de entrada no existe, se debe reportar en el error estándar y terminar la ejecución.

  3. [10%] Implementación de la funcionalidad propia del comando y reutilizar el código la biblioteca, el cual debe enlazarse de forma dinámica (ver adelante). Es decir, si se realiza un cambio (ej. una corrección de una pulga) en la biblioteca, el comando se verá beneficiado sin tener que recompilarlo.

Biblioteca

Mientras desarrolla el comando propuesto, identifique el código que puede ser reutilizable, por ejemplo, para un videojuego de escritorio o web. El código reutilizable debe separarlo a una biblioteca cuyos archivos fuente deben estar en la carpeta src/pipeleak. Los siguientes rubros se evaluarán:

  1. [10%] Módulo de validación. Provee subrutinas que validan un nivel del juego y generan un reporte (en memoria) de fugas. Debe usar alguna estructura de datos y no imprimir en salida o archivo. Recuerde que todo módulo debe tener al menos una tripleta de archivos .alg, .h, .c.

  2. [15%] Módulo de resolución. Provee subrutinas que encuentran la solución a un nivel y generan una estructura de datos en memoria que representa el nivel resuelto.

  3. [10%] Módulo de conversión. Provee funcionalidad de conversión de formato textual y binario. Provee subrutinas para leer y escribir niveles textuales y binarios, tanto de la entrada estándar como archivos nombrados.

  4. [10%] Módulo común. Provee estructuras de datos y subrutinas comunes que necesitan los tres modulos anteriores.

  5. [10%] Documentación interna. Toda subrutina de la biblioteca debe estar cuidadosamente documentada en inglés o español, usando directivas de Doxygen. Debe proveer una página principal para la biblioteca y algunos ejemplos de uso.

  6. [5%] Diseño por contratos y programación defensiva. Todas las subrutinas de la biblioteca deben implementarse usando estas dos prácticas de programación. Todo supuesto (invariante) debe estar documentado con Doxygen y toda subrutina de la biblioteca debe defenderse de entradas inválidas, sea a través de condicionales o supuestos (asserts) depedendiendo de si el error es provocado por el usuario o el programador respectivamente.

Programa de pruebas

  1. [10%] Casos de prueba. Cada equipo debe crear al menos tres casos de prueba por integrante como se explica a continuación.

En la carpeta tests/ cree tres subcarpetas con la notación tests/levelNNN/ donde NNN es un número arbitrario de tres dígitos (mayor a 100). En cada subcarpeta agregue un archivo de texto test/levelNNN/levelNNN-input.txt y escriba un caso de prueba en modo texto. Cree al menos dos niveles resolubles, y al menos uno irresoluble. Al menos uno de los niveles resolubles debe ser "realista" (como los que se encontrarían en un videojuego de la temática), y tener dimensiones arbitrarias mayores a 5x5. Agregue estos archivos a control de versiones. Al final, el repositorio de dos integrantes deberá tener al menos seis casos de prueba.

Para crear los demás archivos del caso de prueba (entrada binaria, solución textual, solución binaria y resultado de la validación), puede usar editores de texto y hexadecimales. Alternativamente puede descargar una solución ejecutable y extraerla a alguna carpeta listada en la variable $PATH de su ambiente de comandos, por ejemplo, $HOME/bin. Eventualmente podrá reemplazar esta solución por la propia conforme progrese en el proyecto. Para generar los archivos restantes del caso de prueba puede usar el script level.sh provisto al final de este documento:

cd tests/
./level.sh NNN

Buenas prácticas de programación

  1. Sin fugas de memoria (valgrind)

  2. Identación

  3. Identificadores significativos

Archivos provistos

box c
pipeleak-v1.0.7z

El comprimido anterior cuenta con casos de prueba y un Makefile que puede extraer sobre su repositorio (asegúrese de no sobrescribir cambios a los que no haya hecho commit). Los siguientes enlaces podrían tener versiones actualizadas de los archivos que se encuentran en el comprimido:

  • Makefile. Un Makefile que compila el código fuente separado en tres productos: (1) el ejecutable del comando, cuyo código fuente debe estar en la carpeta src/cli/, (2) una biblioteca dinámica cuyo código proviene de src/pipeleak/, y (3) un programa de pruebas cuyo código se encuentra en la carpeta src/tester/.

  • tests. Carpeta con casos de prueba de caja negra.